Need a programming algorithm for a tight enclosure around line segments

Question

I have a list of perhaps hundreds of unsorted 2D line segments at random angles as shown in blue above, and I need to determine the sorted sequence of points a – i from them as shown in red. Here are some constraints and observations:

• The red polyline sequence a - i forms a tight enclosure of the outer points of all the segments. It's like a convex hull, but "sucked" into concavities. A tight enclosure of the entirety of all segments would be a fine solution; I can delete the unused parts.
• An enclosure does exist. The segments are not completely random.
• The y value of one point of each segment is 0, and the other end is a point on the enclosure.
• The enclosure cannot cross any line segment or itself. This also means that all segments are on one side of the enclosure polyline.
• There will be either one or two enclosure segments connected to each enclosure point a - i.
• The points may be spaced widely differently, not as tidily as shown.
• I should be able to determine point a or i if necessary to start off the algorithm.

It seems like starting from a bounding box around all segments and shrinking it to form a tight enclosure would be a reasonable approach, but I can't come up with a decent algorithm. This will eventually be coded in C#, but an algorithm or pseudo-code would be fine.

Answer 1

History: this answer is now marked community wiki. The original conjecture was proven wrong by @dont talk just code. @Matt Timmermans provided the current conjecture in a comment under the question.

---

The following conjecture is submitted without proof: To compare the order of two line segments, compare the bottom x, and return the opposite if the segments cross.

If the conjecture holds, a comparator can be written for use with any comparison sort. Pseudocode for the comparator:

compare(segment A, segment B)
   if A crosses B
      return B.bottom.x - A.bottom.x
   else
      return A.bottom.x - B.bottom.x

In the event that two line segments have the same bottom.x, their order can be determined by comparing the angles that they make with the x-axis, e.g.

The segment with the larger angle is first. The atan2 function can be used to compute the angles.

---

Note that the conjecture definitely does not hold for all possible arrangements. The line segments must be constrained so that a solution exists. Here's an example where a solution does not exist (because C cannot be connected to A or B without crossing a blue line):

A and B cross, so reversing the x comparison, A is before B. C doesn't cross A or B, so comparing the x values at the bottom, B is before C and C is before A. This creates a rock-paper-scissors situation: A before B, B before C, and C before A. Such intransitive comparisons will cause a comparison sort to fail miserably.