Efficient Line Segment Intersection Algorithm
CS 113: Data Structures and
Algorithms
Abhiram G. Ranade
Line Segment Intersection
Line segment intersection problem
Input: n line segments in the plane.
Output: Do any two intersect?
•
Naive algorithm: For all i,j: check if segment i
intersects with segment j.
–
O(n
2
) time.
•
Can be done in O(nlog n) time by using
–
Creative use of balanced search trees
–
“Line sweep” technique
Important operations on Sets
implemented as search trees
#include <set>
set<int> myset; //balanced search tree
// but no explicit mention of nodes.
// will work on any domain having operator <
myset.insert(20);
myset.insert(30);
myset.insert(40);
auto it = myset.find(30);
// it “points to” node having 30
cout << *prev(it) << *it << *next(it);
// prev(it) ”points to” previous to it
// next(it)
// prints 203040
myset.erase(prev(it));
// deletes node having 20
About algorithm design
Try 1 dimensional case.
•
Line segments lie in the plane.
•
Algorithm for determining intersection:
–
Sort all endpoints.
–
If right endpoint of any segment does not immediately
succeed the left endpoint in the sorted order – declare
“Intersection!”
Key idea: we dont explicitly compare every segment with
every other.
•
If segment 1 is to left of 2 which is to the left of 3, then
we never have to compare 1 and 3.
Can we do something like this in the plane?
Line segment intersection: 2d case
•
“Sweep” a horizontal line L from top to bottom.
•
Let S = segments intersected by L as it moves.
–
Segments will enter and leave S
–
Maintain segments in S in left to right order of their
intersection with L
•
Check for intersection between segments i,j only if i,j
are adjacent in left to right order at some time while
sweeping.
Observation
: If segments i,j intersect at (x,y), then i,j will
be adjacent in S when L is just above (x,y).
Observation
: Many i,j will never be adjacent: we do not
perform intersection calculation for them.
Saving
!
Algorithm
1.
Points[0..2n-1] = Segment endpoints sorted by y coordinate.
2.
Ordered_Set S = empty;
3.
For i=0 to 2n-1
4.
If Points[i] = Points[i].segment.top // if Points[i] is top endpoint of its segment
5.
S.Insert(Points[i].segment)
6.
If Points[i].segment intersects S.prev(Points[i].segment) return true
7.
// segment previous to Points[i] in S
8.
if Points[i].segment intersects S.next(Points[i].segment) return true
9.
else // if Points[i] is bottom endpoint of its segment
10.
if S.prev(Points[i].segment) intersects S.next(Points[i].segment)
11.
return true
12.
S.Remove(Points[i].segment)
13.
End for
14.
Return false
Key Fact
•
Suppose we are sweeping L, and segment s
1
intersects L to the left of segment s
2
.
•
As L moves, s
1
will continue to intersect it to the
left of s
2
, unless s
1
and s
2
first intersect.
•
But for s
1
to intersect s
2
they will have to first
become adjacent on L.
•
At this point the an intersection check is made,
and the algorithm will stop.
•
Once a segment s
1
is deemed to be to the left of
segment s
2
on L and thus placed in S, their
relative order will not change.
Implementation of S
Operations needed
:
•
Insert a segment
•
Find
•
Get next and previous to current as per left to right
order
•
Delete
Key idea
•
S is implemented as STL set.
•
Must define < operator so that next and previous will
refer to next and previous segments intersecting L in x
coordinate order.
The comparison operator on segments
•
PQ, RT: segments to compare.
•
Assume P, R : top endpoints of PQ, RT
•
Assume P.top.y > R.top.y
•
P’, R’=R : points where PQ, RT intersect L
•
Ordering relation: PQ < RT == P’.x < R.x
P’.x < R.x iff PR is counterclockwise to PQ
PQ < RT = whether PQ x PR is positive.
cross-product = determinant
= (Q.x– P.x)(R.y – P.y) – (R.x – P.x)(Q.y – P.y)
If R.top.y > P.top.y: check if RP is counterclockwise to RT
Time analysis
•
Line 1 : O(nlogn)
•
Each statement in loop takes constant time
except for the set operations on Sweep, which
take O(log n) time
•
Loop has O(n) iterations.
•
So total time = O(nlog n)
This content discusses the Line Segment Intersection problem and presents an efficient algorithm using the line sweep technique. The algorithm utilizes ordered sets implemented as balanced search trees to efficiently determine if any two line segments intersect in the plane. By sorting endpoints and sweeping a horizontal line, unnecessary comparisons between segments are avoided, resulting in an effective solution with a time complexity of O(n log n). Key ideas and observations are highlighted throughout the discussion.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS 113: Data Structures and Algorithms Abhiram G. Ranade Line Segment Intersection
Line segment intersection problem Input: n line segments in the plane. Output: Do any two intersect? Naive algorithm: For all i,j: check if segment i intersects with segment j. O(n2) time. Can be done in O(nlog n) time by using Creative use of balanced search trees Line sweep technique
Important operations on Sets implemented as search trees #include <set> set<int> myset; //balanced search tree // but no explicit mention of nodes. // will work on any domain having operator < myset.insert(20); myset.insert(30); myset.insert(40); auto it = myset.find(30); // it points to node having 30 cout << *prev(it) << *it << *next(it); // prev(it) points to previous to it // next(it) // prints 203040 myset.erase(prev(it)); // deletes node having 20
About algorithm design Try 1 dimensional case. Line segments lie in the plane. Algorithm for determining intersection: Sort all endpoints. If right endpoint of any segment does not immediately succeed the left endpoint in the sorted order declare Intersection! Key idea: we dont explicitly compare every segment with every other. If segment 1 is to left of 2 which is to the left of 3, then we never have to compare 1 and 3. Can we do something like this in the plane?
Line segment intersection: 2d case Sweep a horizontal line L from top to bottom. Let S = segments intersected by L as it moves. Segments will enter and leave S Maintain segments in S in left to right order of their intersection with L Check for intersection between segments i,j only if i,j are adjacent in left to right order at some time while sweeping. Observation: If segments i,j intersect at (x,y), then i,j will be adjacent in S when L is just above (x,y). Observation: Many i,j will never be adjacent: we do not perform intersection calculation for them. Saving!
Algorithm 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Points[0..2n-1] = Segment endpoints sorted by y coordinate. Ordered_Set S = empty; For i=0 to 2n-1 If Points[i] = Points[i].segment.top // if Points[i] is top endpoint of its segment S.Insert(Points[i].segment) If Points[i].segment intersects S.prev(Points[i].segment) return true // segment previous to Points[i] in S if Points[i].segment intersects S.next(Points[i].segment) return true else // if Points[i] is bottom endpoint of its segment if S.prev(Points[i].segment) intersects S.next(Points[i].segment) return true S.Remove(Points[i].segment) End for Return false
Key Fact Suppose we are sweeping L, and segment s1 intersects L to the left of segment s2. As L moves, s1will continue to intersect it to the left of s2, unless s1and s2first intersect. But for s1to intersect s2they will have to first become adjacent on L. At this point the an intersection check is made, and the algorithm will stop. Once a segment s1is deemed to be to the left of segment s2on L and thus placed in S, their relative order will not change.
Implementation of S Operations needed: Insert a segment Find Get next and previous to current as per left to right order Delete Key idea S is implemented as STL set. Must define < operator so that next and previous will refer to next and previous segments intersecting L in x coordinate order.
The comparison operator on segments PQ, RT: segments to compare. Assume P, R : top endpoints of PQ, RT Assume P.top.y > R.top.y P , R =R : points where PQ, RT intersect L Ordering relation: PQ < RT == P .x < R.x P .x < R.x iff PR is counterclockwise to PQ PQ < RT = whether PQ x PR is positive. cross-product = determinant = (Q.x P.x)(R.y P.y) (R.x P.x)(Q.y P.y) If R.top.y > P.top.y: check if RP is counterclockwise to RT
Time analysis Line 1 : O(nlogn) Each statement in loop takes constant time except for the set operations on Sweep, which take O(log n) time Loop has O(n) iterations. So total time = O(nlog n)
