Outermost Polygon from a set of Edges

Question

Suppose I have a set of 2d line segments that are all connected. I need an algorithm that finds the outermost segments in the set. That is, the minimal subset that bounds the same region.

Note: this is not the same as finding the convex hull of the points making up the segments.

Edit: On the top is the initial set of segments. Below that is the same outline with interior segments deleted. (Ignore the little grey crosses, they're just to mark intersection points.)

Answer 1

How would you do that with a pencil...?

1. Find the leftmost vertex (minimum x). If there's more than one, choose the lowest of them (minimum y). There is no vertex below the current one, so take the direction 'downwards' as a reference.
2. Find all edges going from the current vertex and calculate their directions (bearings). Find the one which makes the smallest positive angle (counter-clockwise) from the reference direction. That will be the outline segment.
3. Select its other end as your new 'current' vertex and set the direction from that vertex to the recent one as a new reference direction.
4. Proceed from step 2 until you arrive to the start vertex.
5. Remove all unvisited segments.
6. Remove all orphaned vertices (if any appeared in step 5).

Answer 2

Given a triangulated non-convex polygon you can specify the direction of vertices traversal (clockwise of CCW). Make all the triangles to be similarly oriented WRT traversal of its vertices. Do decompose all the triangles into directed edges. Every edge for every triangle is the tuple of two vertices (a, b). For each neighbouring triangles you have two contradirectional edges (a, b) and (b, a). You can simply exclude such a pairs of edges from further consideration. Finally you will obtain a set of exclusively outer edges.

There is no loss of generality if your polygon consists of non-simplicial parts (but still you can specify the direction of vertices traversal).

Triangulation of the source segments-constructed polygon is evident step: stretching the vertices onto $d + 1$ paraboloid and triangulation, then excluding triangles, containing at least one edge that match no one source segment.

Another possible approach is slightly modified Gift wrapping algorithm.

Answer 3

The following is an approach that starts with the convex hull then works its way inward. The intuition is that you start with edges on the hull, then you fill in gaps by finding the closest point "along" the gap by following the shortest path in your edge set.

1. Compute the convex hull of your points.
2. Intersect the hull set with your edge set. This will leave you with a series of, potentially disconnected, edge paths.
3. Any point that does not have two edges (i.e., a leaf in graph terms) is connected to its closest leaf by finding the shortest path in the original edge set.
4. Any ties can be broken by a path that makes the smallest area when closed off by the hull.