<p>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.</p>
<p>One can improve the running time to linear using hashing and the floor function, etc.</p>

CC BY-SA 4.0
2020-07-26T21:42:00.153Z
tahnks. how hash can be used?
YAKOVM
CC BY-SA 4.0
2020-07-27T22:57:06.733Z
See here for how grids help: https://sarielhp.org/book/chapters/min_disk.pdf
Sariel Har-Peled
CC BY-SA 4.0
2020-07-26T02:48:54.557Z
2020-07-26T02:48:54.557Z
Sariel Har-Peled
<p>I have a set of <code>n</code> <code>3d</code> line segments  <code>[(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)]</code>.
(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 :  <code>[pj_start,pj_end, ...p1_start, p1_end.....]</code>
(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 <code>s = (pm_start, pm_end)</code>,
among all other segment find the one , which distance to <code>pm_start</code> or  <code>pm_end</code> 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</p>

<graph-algorithms><computational-geometry>
Find a boundary from set of 3d line segments
YAKOVM
# Find a boundary from set of 3d line segments

(Asked by: username_0 on 2020-07-21)

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

**Tags:** graph-algorithms, computational-geometry

---

## 1 answers

### Answer by username_1 on 2020-07-26. Score: 2

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.

> **Comments:**
> **username_0**: tahnks. how hash can be used?  
> **username_1**: See here for how grids help: https://sarielhp.org/book/chapters/min_disk.pdf  

---

