0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.