Space line, how to find the red boundary?
Basically the algorithm would be like this:
1.) Build an index of all start- and endpoints of the lines.
2.) Now you can represent lines by index pairs. I.e. the four lines around face A are (0,1), (1,4), (0,3) and (3,4).
3.) Create a "connection map". I.e.:
std::map<unsigned, std::vector<unsigned> > connections;
connections[0].push_back(1);
connections[1].push_back(0);
connections[0].push_back(3);
connections[3].push_back(0);
connections[3].push_back(4);
connections[4].push_back(3);
connections[3].push_back(6);
connections[6].push_back(3);
...4.) For every connection look for closed triangle- or quad-loops. I.e. (3,4) has two loops: face A and C. If a connection is within two loops, it is an inner connection. If it has only one loop, like (6,7) and (7,8) it is an outer boundary.
It's not too difficult.
Let's say you start at (3,4)
In the connections map you find the points connected to 3 and 4.
- Set3: 0,6,9 (point 9 is left of point 3. It isn't drawn in my picture)
- Set4: 1,5,7
We first check, whether there is a triangle: Does one or two of the points in Set3 connect to 4?
If there are less than two triangle connections then we search for quad connections between Set3 and Set4.
In this case there is no triangle connection. But we easily find the two quad connections (0,1) and (6,7).
And now, because we found two connections, you can tell that (3,4) is an inner connection.
My algorithm，3-4 there are two results, proving that it is not a boundary
No. 1
3-4
No. 2
3-4-1
3-4-5
3-4-7
No. 3
3-4-1-0
3-4-1-14
3-4-1-2
3-4-5-2
3-4-5-10
3-4-5-8
3-4-7-6
3-4-7-8
No. 4
3-4-1-0-15
3-4-1-0-17
3-4-1-0-3 Found a closed body A
3-4-1-14-15
3-4-1-14-?
3-4-1-14-13
3-4-1-2-13
3-4-1-2-11
3-4-1-2-5
3-4-5-2-1
3-4-5-2-13
3-4-5-2-11
3-4-5-2-5
3-4-5-10-11
3-4-5-10-?
3-4-5-10-9
3-4-5-8-9
3-4-5-8-7
3-4-7-6-3 Found a closed body C
3-4-7-6-19
3-4-7-8-5
3-4-7-8-9
My idea was to search for triangles and quads only because your drawing only contains triangles and quads and because it is common to form shells from triangles an quads.
I would not search for loops that contain more than four points!
So neither 3-4-5-2-1-0 nor 3-4-5-2-1-0-3 is a "valid" loop. I would check 3-4-5-2 and discard it, because 2 isn't connected to 3.
If you expect faces with more than 4 edges the algorithm becomes much more complex. In this case you have to "walk along" all possible paths and remember which points you have already visited. You will find a bunch of long loops that can be split into shorter loops like (3,4,5,2,1,0) => (3,4,1,0)+(4,5,2,1). These long loops must be sorted out.
Hm. Really? It's quite challenging to find an effective algorithm for this.
I already wrote one basic idea above: Walk along all possible paths and remember which points you have already visited. If you come to a point that you visited before you found a loop. Store all loops. You will find a bunch of long loops that can be split into shorter loops like (3,4,5,2,1,0) => (3,4,1,0)+(4,5,2,1). These long loops must be sorted out. Analyse the remaining short loops and look for single connections. These are the border lines.
If you find loops with 4 and more points the points may not be in the same plane and/or the face might be concave.
What is this?
- If all four points 0,1,2 and 3 are within the same plane you have a triangle (0,1,2) and a concave quad (0,1,3,2).
In this case (1,2,3) is the outer border. - Otherwise you have two triangles (0,1,2) and (1,2,3).
In this case (1,3,2,0) is the outer border.
Now imagine loops with 5, 6, ... points.
Maybe it makes sense to look for points within (nearly?) the same plane while searching for loops.
(6-7-8-9-?-?...-?-19) can be split into smaller loops. (6,7,4,3) can't. You must sort out all loops that can be split! I.e. consider (6,7,8,9,10,5,4,3,18,19). It includes the connected points (6,3), (7,4) and (5,8). So it can be split at these three connections in three steps:
- split at (6,3): (6,7,8,9,10,5,4,3,18,19) => (6,3,18,19) + (6,7,8,9,10,5,4,3)
- split at (7,4): (6,7,8,9,10,5,4,3) => (6,7,4,3) + (7,8,9,10,5,4)
- split at (5,8): (7,8,9,10,5,4)=(5,4,7,8,9,10) => (5,8,9,10) + (5,4,7,8)
Result: (6,3,18,19) + (6,7,4,3) + (5,8,9,10).
This includes (6,7) only once.
In MyGroupMyCommand1 () you use a function deletePoint(dat3, 1e-7). Can you post the code?
Comments in the code would be extremely helpful to show which results you expect and where things don't work as expected.
At first glance I only see that some for loops use wrong ranges. i.e.:
map<int, AcGePoint3d> dats;
for (int i = 1; i < dat4.length()+1; i++)
dats.insert(pair<int, AcGePoint3d>(i, dat4.at(i - 1)));
for (int i = 1; i < dats.size(); i++)
// will only iterate over dats.size()-1 entries
It makes more sense to use the AcGePoint3dArray dat4 directly instead of a map. Simply use the array-index as point index! Note: Usually a map is filled like this:
dats[i] = dat4[i-1]; // will create an entry at key i
To understand the code better I have renamed some variables and made some changes. You find my code in the attached zip. Basically you have to code an algorithm that "walks along" all possible paths using connectedPointsIndices and finds all the shortest possible closed loops. This isn't trivial - and it's your job. Good luck!
