Transcription
Computational Geometry[csci 3250]Line segment intersection The problem (what) Applications (why)Computational Geometry[csci 3250]Orthogonalline segment intersection Algorithms (how) A special case: Orthogonal line segments General case and Bentley-Otman line sweep algorithmLaura TomaBowdoin CollegeLaura TomaBowdoin College12Line segment intersectionLine segment intersectionProblem: Given a set of line segments in 2D, find all their pairwise intersections.3Line segment intersectionProblem: Given a set of line segments in 2D, find all their pairwise intersections.Problem: Given a set of line segments in 2D, find all their pairwise intersections. 456
ApplicationsApplicationsApplicationsGraphics: rendering hidden surfaces intersectionsMotion planning and collision detection in autonomous systems/roboticsGeographical data: River networks, road networks, railways, cal data: River networks, road networks, railways, .Map overlay in GISMap overlay in GISfrom: ture2/fig9-30 raster overlay.gif1011from: ture2/fig9-30 raster overlay.gif12
NotationNaive n: size of the input (number of segments) k: size of output (number of intersections)A special case: Orthogonal line segment intersectionProblem: Given a set of n line segments in 2D, find all their pairwise intersections.AlgorithmsExercises: Give upper and lower bounds for k, draw examples that achieve these bounds. Give a straightforward algorithm that computes all intersections and analyze itsrunning time. Give scenarios when this algorithm is efficient/inefficient. What is your intuition of an upper bound for this problem? (how fast would youhope to be able to solve it?)13Binary Search Trees (BST)Operations 16Come up with a straightforward algorithm and analyze its time Improved algorithm?14 Balanced Binary Search Trees- review -Exercises 15Balanced Binary Search Trees (BBST) Binary search trees invariants that constrain the tree to be balanced (andthus have logarithmic height) These invariants have to be maintained when inserting and deleting (so wecan think of the tree as self-balancing) BBST variantsinsert delete search successor, predecessor traversals (in order, .) min, max17 red-black trees AVL trees B-trees (a,b) trees 18
Example: Red-Black trees Example: Red-Black treesBinary search tree, and Each node is Red or Black The children of a Red node must be Black The number of Black nodes on any path from the root to any node thatdoes not have two children must be the sameExample: Red-Black treesTheorem: A Red-Black tree of n nodes has height Theta( lg n).Theorem: After an insertion or a deletion, the RB tree invariants can be maintainedin additional O(lg n) time. This is done by performing rotations andrecoloring nodes on the path from the inserted/deleted node to the root.Note: easier to conceptualize the tree as containing explicit NULL leaves, all Blackthe number of Black nodes on any root-to-leaf path must be the same19Binary Search Trees insert delete search successor, predecessor traversals (in order, .) min, max range search (1D)211D Range SearchingOperations 201D Range Searching Given a set of values P {x1, x2, x3, xn } Given a set of values P {x1, x2, x3, xn } Pre-process it in order to answer Pre-process it in order to answerrangeSearch(a,b): return all elements in P in interval (a,b)a22b23rangeSearch(a,b): return all elements in P in interval (a,b)ab24
1D Range Searching 1D Range SearchingGiven a set of values P {x1, x2, x3, xn } Pre-process it in order to answer Given a set of values P {x1, x2, x3, xn }Given a set of values P {x1, x2, x3, xn }Pre-process it in order to answer Pre-process it in order to answerrangeSearch(a,b): return all elements in P in interval (a,b) aIf P is static bIdeas?1D Range Searching rangeSearch(a,b): return all elements in P in interval (a,b) aIf P is staticb Pre-precess: sort Range search: binary search , O( lg n k) per query25rangeSearch(a,b): return all elements in P in interval (a,b) If P is static If P is dynamic: abuse BBST26271D range searching with Binary Search Trees1D range searching with Binary Search Trees1D range searching with Binary Search TreesExample: range search(21, 53): return 21, 34, 35, 46, 51, 52Example: range search(21, 53): return 21, 34, 35, 46, 51, 52Example: range search(21, 53): return 21, 34, 35, 46, 51, 52215328215329215330
1D range searching with Binary Search TreesExample: range search(21, 53): return 21, 34, 35, 46, 51, 521D Range Searching with Red-Black TreesExample: range search(10, 16): return 11, 13, 151021 Range search (a,b): return all elements in this interval1653a3132 Range search (a,b): return all elements in this interval Can be answered in O( lg n k), where k O(n) is the size of outputb33Orthogonal line segment intersection1D range searching with Binary Search Treesa1D range searching with Binary Search Treesb343536
Orthogonal line segment intersection Orthogonal line segment intersectionLet X be the set of x-coordinates of all segmentsxstart//the “events”Orthogonal line segment intersection Let X be the set of x-coordinates of all segments Sort X and traverse the events in orderline sweep techniqueline sweep techniquesolve the problem behind the linesolve the problem behind the line//our “events” Let X be the set of x-coordinates of all segments Sort X and traverse the events in order//our “events”xendx3738Orthogonal line segment intersection39Orthogonal line segment intersection Let X be the set of x-coordinates of all segments Sort X and traverse the events in order40Orthogonal line segment intersectionline sweep techniqueline sweep techniqueline sweep techniquesolve the problem behind the linesolve the problem behind the linesolve the problem behind the line//our “events” Let X be the set of x-coordinates of all segments Sort X and traverse the events in order41//our “events” Let X be the set of x-coordinates of all segments Sort X and traverse the events in order42//our “events”
Orthogonal line segment intersectionOrthogonal line segment intersectionOrthogonal line segment intersectionLine sweep techniqueline sweep technique Events Traverse events in order and maintain anActive Structure (AS) solve the problem behind the lineEventsEventsbeginning of a horizontal segmentbeginning of a horizontal segmentend of a horizontal segmentend of a horizontal segmentvertical segmentvertical segment43Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X at certain events, insert in AS at certain events, delete from ASif x is start of horizontal segment (x, x’, y)://segment becomes activeinsert segment (x,x’,y) in AS if x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x)://segment stops being activedelete segment (x,x’,y) from ASat other events, query ASAS ?in order to do this efficiently//All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections44Orthogonal line segment intersectionLet X be the set of x-coordinates of all segments//the events AS contains objects that are“active” (started but not ended) inother words they are intersected by thepresent sweep line 45Orthogonal line segment intersectionOrthogonal line segment intersection Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Initialize AS {} Initialize AS {} Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X AS ?in order to do this efficientlyif x is start of horizontal segment (x, x’, y): //segment becomes active//segment becomes activeinsert segment (x,x’,y) in ASinsert segment (x,x’,y) in ASif x is end of horizontal segment (x, x’, y): //segment stops being activedelete segment (x,x’,y) from ASdelete segment (x,x’,y) from ASif x corresponds to a vertical segment (y, y’,x): AS ?in order to do this efficientlyinsert segment (x,x’,y) in AS if x is end of horizontal segment (x, x’, y)://segment stops being activedelete segment (x,x’,y) from AS AS ?in order to do this efficientlyif x corresponds to a vertical segment (y, y’,x)://All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections47if x is start of horizontal segment (x, x’, y)://segment becomes activeif x corresponds to a vertical segment (y, y’,x)://All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections if x is end of horizontal segment (x, x’, y)://segment stops being active//All active segments start before x and endafter x. We need those whose y is in [y,y’]46if x is start of horizontal segment (x, x’, y):search AS for all segments with y-value ingiven range [y,y’] and report intersections48
Orthogonal line segment intersectionOrthogonal line segment intersectionOrthogonal line segment intersection Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Initialize AS {} Initialize AS {} Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X if x is start of horizontal segment (x, x’, y): //segment becomes activeif x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x):if x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x)://All active segments start before x and endafter x. We need those whose y is in [y,y’]insert segment (x,x’,y) in ASif x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x)://segment stops being activedelete segment (x,x’,y) from ASAS ?in order to do this efficiently//All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersectionsdelete segment (x,x’,y) from ASAS ?in order to do this efficiently//All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections49search AS for all segments with y-value ingiven range [y,y’] and report intersections50Orthogonal line segment intersection //segment stops being activedelete segment (x,x’,y) from ASif x is start of horizontal segment (x, x’, y)://segment becomes activeinsert segment (x,x’,y) in AS //segment stops being activeAS ?in order to do this efficiently //segment becomes activeinsert segment (x,x’,y) in AS if x is start of horizontal segment (x, x’, y):51Orthogonal line segment intersectionOrthogonal line segment intersection Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Initialize AS {} Initialize AS {} Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X AS ?in order to do this efficientlyif x is start of horizontal segment (x, x’, y): //segment becomes active//segment becomes activeinsert segment (x,x’,y) in ASinsert segment (x,x’,y) in ASif x is end of horizontal segment (x, x’, y): //segment stops being activedelete segment (x,x’,y) from ASdelete segment (x,x’,y) from ASif x corresponds to a vertical segment (y, y’,x): AS ?in order to do this efficientlyinsert segment (x,x’,y) in AS if x is end of horizontal segment (x, x’, y)://segment stops being activedelete segment (x,x’,y) from AS AS ?in order to do this efficientlyif x corresponds to a vertical segment (y, y’,x)://All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections53if x is start of horizontal segment (x, x’, y)://segment becomes activeif x corresponds to a vertical segment (y, y’,x)://All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections if x is end of horizontal segment (x, x’, y)://segment stops being active//All active segments start before x and endafter x. We need those whose y is in [y,y’]52if x is start of horizontal segment (x, x’, y):search AS for all segments with y-value ingiven range [y,y’] and report intersections54
Orthogonal line segment intersectionOrthogonal line segment intersectionOrthogonal line segment intersection Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Let X be the set of x-coordinates of all segments//the events Initialize AS {} Initialize AS {} Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X Sort X and traverse the events in sorted order; letx be the next event in X if x is start of horizontal segment (x, x’, y): //segment becomes activeif x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x):if x is end of horizontal segment (x, x’, y): if x corresponds to a vertical segment (y, y’,x):AS ?in order to do this efficiently//All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections56 Pick an example and simulate thealgorithm How do you implement the AS?Line sweepLet X be the set of x-coordinates of all segments//the events Initialize AS {} Sort X and traverse the events in sorted order; letx be the next event in X Frequently used technique Line can be horizontal or vertical or radial or . Traverse events in order and maintain an Active Structure (AS)if x is start of horizontal segment (x, x’, y)://segment becomes activeinsert segment (x,x’,y) in AS Analysis?if x is end of horizontal segment (x, x’, y)://segment stops being activedelete segment (x,x’,y) from AS if x corresponds to a vertical segment (y, y’,x): //All active segments start before x and endafter x. We need those whose y is in [y,y’]AS maintains objects that are “active” (started but not ended) in other words they areintersected by the present sweep line at certain events, insert in AS at certain events, delete from AS at other events, query ASsearch AS for all segments with y-value ingiven range [y,y’] and report intersections58 if x corresponds to a vertical segment (y, y’,x)://segment stops being activedelete segment (x,x’,y) from ASAS ?in order to do this efficiently//All active segments start before x and endafter x. We need those whose y is in [y,y’]search AS for all segments with y-value ingiven range [y,y’] and report intersections55 if x is end of horizontal segment (x, x’, y):delete segment (x,x’,y) from AS//All active segments start before x and endafter x. We need those whose y is in [y,y’]Orthogonal line segment intersectioninsert segment (x,x’,y) in AS //segment stops being activedelete segment (x,x’,y) from AS59if x is start of horizontal segment (x, x’, y)://segment becomes activeinsert segment (x,x’,y) in AS //segment stops being activeAS ?in order to do this efficiently //segment becomes activeinsert segment (x,x’,y) in AS if x is start of horizontal segment (x, x’, y):search AS for all segments with y-value ingiven range [y,y’] and report intersections57
Example: Red-Black trees Binary search tree, and Each node is Red or Black The children of a Red node must be Black The number of Black nodes on any path from the root to any node that does not have two children must be the same Note: easier to conceptualize the tree as containing explicit NULL leaves, all Black the number of Black nodes on any root-to-leaf path must be .
