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