Is there an efficient algorithm for finding all intersections of a set of infinite lines?

Question

There are efficient (compared to O(n²) pairwise testing) algorithms for finding all intersections in a set of line segments, like the Bentley-Ottmann algorithm. However, I want to find all intersections in a set of infinite lines. When the region of interest is something finite like a rectangle, the line-segment intersection algorithms can be applied after clipping the lines. But

Is there a simpler or more efficient way than just clipping the lines and applying line-segment intersection algorithms?
Is there an efficient algorithm for all intersections over the entire plane for a set of lines?

Line segment algorithms usually exploit topology and or spatial subdivision of the space. They still are quadratic ~O((n/m)^2) but the m is number of the subdivisions making this a lot of faster. Here an example: Implementing Hoey Shamos algorithm with C#. However infinite lines can not be effectively subdivided spatially making such algorithms unusable. The only thing I can think of is compute unit direction vector of each line, sort the lines by it and ignore parallel lines. the rest is still ~O(n^2) but this will not give you much... — Spektre
The efficient algorithms for segments are at best O(N Log N + K), which can degenerate to O(N²). For infinite lines, O(N²) is unavoidable. — Yves Daoust

MBo MBo · Accepted Answer · 2019-03-27T06:19:40

In general case (not all lines are parallel) there are O(n^2) intersections, so simple loop with intersection calculation is the best approach
(there is no way to get n*(n-1)/2 points without calculations)

For the case of existence a lot of parallel lines make at first grouping lines by direction and check only intersections between lines in diffferent groups

Is there an efficient algorithm for finding all intersections of a set of infinite lines?

2 Answers