CODEWITHSUNDEEP
algorithmlinecomputational-geometryline-intersection
Darko
Darko

Reputation: 607

Efficient algorithm for minimum trace of several line segments

What is the most efficient algorithm for generating a set of line segments that represent the minimum of a group of line segments (see image)?

The resulting line segments should have following properties:

  1. Do not overlap
  2. Each segment must fall within one segment of the original set
  3. No point on any segment of the original set can fall beneath it

enter image description here

Upvotes: 0

Views: 196

Answers (1)

user1196549
user1196549

Reputation:

Seems like a good candidate for a sweepline algorithm.

Create a list of the segment endpoints and tag them with a begin/end flag as well as a reference to the segment. Sort the list by increasing abscissa.

Now scan the list from left to right, while you maintain an active list of segments. Any "begin" point creates a segment entry in the list, an "end" point discards it. At any time, the active list will contain a subset of the segments that are in overlapping configuration between the previous and current "event" points.

By interpolation, evaluate the ordinates at these endpoints and sort them vertically. This allows you to

  • detect the intersections (which correspond to re-orderings in the vertical list),
  • find the lowest ordinates.

Finally, you will have to sort the intersections from left to right and in the end you will have a list of subsegments that do not intersect and which are in a total order vertically.

Upvotes: 1

Related Questions