IntersectionIntroduction

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,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.),r,7,r,2,r,8,r,6,r,5,r,4,r,3,r,1,Answer: (,r,1,r,3,) (,r,1,r,8,) (,r,3,r,4,) (,r,3,r,5,) (,r,4,r,5,) (,r,7,r,8,),Intersection example 2,Given two convex polygons, construct their intersection.,(Polygon,boundary and interior, intersection,all points that,are members of both polygons.),A,B,A,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 theirintersections.,Construction problem,Given a data set of,N,geometric objects, construct a new object,which is their intersection.,Intersection,Introduction,Applications,Domain:GraphicsProblem:Hidden-line and hidden surface removalApproach:Intersection of two polygonsType:Construction,Domain:Pattern recognitionProblem:Finding a linear classifier between two sets of pointsApproach:Intersection of convex hullsType:Test,Domain:VLSI designProblem:Component overlap detectionApproach:Intersection of rectanglesType:Pairwise,Intersection,Introduction,Problem definition,Given,N,line segments in the plane, report all their points of,intersection (pairwise).,LINE SEGMENT INTERSECTION (LSI).,INSTANCE: Set,S,= ,s,1,s,2, .,s,N, of line segments in the plane.,For 1,i,N,s,i,= (,e,i1,e,i2,) (endpoints of the segments),and for 1,j,2,e,ij,= (,x,ij,y,ij,) (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,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,(,N,2,); there are,N,(,N,- 1) / 2,O,(,N,2,) 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,s,1,is above segment,s,2,at,x, written,s,1,x,s,2,if,s,1,and,s,2,are comparable at,x,and the,y,-coordinate of the,intersection of,s,1,with the vertical line through,x,is greater,than the,y,-coordinate of the intersection of,s,2,with that line.,u,v,s,4,s,2,s,1,s,3,In the example,s,2,u,s,4,s,1,v,s,2,s,2,v,s,4, and,s,1,v,s,4,.,Segment,s,3,is not comparable with any other segment.,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,s,1,and,s,2,is encountered.,Segments,s,1,and,s,2, exchange places in the ordering.,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Crucial observation: For two segments,s,1,and,s,2,to intersect,there must be some,x,for which,s,1,and,s,2,are consecutivein 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,s,1,s,2,Algorithm idea,x,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 setof 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) canperform 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 currentlycomparable 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) canperform all of these operations in,O,(log,N,) time.,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Algorithm,1procedure LineSegmentIntersection(,S,),2begin,3Sort the 2,N,endpoints of,S,lexicographcially by,x,and,y,and load them into,E,;,4,A,=,; /* A is an internal working queue. */5while (,E,) do,6begin7,p,= MIN(,E,);8if(,p,is a left endpoint) then9begin10,s,= segment of which,p,is endpoint;,11INSERT(,s,L,);,12,s,1,= ABOVE(,s,L,);13,s,2,= BELOW(,s,L,):,14if(,s,1,intersects,s,) then add (,s,1,s,) to,A,;15if(,s,2,intersects,s,) then add (,s,2,s,) to,A,;16end17else if (,p,is a right endpoint) then18begin19,s,= segment of which,p,is endpoint;,20,s,1,= ABOVE(,s,L,);21,s,2,= BELOW(,s,L,):,22if(,s,1,intersects,s,2,to the right of,p,) then add (,s,1,s,2,) to,A,;23DELETE(,s,L,);24end25else /*,p,is an intersection */26begin27,s,1,s,2,= segments that intersect at,p, with,s,1,above,s,2,to the left of,p,.28,s,3,= ABOVE(,s,1,L,);29,s,4,= BELOW(,s,2,L,):,30if(,s,3,intersects,s,2,) then add (,s,3,s,2,) to,A,;,31if(,s,1,intersects,s,4,) then add (,s,1,s,4,) to,A,;,32Interchange,s,1,and,s,2,in,L,;33end,Algorithm continued on next page.,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Algorithm, 2,34/* The detected intersections must now be processed */35while (,A,) do36begin,37(,s,1,s,2,) = get and remove first element of,A,;,38,x,=,x,-coordinate of intersection point of,s,1,and,s,2,;,39if(MEMBER(,x,E,) = FALSE) then40begin41report (,s,1,s,2,);42INSERT(,x,E,);43end44end,45end46end,The “while (,A,) do” block (lines 35-44) is within the “while (,E,) do”begin-end block (lines 5-45).,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Problems with the Shamos-Hoey algorithm, as given in Preparata,Cases excluded by assumption:,1.Vertical segments.,2.Three (or more) segments intersecting at a single point.,Cases not handled:,1.Multiple intersections at same abscissa (fails at line 39).2.Intersection and endpoint at same abscissa (fails at line 39).,3.Segments that intersect at endpoints (special case of 2,pointed out by Franceschini).4.Segments that intersect at 1 point (i.e. collinear overlap).5.Event type (left endpoint, right endpoint, intersection) istested by the algorithm (lines 8 and 17) but never stored in,E,.,1,2,3,4,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Analysis,Preprocessing:,O,(,N,log,N,); sort of endpoints.Query:,O,(,N,+,K,) log,N,); each of 2,N,endpoints and,K,intersections,are inserted into,E, an,O,(log,N,) operation.Storage:,O,(,N,+,K,); at most 2,N,endpoints and,K,intersections arestored in,E,.,Comments,Here “query” refers to the process of finding intersections;,this is a single-shot problem.,Query time of,O,(,N,+,K,) log,N,) is suboptimum.,An optimum,O,(,N,log,N,+,K,) algorithm exists, but is quite difficult.,Laszlo (1996) still presents the Shamos-Hoey algorithm (1976),20 years later.,Intersection,Intersection of line segments, Shamos-Hoey algorithm,Intersection,Interval trees,Notation,The notation used here for interval trees is not consistent with eitherPreparata (pp. 359-363) or Ullman (pp. 385-393), which areunfortunately not consistent with each other.This notation is consistent with notation used earlier,for similar concepts regarding segment trees.,Definition, 1,An,interval tree,is a rooted binary tree that stores data intervals onthe real line whose endpoints are integers within a fixed scope.,It is the scope from within the endpoints are chosen that is fixed,not the data interval endpoints themselves.,The tree structure in which the intervals are stored is defined for,a scope interval ,l,r, where,l,and,r,must be consecutive multiplesof the same power of 2.For a given ,l,r, there is exactly one interval tree structure.The data intervals are stored within the fixed tree.We will assume WLOG that the data interval endpoints havebeen normalized to 1,N, and the tree has been built for scopeinterval 0, 2,k, where N + 1,2,k,.,T,(,l,r,) = Interval tree over scope interval ,l,r,.,Each node of,T,(,l,r,) is associated with a scope interval,l,r,.,Intersection,Interval trees,Definition, 2,A node,v,has these parameters:,B,(,v,)Beginning of scope interval associated with this node.,E,(,v,)End of scope interval associated with this node.,M,(,v,)Midpoint of scope interval,M,(,v,) = (,B,(,v,) +,E,(,v,) / 2,Lchild,(,v,)Left subtree =,T,(,B,(,v,),(,B,(,v,) +,E,(,v,) / 2,),Rchild,(,v,)Right subtree =,T,(,(,B,(,v,) +,E,(,v,) / 2,E,(,v,),L(v),AVL tree containing data intervals stored at,v,ordered on ascending left endpoint.,R(v),AVL tree containing data intervals stored at,v,ordered on descending right endpoint.,Lptr,(,v,)Pointer to left subchild in secondary search tree.,Rptr,(,v,)Pointer to right subchild in secondary search tree.,Status,(,v,), active, inactive = active iff,(,L,(,v,),or there are active nodes,in both subtrees (,Lchild,(,v,) and,Rchild,(,v,),B,(,v,),E,(,v,) is the scope interval associated with node,v,.,We will refer to a data interval as ,b,e,. Data intervals will bestored at the highest node where,B,(,v,) ,b,M,(,v,),e,E,(,v,).,Operations preview.,The interval tree supports interval insert, delete, and queryoperations, all in,O,(log,N,) time, as will be shown.,Query is defined as reporting overlaps between a query interval,and the data intervals stored in the tree.,Intersection,Interval trees,Example,The structure of the interval tree,T,(0,16) is shown;,0 = 0 2,4, 16 = 1 2,4,.,Each node is labeled with,B,(,v,),E,(,v,) of its scope interval.,Data intervals 0,4, 7,12, 9,10, 9,11, 1,1, 6,7, 13,15,and 1,6 are shown below the node where they would be stored.,Note that,T,(0,16) is shown here down to a level that accomodates,0 length intervals (e.g. 1,1); if such degenerate cases will not occur,the lowest level is usually not represented. To simplify the figures,that level (and interval 1,1) will be omitted hereinafter.,0,16,8,16,8,12,12,16,8,10,10,12,12,14,14,16,0,8,0,4,4,8,0,2,2,4,4,6,6,8,9,10,7,12,0,4,9,11,1,1,6,7,13,15,1,6,Intersection,Interval trees,Data trees,Each node,v,has attached two AVL trees,L,(,v,) and,R,(,v,), that hold,the intervals stored at this node, ordered by ascending left endpoint,and descending right endpoint respectively.,L,(,v,) and,R,(,v,) are shown for node 0,8 only; every node would have,similar trees.,0,16,8,16,8,12,12,16,0,8,0,4,4,8,9,10,7,12,9,11,6,7,13,15,0,4,1,6,L,1,6,0,4,R,L,(,v,) and,R,(,v,) are threaded to allow ordered scans of the data intervals,contained therein without requiring a binary search.,descending right,ascending left,Intersection,Interval trees,Secondary search tree,The active nodes of an interval tree are connected by pointers,forming a secondary binary search tree within the interval tree.,The secondary search tree allows the interval tree to be searched,without requring numerous accesses to empty nodes.,Lptr,(,v,) and,Rptr,(,v,) hold the secondary search tree pointers.,Active nodes are in the secondary search tree.,0,16,8,16,8,12,12,16,0,8,0,4,4,8,9,10,7,12,9,11,6,7,13,15,In this example, data intervals 0,4 and 1,6 are not present.,Nodes 0,16, 4,8, 8,12, and 12,16 are active because there aredata intervals stored at those nodes.,Node 8,16 is active because both of its child nodes are active.,Nodes 0,8 and 0,4 are inactive because there are no intervals,stored at those nodes and neither has two active child nodes.,Because a binary tree has one more leaf node than internal nodes,it can be shown that the number of empty active nodes is lessthan half the number of non-empty active nodes.,Intersection,Interval trees,Insertion,The interval tree,T,(,l,r,) supports insertions and deletions of,data intervals ,b,e, with endpoints,l,b,e, 2 child nodes.,The secondary search tree has depth log,N,.,The number of class A, B, or C nodes traversed in a query is,2 log,N,.,The query time complexity, neglecting class D nodes, is,O,(log,N,).,But what about class D nodes?,Intersection,Interval trees,Traversal length, 2,Close but not quite right answer:,Every data interval at a class D node overlaps the query interval.,The time to access the class D nodes can be charged to reporting,i.e. is,O,(,K,).,This is not quite right because some active class D nodes mighthave empty data interval lists; they are active because both subtreesare active.,Right answer:,A binary tree has one more leaf the non-leaf nodes.The subtrees of the class D nodes are binary trees.,More than half of the class D nodes have non-empty interval lists.,The time to access the class D nodes, bo