2

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?
Improve this question
2
  • 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#. 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... Commented Mar 27, 2019 at 8: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. Commented Mar 27, 2019 at 11:46

2 Answers 2

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.