CODEWITHSUNDEEP
algorithmgraphics
padmalcom
padmalcom

Reputation: 1469

Splitting set of lines into intersecting segments

I have a set of lines which may intersect at certain points. Each line is constructed of at least 2 points. What I want to do is to split each line when it intersects an other line and store all lines to a list. In this result list there may not be any line intersecting an other.

Intersecting lines and resolved lines

An intersection may only occur on a line's points what makes the intersection detection trivial (just compare each point with each other). What I consider to be very challenging is to find a performant algorithm to solve this problem.

Thanks for your help!

EDIT: Lines are represented as points, e.g. A = (0,0),(10,1),(20,2),(30,3),(35,4) and B = (12,-4), (10,1), (8, 5)

Upvotes: 1

Views: 382

Answers (1)

Malcolm McLean
Malcolm McLean

Reputation: 6404

Plane sweep algorithm.

Look up a reference anywhere.

Essentially, we sweep along the x axis by, for each line segment, storing startx and endx as "events". Sort the events. Then you keep a second sorted list of "active" segments, add lines to the active list when you hit startx and removing it when you hit endx. The active list is sorted by y. So you only need a few actual intersection tests, where lines overlap in both x and y.

Upvotes: 1

Related Questions