Line crossing

Question

I have several line segments. And the lines are random. I have to check for intersection between two lines. Lines can be connected or not. What would be the best algorithm for this problem.

Sample code is much appreciated.

Edit: line segments

Answer 1

Assuming you are talking about line segments here (otherwise just compare the slopes of the lines: if they have unequal slopes, they intersect).

To find out if there is [one] intersection in a set of two or more line segments, you can use the Chamos-Hoi algorithm.

To find all the intersections in a set of two or more line segments, you can use the Bentley-Ottman algorithm.

Implementation of two and other “scan-based” algorithms is available in abundance on the Internet .