Intersection Introduction Intersection example 1 Given a set of N axis parallel rectangles in the plane report all intersecting pairs Intersect share at least one point r6 r7 r5 r4 r8 r3 r1 r2 Answer r1 r3 r1 r8 r3 r4 r3 r5 r4 r5 r7 r8 Intersection Introduction Intersection example 2 Given two convex polygons construct their intersection Polygon boundary and interior intersection all points that are members of both polygons A A B B Intersection Introduction General intersection problems Test or decision problem Given two geometric objects determine if they intersect Pairwise counting or reporting problem Given a data set of N geometric objects count or report their intersections Construction problem Given a data set of N geometric objects construct a new object which is their intersection Intersection Introduction Applications Domain Graphics Problem Hidden line and hidden surface removal Approach Intersection of two polygons Type Construction Domain Problem Approach Type Pattern recognition Finding a linear classifier between two sets of points Intersection of convex hulls Test Domain Problem Approach Type VLSI design Component overlap detection Intersection of rectangles Pairwise Intersection Intersection of line segments Problem definition Given N line segments in the plane report all their points of intersection pairwise LINE SEGMENT INTERSECTION LSI INSTANCE Set S s1 s2 sN of line segments in the plane For 1 i N si ei1 ei2 endpoints of the segments and for 1 j 2 eij xij yij coordinates of the endpoints QUESTION Report all points of intersection of segments in S Note that this problem is single shot not repetitive mode Assumptions 1 No segments of S are vertical 2 No three segments meet at a point Intersection Intersection of line segments brute force algorithm Algorithm For every pair of segments in S test the two segments for intersection Segment intersection test can be done in constant time The test involves the parametric equations of the lines defined by the segments and the dot product operation See Laszlo pp 90 93 for details Analysis Preprocessing None Query O N2 there are N N 1 2 O N2 pairs each requiring a constant time test Storage O N for S Can we do better Intersection Intersection of line segments Shamos Hoey algorithm Segment ordering 1 We need some way to order segments in the plane Two segments are comparable at abscissa x iff a vertical line through x that intersects both of them Define the relation above at x as follows segment s1 is above segment s2 at x written s1 x s2 if s1 and s2 are comparable at x and the y coordinate of the intersection of s1 with the vertical line through x is greater than the y coordinate of the intersection of s2 with that line s2 s1 s3 s4 u v In the example s2 u s4 s1 v s2 s2 v s4 and s1 v s4 Segment s3 is not comparable with any other segment Intersection Intersection of line segments Shamos Hoey algorithm Segment ordering 2 Preparata defines relation x for non intersecting segments see p 281 and then applies it to segments that may intersect see p 282 Luckily this does not affect the algorithm As the vertical line sweeps the ordering changes in three ways 1 The left endpoint of a segment s is encountered Segment s must be added to the ordering 2 The right endpoint of a segment s is encountered Segment s must be removed from the ordering 3 An intersection point of two segments s1 and s2 is encountered Segments s1 and s2 exchange places in the ordering Intersection Intersection of line segments Shamos Hoey algorithm Algorithm idea s1 s2 x Crucial observation For two segments s1 and s2 to intersect there must be some x for which s1 and s2 are consecutive in the x ordering This suggests that the sequence of intersections of the segments with the vertical line contains the information needed to find the intersections between the segments That suggests a plane sweep algorithm Plane sweep algorithms often use two data structures 1 Sweep line status 2 Event point schedule Intersection Intersection of line segments Shamos Hoey algorithm Sweep line status The sweep line status is a list of the currently comparable segments ordered by the relation x The sweep line status data structure L is used to store the ordering of the currently comparable segments Because the set of currently comparable segments changes the data structure for L must support these operations 1 INSERT s L Insert segment s into the total order in L 2 DELETE s L Delete segment s from L 3 ABOVE s L Return the name of the segment immediately above s in the ordering in L 4 BELOW s L Return the name of the segment immediately below s in the ordering in L The dictionary data structure see Preparata pp 11 13 can perform all of these operations in O log N time or better Intersection Intersection of line segments Shamos Hoey algorithm Event point schedule As the sweep line is swept from left to right the set of the currently comparable segments and or their ordering by the relation x changes at a finite set of x values those are known as events The events for this problem are segment endpoints and segment intersections The event point schedule data structure E is used to store events prior to their processing For E the following operations are needed 1 MIN E Determine the smallest element in E based on x return it and delete it 2 INSERT x E Insert abscissa x representing an event into E 3 MEMBER x E Determine if abscissa x is a member of E The priority queue data structure see Preparata pp 11 13 can perform all of these operations in O log N time Intersection Intersection of line segments Shamos Hoey algorithm Algorithm 1 procedure LineSegmentIntersection S 2 begin 3 Sort the 2N endpoints of S lexicographcially by x and y and load them into E 4 A A is an internal working queue 5 while E do 6 begin 7 p MIN E 8 if p is a left endpoint then 9 begin 10 s segment of which p is endpoint 11 INSERT s L 12 s1 ABOVE s L 13 s2 BELOW s L 14 if s1 intersects s then add s1 s to A 15 if s2 intersects s then add s2 s to A 16 end 17 else if p is a right endpoint then 18 begin 19 s segment of which p is endpoint 20 s1 ABOVE s L 21 s2 BELOW s L 22 if s1 intersects s2 to the right of p then add s1 s2 to A 23 DELETE s L 24 end 25 else p is an intersection 26 begin 27 s1 s2 segments that intersect at p with s1 above s2 to the left of p 28 s3 ABOVE s1 L 29 s4 BELOW s2 L 30 if s3 intersects s2 then add s3 s2 to A 31 if s1 intersects s4 then add s1 s4 to A 32 Interchange s1 and s2 in L 33 end
View Full Document
Unlocking...