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.

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.

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.

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!