1

There are efficient (compared to O(n2) 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?
nradk
  • 680
  • 9
  • 19
  • 1
    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#](https://stackoverflow.com/a/18739791/2521214). **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 Mar 27 '19 at 08:08
  • 1
    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. –  Mar 27 '19 at 11:46

2 Answers2

7

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

MBo
  • 77,366
  • 5
  • 53
  • 86
1

If the lines are in general position, all pairs do intersect and exhaustive computation is optimal.