Menu
Suppose I have n line segments in general position. How can I quickly count, for each of my n segments, how many of the other n-1 it intersects?
I can do this naively in O(n2) time. I can find all intersections using a fairly straightforward sweep line algorithm (Bentley-Ottmann) in O((n + k) log n) time, where k is the number of such intersections, and then aggregate the intersections I found into a bunch of counts.
I don't need to find the intersections, though; I just want to know how many there are. I don't see how to modify the sweep line algorithm to be faster since it needs to reorder two things in a tree for every intersection, and I can't think of any other techniques that don't suffer from the same problem.
I'm also interested in hearing how to count how many total intersections there are.
476
Naive Approach: The simplest approach to solve the given problem is to iterate over all segments and for each segment count the number of intersections by checking it with all other segments and then print the maximum among all the count of intersections obtained.
To count the intersection of sets in Python, we will use “len(set(set1) & set(set2))”. Here, ” & “ is an intersection element common to both. It will return the count as “3” because “10, 8, and 6” are common to both the sets.
Sweep Line Algorithm: We can solve this problem in O(nLogn) time using Sweep Line Algorithm.
Explanation: For the given two pairs, the line form (1, 0) to (2, 1) intersect with the line from (2, 0) to (1, 1) at point (1.5, 0.5). Hence the total count of points of intersection is 1.
Given x coordinates of N vertical lines (parallel to Y-axis) and M line segments extending from (x1, y1) to (x2, y2), the task is to find the total number of intersections of the line segments with the vertical lines. There are total of 8 intersections.
There are total of 8 intersections. Dotted lines are the vertical lines. A green circle denote a single point of intersection and a green triangle denotes that two line segments
Dotted lines are the vertical lines. intersect same vertical line at that point. Recommended: Please try your approach on {IDE} first, before moving on to the solution. The simplest approach is, for each query, check if a vertical line falls between the x-coordinates of the two points.
I have a hard time believing that you can do better than Bentley Ottman in the general case. You can simplify the computation a bit if you don't care where the line segments intersect, but I don't see how you could count crossings without finding them.
In essence, Bentley Ottman is a way to simplify the search space for intersections. There are other ways, which might work for particular arrangements of line segments, but unless there is some predictable geometric relationship between your segments, you're not going to be able to better than first using some clever way of finding candidate intersections combined with an individual verification of each candidate.
Unless your problem domain has some specific features which might make provide exploitable substructure, I'd think your best bet for speed would be to adapt Bentley Ottman (or some similar sweeping algorithm) for parallel execution. (Clipping the line segments into bands is a simple one. Figuring out an optimal set of bands would be interesting, too.) Of course, that's a practical rather than an academic exercise; the parallel algorithm might well end up doing more work in total; it just exploits hardware to do the work in (a constant factor) less time.
138
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
