# Find a boundary from set of 3d line segments

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

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.

• tahnks. how hash can be used? Jul 26, 2020 at 21:42
• See here for how grids help: sarielhp.org/book/chapters/min_disk.pdf Jul 27, 2020 at 22:57