Find a boundary from set of 3d line segments

Question

I have a set of n 3d line segments  [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].
(I believe that they shod be nin-intersecting...)
These segments represent a (closed) boundary.  I am looking for effective algorithm to generate this boundary, i.e. to find the order of segments for boundary :  [pj_start,pj_end, ...p1_start, p1_end.....]
(segments can be connected via their ends: start to start , start to end, end to start, end to end)
I thought to start from arbitrary segment , say s = (pm_start, pm_end),
among all other segment find the one , which distance to pm_start or  pm_end is minimal, and add this segment end based on calculated minimum distance and continue this way for all segments
The complexity of this approach is not good
Can anyone propose effective algorithm for this problem

Sariel Har-Peled · Answer

For each segment extract the two endpoints (remembering which segment they came from), now sort the endpoints by (say) lexicographical ordering. Any two endpoints that are the same are now adjacent. so, scan the sorted list, attache adjacent segments that share endpoints, and then read the cycle by following the resulting list like structure among the segments.
One can improve the running time to linear using hashing and the floor function, etc.

Find a boundary from set of 3d line segments

One Answer

Add your own answers!

Ask a Question