Need a programming algorithm for a tight enclosure around line segments

user_3453633 0
Viewed 163

enter image description here

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.

algorithm
1 Answers

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.

enter image description here

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

enter image description here

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.

user_33861090
Related