neighbor searching algorithm

Question

I have a STL file that contains the coordinates (x,y,z) of 3 points (p0, p1, p2) of a triangle. these triangle represent a 3D surface f(x,y,z). The STL file might have over a 1000 triangles to represent a complex geometry.

for my application, I need to know the neighboring triangles for each triangle entry from the stl file. meaning that for each triangle, i have to pick 3 pairs of points pair1=(p0,p1), pair2=(p0,p2), pair3= (p1,p2) and compare them with pair of points in other triangles in the set

what's the best and most efficient algorithm to achieve this purpose? can i use a hashtree, hashmap?

Answer 1

change the mesh representation to point table and triangle faces table. STL demands that all triangles are joined in their vertexes so no cutting of edges which means neighboring triangle always share one complete edge.

double pnt[points][3];
int    tri[triangles][3];

The pnt should be list of all distinct points (index sort it to improve speed for high point count). The tri should contain 3 indexes of points used in triangle. Sort them (asc or desc) to improve match speed.

Now if any triangle tri[i] shares the same edge like tri[j] then those two are neighboring triangles.

if ((tri[i][0]==tri[j][0])&&(tri[i][1]==tri[j][1])
  ||(tri[i][0]==tri[j][1])&&(tri[i][1]==tri[j][2])) triangles i,j are neighbors

Add all combinations ...

If you need just neighboring points then find all triangles containing that points and all the other points used in those triangles are neighbors

To load STL to such structure do this:

1. clear pnt[],tri[] lists/tables

2. process each triangle of STL

3. for each point of triangle

   look if it is in pnt[] if yes use its index for new triangle. if not add new point to pnt and use its index for new triangle. When all 3 points done add new triangle to tri.

Improving pnt[] performance

Add index sort for pnt[] sorted by any coordinate for example x and improve performance of checking if point is already present in pnt.

So while adding (xi,yi,zi) into pnt[] find index of point that have the biggest x which is xi>=pnt[i0][0] via binary search and then scan all points in pnt until x crosses xi so xi<pnt[i1][0] this way you do not need to check all points.

If this is too slow (usually if number of points is bigger then 40000) you can improve performance more by segment index sorting (dividing index sort into segment pages of finite size like 8192 points)

Improving tri[] performance

You can also sort the tri[] by tri[i][0] so you can use binary search similarly to pnt[].

Answer 2

I would suggest going with hashmap where values are sets (based on tree) of references to Tringles, keys are those pairs of Points (lets call these pairs simply Sides) and some hashing function that would take into accout the property that hash of Side (a,b) should be equal to hash of (b,a).

Some kind of algorithm:

1. Read 3 Points and create from them 3 Sides and Triangle.
2. Add all that to hashmap: map[side[i]].insert(tringle)
3. Repeat 1-2 until you read all the data

Now you have a map with filled data. About the complexity of filling: insertion into hashmap are constant-time at average (it also depends on the hash-function) and insertion complexity into a set is logarithmic so the complete complexity of filleng data is O(n*logm) where n is the number of Sides and m is average number of Tringles with the same Side.

Normally each set would contain around 4 Triangles: 1 + 3 side-neighbours, so logm is relatively small (comparing to n) and could be not taken into account (suppose it is a constant). These suggestions lead us to some kind of conclusion: best-case complexity for filling is O(n) (no collisions, no rehashing, etc) and worst is O(n*logn) (worst-case inserting of n Sides by 1 average case in map and by logn case inserting into one set meaning all Tringles share the same Side).

Now to get all side-neighbours for some Triangle:

1. Get all 3 sets for each Side of that Triangle (e.g. set[i] = map[triangle.sides[i]].
2. Get intersection of those 3 sets (exclude triangle to get only its side-neighbours).
3. Done.

About complexity of getting side-neighbours: linearly-depent on the size of the sets and relatively small comparing to 'n' in normal case.

Note: To get not side-neighbours but point-neighbours (assuming neighbours are called any 2 Triangles with common Point not Side) simply fill sets with Points instead of Sides. The above assumptions about time-complexities hold exept for constants.