Thread: Trouble with an algorithm to find edges

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    2

    Trouble with an algorithm to find edges

    I will try to be as thorough as possible in describing the problem here, but the task at hand is a peculiar one so I may miss something. let me know if it is unclear.

    So, I am working on a CFD code. I am still new to programming, so the part I have been given to work on is relatively easy: Given a field of points, I am supposed to find out which correspond to the object in the center of the field. For clarity, here's what that looks like in an x-y plot: Example.

    Now, the program I am working with spits out these points as a series of triangles. The points in the field are numbered from 1 to N, and each triangle is presented as a list of three of these points. I first divide these triangles into three edges apiece. To find out where the object in the center lies, in this case a wing, I need to find the edges that don't repeat, as the only places where triangles aren't touching each other is the surface of the wing.

    The first code I wrote to do this worked just fine, but it was naive and slow: it compared every single edge to every other edge to find matches. That's fine on a small scale, but ultimately I'll be working with data that has hundreds of thousands of points. So, I've been working on an algorithm to make things quicker.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
    
    //I've gotten rid of the code that reads the file and converts that data
    //into edges, to make this easier to read.  I know that part works fine.
    
    //E = Number of triangles
    //N = Number of points
    
    vector<int> Newalg (9*E,0); //3 edges per triangle * 3 spaces per edge (two for endpoints, one to mark duplicates)
    vector<int> Newcheck (N,0);
    int temp1 = 0;
    int temp2 = 0;
    //write all edges to newalg:
    for (int i=0;i<3*E;i++)
    {
        Newalg[3*i] = Edges[2*i];
        Newalg[3*i+1] = Edges[2*i+1];
        temp1 = Edges[2*i] - 1;
        temp2 = Edges[2*i+1] - 1;
        Newcheck[temp1] += 1;
        Newcheck[temp2] += 1;
    };
    //find max instances of any one point
    int inst = 0;
    for (int i=0;i<N;i++)
    {
        if (Newcheck[i] > inst)
        {
            inst = Newcheck[i];
        };
    };
    vector<int> Instances (inst*N,0); //This allows one to compare edges only with those edges in which the same point apppears
    temp1 = 0;
    temp2 = 0;
    for (int i=0;i<N;i++)
    {
        Newcheck[i] = 0; //resets vector for use in next loop
    };
    int temp3 = 0; //placeholder value for stacking vectors
    for (int i=0;i<3*E;i++)
    {
        temp1 = Newalg[3*i];
        temp2 = Newalg[3*i+1];
        //check against all other cases found thus far
        for (int j=0;j<inst;j++)
        {
            if (Instances[j] == 0)
            {
                continue;
            };
            temp3 = Instances[inst*(temp1-1)+j] - 1;
            if ((Newalg[3*temp3] == Newalg[3*i]) && (Newalg[3*temp3+1] == Newalg[3*i+1]))
            {
                Newalg[3*i+2] = 1;
                Newalg[3*temp3+2] = 1;
            };
            temp3 = Instances[inst*(temp2-1)+j] - 1;
            if ((Newalg[3*temp3] == Newalg[3*i]) && (Newalg[3*temp3+1] == Newalg[3*i+1]))
            {
                Newalg[3*i+2] = 1;
                Newalg[3*temp3+2] = 1;
            };
        };
        //first endpoint write
        Newcheck[temp1-1] += 1; //-1 relates to fact that vector starts at 0
        temp3 = Newcheck[temp1-1];
        Instances[inst*(temp1-1)+(temp3-1)] = i+1;
        //second endpoint write
        Newcheck[temp2-1] += 1;
        temp3 = Newcheck[temp2-1];
        Instances[inst*(temp2-1)+(temp3-1)] = i+1;
    };
    //eliminate all rows with "1" in third column
    temp3 = 0;
    for (int i=0;i<3*E;i++)
    {
        if (Newalg[3*i+2] > 0)
        {
            Newalg[3*i] = 0;
            Newalg[3*i+1] = 0;
            Newalg[3*i+2] = 0;
            temp3++;
        };
    };
    cout<<"Eliminates "<<temp3<<" edges"<<endl;
    };
    Basically, it's supposed to find all the edges in which an endpoint appears, and compare them to one another to find matches instead of trying against every single edge. The most times any endpoint appears in these edges is 20 for the data set I'm working with right now, which is much smaller than the ~21000 total edges.

    I know from the naive original program that I should get 80 edges on the wing. This code produces 20658. I've spent probably 50 hours trying to figure out where the problem is, and haven't had any luck. If you can spot my error, I will be much obliged, as this is starting to gnaw on my sanity.

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    It is a bit confusing to read through yes, perhaps you would be better using a more descriptive data type to hold your information in, which would let you think more clearly about the problem, We dont know what your source data looks like (the edges conversion you do) but perhaps it would be better to use structs with appropriate member variables to describe the edges?
    Also in the case where you have all these many thousands of points, what about your total memory requirements?
    I dont understand this completely but i would approach this with the debugger and the smallest possible set of data that represents the task. Probably a unit test with the test data hardcoded. Then do some careful stepping through etc.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I agree with rogster about datatypes. Make an Edge datatype (you'll have to make sure that either you have the vertices go in the same way every time or you can check == whichever way the vertices go), and then just make a list and sort it. If you have duplicate edges they'll end up next to each other.

  4. #4
    Registered User
    Join Date
    Aug 2011
    Posts
    2
    Well, I just figured it out. In the unlikely event that anyone else has this problem, the issue was with the giant loop in the middle. By separating the sorting of points into their specific instances and the checking of those instances against every other instance, it runs just fine. Fixed code is below.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
    
    //I've gotten rid of the code that reads the file and converts that data
    //into edges, to make this easier to read.  I know that part works fine.
    
    //E = Number of triangles
    //N = Number of points
    
    vector<int> Newalg (9*E,0); //3 edges per triangle * 3 spaces per edge (two for endpoints, one to mark duplicates)
    vector<int> Newcheck (N,0);
    int temp1 = 0;
    int temp2 = 0;
    //write all edges to newalg:
    for (int i=0;i<3*E;i++)
    {
        Newalg[3*i] = Edges[2*i];
        Newalg[3*i+1] = Edges[2*i+1];
        temp1 = Edges[2*i] - 1;
        temp2 = Edges[2*i+1] - 1;
        Newcheck[temp1] += 1;
        Newcheck[temp2] += 1;
    };
    //find max instances of any one point
    int inst = 0;
    for (int i=0;i<N;i++)
    {
        if (Newcheck[i] > inst)
        {
            inst = Newcheck[i];
        };
    };
    vector<int> Instances (inst*N,0); //This allows one to compare edges only with those edges in which the same point apppears
    temp1 = 0;
    temp2 = 0;
    for (int i=0;i<N;i++)
    {
        Newcheck[i] = 0; //resets vector for use in next loop
    };
    int temp3 = 0; //placeholder value for stacking vectors
    for (int i=0;i<3*E;i++)
    {
        temp1 = Newalg[3*i]-1;
        temp2 = Newalg[3*i+1]-1;
        temp3 = Newcheck[temp1];
        Instances[inst*temp1+temp3] = i+1;
        Newcheck[temp1]++;
        temp3 = Newcheck[temp2];
        Instances[inst*temp2+temp3] = i+1;
        Newcheck[temp2]++;
    };
    for (int i=0;i<N;i++)
    {
        for (int j=0;j<inst-1;j++)
        {
            temp1 = Instances[inst*i+j]-1;
            for (int k=j+1;k<inst;k++)
            {
                temp2 = Instances[inst*i+k]-1;
                if ((Newalg[3*temp1] == Newalg[3*temp2]) && (Newalg[3*temp1+1] == Newalg[3*temp2+1]))
                {
                    Newalg[3*temp1+2] = 1;
                    Newalg[3*temp2+2] = 1;
                };
            };
        };
    };
    for (int i=0;i<3*E;i++)
    {
        temp1 = Newalg[3*i]-1;
        temp2 = Newalg[3*i+1]-1;
        if (fabs(Var[6*temp1]) > 3 || fabs(Var[6*temp1+1]) > 3 || (fabs(Var[6*temp1]) > 3 && fabs(Var[6*temp1+1]) > 3))
        {
            Newalg[3*i+2] = 1;
        };
        if (fabs(Var[6*temp2]) > 3 || fabs(Var[6*temp2+1]) > 3 || (fabs(Var[6*temp2]) > 3 && fabs(Var[6*temp2+1]) > 3))
        {
            Newalg[3*i+2] = 1;
        };
    };
    //eliminate all rows with "1" in third column
    temp3 = 0;
    for (int i=0;i<3*E;i++)
    {
        if (Newalg[3*i+2] > 0)
        {
            Newalg[3*i] = 0;
            Newalg[3*i+1] = 0;
            Newalg[3*i+2] = 0;
            temp3++;
        };
    };
    //compress
    //-make a counter set at zero
    int newcount = 0;
    //-as loop runs, fill data in from behind
    //-if line==0, move it to counter*3 (deleting third row would be tricky and unnecessary)
    //-for each instance of a remaining edge found, counter++
    for (int i=0;i<3*E;i++)
    {
        if (Newalg[3*i] != 0)
        {
            Newalg[3*newcount] = Newalg[3*i];
            Newalg[3*newcount+1] = Newalg[3*i+1];
            Newalg[3*i] = 0;
            Newalg[3*i+1] = 0;
            newcount++;
        };
    };
    cout<<newcount<<" edges remain."<<endl;
    };
    Thanks for looking at this anyway!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithm::find on string
    By rodrigorules in forum C++ Programming
    Replies: 2
    Last Post: 02-26-2011, 04:18 AM
  2. help me find a better algorithm for primes
    By nick2 in forum C Programming
    Replies: 4
    Last Post: 05-30-2009, 07:59 AM
  3. Shortest path algorithm with a maximum number of edges limit
    By blackslither in forum C Programming
    Replies: 4
    Last Post: 12-28-2008, 04:49 PM
  4. Recursive algorithm to find the determinant of a matrix
    By mahesh.mach in forum C Programming
    Replies: 3
    Last Post: 06-07-2007, 09:13 AM
  5. Trouble W/Getline Algorithm
    By drdroid in forum C++ Programming
    Replies: 7
    Last Post: 02-26-2003, 09:39 AM