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.)

Mensuration

So you have a complex polygon and you want to reduce it to its outer boundary? E.g. if you put a pentagram in you'd put five segments in and get ten segments out, describing the outline? – Anacoluthia

No. See the edit I made with the attached example. – Mensuration

Got it. It'd be the outline of every point that is fully surrounded by edges? Willl the edges definitely be a subset of the originals? Can you guarantee no intersecting segments? – Anacoluthia

Yes, and yes. For the specific application those are both true. – Mensuration

Is your drawing available in vectorized or raster form ? – Wrongheaded

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).

Somniloquy

Answer 2

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.

Amabelle

Answer 3

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.

Chauffeur

The image added to the question suggests the polygon is triangulated, but the description does not make such guarantee. – Somniloquy