Ch.2: Line Segment Intersection
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 2.1. Line Segment Intersection 2.2. The Doubly-Connected Edge List 2.3. Computing the Overlay of Two Subdivisions 2.4. Boolean Operations 2.5. Notes and Comments
85 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Line Segment Intersection] In a geographic information system, what is a map layer, and what is an overlay?
A layer is a thematic map storing only one type of information (roads, cities, rivers, vegetation, ...); an overlay shows several layers together. Cities, rivers, railroads, and their overlay in western Canada.
[Line Segment Intersection] When two map layers are overlaid, what are the positions of special interest, for two road/river networks and for two region maps?
The intersections: for networks, intersection points (a road crossing a river); for region maps, intersections of regions. e.g. regions labelled "pine forest" in the vegetation map intersected with regions labelled "1000 to 1500 mm" in the precipitation map.
[Line Segment Intersection] Overlaying two networks (roads, rivers) stored as sets of line segments: what is the geometric problem?
Given two sets of line segments, compute all intersections between a segment from one set and a segment from the other. Curves are approximated by many small segments.
[Line Segment Intersection] For overlaying a road network with a river network, why are the segments taken to be closed (an endpoint lying on another segment counts as an intersection)?
A road/river crossing can coincide with an endpoint of a segment of a chain. Rivers consist of many small segments, and endpoint coordinates may have been rounded when the maps were digitized.
[Line Segment Intersection] The two segment sets of a network overlay are merged into one set SSS of nnn closed segments, and all intersection points among segments of SSS are reported. How are the unwanted intersections then removed?
Filter afterwards: drop each reported intersection whose two segments belong to the same set. There will be such intersections: the segments of one set form chains, and coinciding endpoints count as intersections.
[Line Segment Intersection] What does the brute-force algorithm for reporting all intersections among nnn segments cost, and in which sense is it optimal?
O(n2)\boldsymbol{O(n^2)}O(n2) ; optimal in the worst case, since when every pair intersects any algorithm needs Ω(n2)\Omega(n^2)Ω(n2) time just to report them. It tests every pair of segments. In practice most segments intersect few others, so the number of intersections is much smaller than quadratic.
[Line Segment Intersection] An algorithm whose running time depends not only on the size of the input but also on the size of the output is called output-sensitive.
For segment intersection also called intersection-sensitive, since the number of intersections determines the output size.
[Line Segment Intersection] What is the yyy -interval of a segment, and what follows when the yyy -intervals of two segments don't overlap?
Its orthogonal projection onto the yyy -axis. Disjoint yyy -intervals: the two segments cannot intersect. So only pairs with overlapping yyy -intervals need testing: pairs for which some horizontal line intersects both.
[Line Segment Intersection] In a plane sweep algorithm, what are the sweep line, its status, and the event points?
Sweep line: the line ℓ\ellℓ moved over the plane; status: the set of segments intersecting ℓ\ellℓ ; event points: the points where the status must be updated. The status changes while ℓ\ellℓ moves, but not continuously; only at event points does the algorithm actually do something.
[Line Segment Intersection] A downward sweep keeps the segments intersecting the sweep line, inserts a segment at its upper endpoint, deletes it at its lower endpoint, and tests each inserted segment against all segments currently intersecting the sweep line. Why is this not output-sensitive?
Segments can intersect the sweep line together yet be far apart horizontally, so a quadratic number of pairs is tested. Example: nnn vertical segments that all intersect the xxx -axis but not each other.
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal line ℓ\ellℓ moves downwards over the plane.What does the status hold so that the algorithm becomes output-sensitive, and which pairs are tested?
The segments intersecting ℓ\ellℓ , ordered left to right; only segments adjacent in this order are tested. A new segment is tested only against its two neighbors at its upper endpoint. Later, as ℓ\ellℓ moves down, it can get new neighbors and is tested against them.
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal sweep line ℓ\ellℓ moves downwards; the status T\mathcal{T}T holds the segments crossing ℓ\ellℓ ordered left to right, and only segments adjacent in T\mathcal{T}T are tested for intersection.What are the three types of event points?
Upper endpoints, lower endpoints, and intersection points. Endpoints are known beforehand; intersection points are computed on the fly. At an intersection the order of the two segments along ℓ\ellℓ changes.
[Line Segment Intersection] To first argue that the plane sweep for segment intersection is correct, which three degenerate cases are ignored?
Horizontal segments, overlapping segments (two segments meeting in more than one point), and three or more segments through a common point. Later they turn out to be easy to handle, except overlapping segments, which the chapter ignores throughout.
[Line Segment Intersection] Lemma 2.1 Let sis_isi and sjs_jsj be two non-horizontal segments whose interiors intersect in a single point ppp , and assume no third segment passes through ppp . Then … ?
There is an event point above ppp where sis_isi and sjs_jsj become adjacent and are tested for intersection. So adjacency-only testing finds all interior intersections. Intersections at an endpoint are found anyway when the sweep line reaches that endpoint.
[Line Segment Intersection] Lemma: if the interiors of two non-horizontal segments si,sjs_i, s_jsi,sj intersect in a single point ppp and no third segment passes through ppp , then at some event point above ppp they become adjacent on the sweep line and are tested.What is the proof?
Just above ppp they are adjacent; at the start they are not (empty status), so some event point above ppp makes them adjacent. "Just above": a horizontal line ℓ\ellℓ with no event point on ℓ\ellℓ nor between ℓ\ellℓ and the horizontal line through ppp .
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal sweep line ℓ\ellℓ moves downwards; the status T\mathcal{T}T holds the segments crossing ℓ\ellℓ ordered left to right, and only segments adjacent in T\mathcal{T}T are tested for intersection.What happens when the event point is the upper endpoint of a segment sjs_jsj ?
Insert sjs_jsj into the status and test it against its left and right neighbors; an intersection found below the sweep line becomes a new event point. Intersections above the sweep line have been detected already. sjs_jsj appears between sis_isi and sks_ksk , and is tested against both.
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal sweep line ℓ\ellℓ moves downwards; the status T\mathcal{T}T holds the segments crossing ℓ\ellℓ ordered left to right, and only segments adjacent in T\mathcal{T}T are tested for intersection.The sweep line reaches the intersection point of sks_ksk and sls_lsl , where the order along the sweep line was sj,sk,sl,sms_j, s_k, s_l, s_msj,sk,sl,sm . What happens?
sks_ksk and sls_lsl swap, then sls_lsl is tested against sjs_jsj and sks_ksk against sms_msm (each against its one new neighbor). Only intersections below the sweep line are of interest.
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal sweep line ℓ\ellℓ moves downwards; the status T\mathcal{T}T holds the segments crossing ℓ\ellℓ ordered left to right, and only segments adjacent in T\mathcal{T}T are tested for intersection.What happens when the event point is the lower endpoint of a segment sls_lsl ?
Delete sls_lsl ; its two neighbors become adjacent and are tested for intersection (below the sweep line). Removing sls_lsl makes sks_ksk and sms_msm adjacent.
[Line Segment Intersection] Plane sweep for segment intersection: a horizontal sweep line ℓ\ellℓ moves downwards; the status T\mathcal{T}T holds the segments crossing ℓ\ellℓ ordered left to right, and only segments adjacent in T\mathcal{T}T are tested for intersection.Why may an intersection found at an event have been detected already?
The two segments that just became adjacent may have been adjacent before, and were tested then.
[Line Segment Intersection] Which invariant guarantees that the plane sweep for segment intersection has found all intersection points once the last event is treated?
All intersection points above the sweep line have been computed correctly.
[Line Segment Intersection] In degenerate cases (several segments through one point), what output is required from the segment intersection algorithm?
Each intersection point once, with the list of segments that pass through it or have it as an endpoint.
[Line Segment Intersection] In the segment intersection sweep, what is the order ≺\prec≺ on the event points p,qp, qp,q in the event queue Q\mathcal{Q}Q ?
p≺q ⟺ py>qy\boldsymbol{p \prec q \iff p_y > q_y}p≺q⟺py>qy or (py=qy and px<qx)\boldsymbol{(p_y = q_y \text{ and } p_x < q_x)}(py=qy and px<qx) Higher events first; events on the same horizontal line are treated from left to right.
[Line Segment Intersection] In the segment intersection sweep, which endpoint of a horizontal segment is its upper endpoint, and how can you picture the convention?
The left endpoint is the upper endpoint (the right one is the lower). As if the sweep line were sloping just a tiny bit upward: it reaches the left endpoint just before the right one.
[Line Segment Intersection] How is the event queue Q\mathcal{Q}Q of the segment intersection sweep implemented, and what is stored with each event point ppp ?
A balanced binary search tree ordered by ≺\prec≺ ; with ppp it stores the segments whose upper endpoint is ppp . Fetching the next event and inserting an event take O(logm)O(\log m)O(logm) , where mmm is the number of events in Q\mathcal{Q}Q . Coinciding event points (e.g. two upper endpoints) are treated as one event.
[Line Segment Intersection] Why is the event queue of the segment intersection sweep not a heap?
The algorithm must test whether an event is already present in Q\mathcal{Q}Q , which a heap doesn't support efficiently. Two segments' upper endpoints can coincide, and an intersection can be found more than once.
[Line Segment Intersection] How is the status structure T\mathcal{T}T of the segment intersection sweep organized?
A balanced search tree with the segments in its leaves, left to right; each internal node stores the segment of the rightmost leaf of its left subtree. The internal nodes only guide the search.
[Line Segment Intersection] How do you find, in the status tree T\mathcal{T}T of the segment intersection sweep, the segment immediately to the left of a point ppp on the sweep line, and at what cost?
At each internal node, test whether ppp lies left or right of its segment, and descend accordingly: O(logn)\boldsymbol{O(\log n)}O(logn) . The leaf reached, or the leaf to its left, holds the answer. Every update and neighbor search in T\mathcal{T}T takes O(logn)O(\log n)O(logn) .
[Line Segment Intersection] What are the steps of FindIntersections( SSS ) for a set SSS of segments?
Put all endpoints into the event queue Q\mathcal{Q}Q , start with an empty status T\mathcal{T}T , then remove and handle the next event until Q\mathcal{Q}Q is empty. Each upper endpoint is inserted together with its segment.Output: the intersection points, each with the segments that contain it.
[Line Segment Intersection] For an event point ppp : U(p)U(p)U(p) = segments whose upper endpoint is ppp , L(p)L(p)L(p) = segments whose lower endpoint is ppp , C(p)C(p)C(p) = segments that contain ppp in their interior.When handling event point ppp , when is ppp reported as an intersection, and how are L(p)L(p)L(p) and C(p)C(p)C(p) found?
Report ppp when L(p)∪U(p)∪C(p)L(p) \cup U(p) \cup C(p)L(p)∪U(p)∪C(p) has more than one segment. L(p)L(p)L(p) and C(p)C(p)C(p) are found in T\mathcal{T}T , where they are adjacent. U(p)U(p)U(p) is stored with ppp in the event queue. Report ppp with L(p)L(p)L(p) , U(p)U(p)U(p) and C(p)C(p)C(p) .
[Line Segment Intersection] For an event point ppp : U(p)U(p)U(p) = segments whose upper endpoint is ppp , L(p)L(p)L(p) = segments whose lower endpoint is ppp , C(p)C(p)C(p) = segments that contain ppp in their interior.How does the handling of event point ppp update the status T\mathcal{T}T ?
Delete L(p)∪C(p)L(p) \cup C(p)L(p)∪C(p) , then insert U(p)∪C(p)U(p) \cup C(p)U(p)∪C(p) in the order of a sweep line just below ppp . A horizontal segment comes last among the segments containing ppp . Deleting and re-inserting C(p)C(p)C(p) reverses its order. Here U(p)={s2}U(p) = \{s_2\}U(p)={s2} , L(p)={s4,s5}L(p) = \{s_4, s_5\}L(p)={s4,s5} , C(p)={s1,s3}C(p) = \{s_1, s_3\}C(p)={s1,s3} .
[Line Segment Intersection] For an event point ppp : U(p)U(p)U(p) = segments whose upper endpoint is ppp , L(p)L(p)L(p) = segments whose lower endpoint is ppp , C(p)C(p)C(p) = segments that contain ppp in their interior.After the status is updated at ppp , which pairs are tested for new intersections if U(p)∪C(p)=∅U(p) \cup C(p) = \emptysetU(p)∪C(p)=∅ , and which otherwise?
Empty: the left and right neighbors sl,srs_l, s_rsl,sr of ppp . Otherwise: the leftmost segment of U(p)∪C(p)U(p) \cup C(p)U(p)∪C(p) with its left neighbor, and the rightmost with its right neighbor. Steps are skipped when a neighbor doesn't exist.
[Line Segment Intersection] FindNewEvent( sl,sr,ps_l, s_r, psl,sr,p ) in the segment intersection sweep: when is the intersection of sls_lsl and srs_rsr inserted into the event queue?
When it lies below the sweep line, or on it to the right of ppp , and is not yet in the queue. "On it, to the right of ppp " is needed for horizontal segments, since events at the same height are treated from left to right.
[Line Segment Intersection] How is the correctness of FindIntersections (plane sweep for segment intersection) proved?
By induction on the priority of the event points. Assuming all intersection points of higher priority are computed correctly, show that the intersection point ppp and its segments are.Priority: higher yyy first; on equal yyy , smaller xxx first.
[Line Segment Intersection] Correctness of the plane sweep for segment intersection, by induction on event priority: all intersection points qqq with higher priority than ppp are computed correctly.Why are ppp and its segments found when ppp is an endpoint of some segment?
ppp is in the event queue from the start; U(p)U(p)U(p) is stored with ppp , and L(p)L(p)L(p) , C(p)C(p)C(p) are in T\mathcal{T}T when ppp is handled.
[Line Segment Intersection] Correctness of the plane sweep for segment intersection, by induction on event priority: all intersection points qqq with higher priority than ppp are computed correctly.Why is ppp inserted into the event queue when ppp lies in the interior of all its segments?
Two segments neighboring in angular order around ppp become adjacent at an event of higher priority, which detects ppp . As in the proof that two segments meeting at an interior point become adjacent above it.
[Line Segment Intersection] Lemma 2.3 The running time of FindIntersections (plane sweep) for a set SSS of nnn segments in the plane with III intersection points is … ?
O(nlogn+Ilogn)\boldsymbol{O(n \log n + I \log n)}O(nlogn+Ilogn)
[Line Segment Intersection] Why is the bound O((n+I)logn)O((n + I) \log n)O((n+I)logn) for segment intersection, with III the number of intersection points, stronger than O((n+k)logn)O((n + k) \log n)O((n+k)logn) , with kkk the output size?
One intersection point can contribute many segments to the output, so kkk can be much larger than III . e.g. many segments through a common point.
[Line Segment Intersection] For an event point ppp : U(p)U(p)U(p) = segments whose upper endpoint is ppp , L(p)L(p)L(p) = segments whose lower endpoint is ppp , C(p)C(p)C(p) = segments that contain ppp in their interior.Why does the plane sweep for segment intersection run in O(mlogn)O(m \log n)O(mlogn) , with mmm the sum over all events ppp of m(p)=∣L(p)∪U(p)∪C(p)∣m(p) = |L(p) \cup U(p) \cup C(p)|m(p)=∣L(p)∪U(p)∪C(p)∣ ?
Each event costs O(logn)O(\log n)O(logn) per segment involved: a constant number of event-queue operations, and O(m(p))O(m(p))O(m(p)) operations on T\mathcal{T}T . Building the event queue takes O(nlogn)O(n \log n)O(nlogn) . Each event causes at most two new insertions into Q\mathcal{Q}Q .
[Line Segment Intersection] With m(p)m(p)m(p) the number of segments involved in event ppp and m=∑pm(p)m = \sum_p m(p)m=∑pm(p) , the sweep runs in O(mlogn)O(m \log n)O(mlogn) .Why is m=O(n+I)m = O(n + I)m=O(n+I) , with III the number of intersection points?
View the segments as a planar graph (vertices: endpoints and intersections). m(p)≤degpm(p) \le \deg pm(p)≤degp , so m≤2nem \le 2n_em≤2ne , and ne=O(nv)=O(n+I)n_e = O(n_v) = O(n + I)ne=O(nv)=O(n+I) . nv≤2n+In_v \le 2n + Inv≤2n+I . Euler's formula then gives ne≤6n+3I−6n_e \le 6n + 3I - 6ne≤6n+3I−6 , so m≤12n+6I−12m \le 12n + 6I - 12m≤12n+6I−12 .
[Line Segment Intersection] Euler's formula: for a planar graph with nvn_vnv vertices, nen_ene edges and nfn_fnf faces, what holds, and when with equality?
nv−ne+nf≥2\boldsymbol{n_v - n_e + n_f \ge 2}nv−ne+nf≥2 , with equality if and only if the graph is connected.
[Line Segment Intersection] In a planar graph with nen_ene edges (at least three of them), why is the number of faces nf≤2ne/3n_f \le 2n_e/3nf≤2ne/3 ?
Every face is bounded by at least three edges, and every edge bounds at most two faces.
[Line Segment Intersection] How much storage does the plane sweep for segment intersection ( nnn segments, III intersection points) use, as described first?
O(n+I)O(n + I)O(n+I) : the status T\mathcal{T}T is O(n)O(n)O(n) , but the event queue Q\mathcal{Q}Q can grow to O(n+I)O(n + I)O(n+I) . Intersection points are inserted when detected and removed only when handled. Intersections of segments that were adjacent earlier stay in Q\mathcal{Q}Q .
[Line Segment Intersection] How is the storage of the plane sweep for segment intersection reduced to O(n)O(n)O(n) , and why does it stay correct?
Store only intersection points of pairs currently adjacent on the sweep line; delete one when its pair stops being adjacent. The pair must become adjacent again before the intersection point is reached, so it is re-inserted then. Time stays O(nlogn+Ilogn)O(n \log n + I \log n)O(nlogn+Ilogn) .
[Line Segment Intersection] Theorem 2.4 Let SSS be a set of nnn line segments in the plane, with III intersection points. All intersection points, each with its segments, can be reported in … ?
O(nlogn+Ilogn)\boldsymbol{O(n \log n + I \log n)}O(nlogn+Ilogn) time and O(n)\boldsymbol{O(n)}O(n) space.
[The Doubly-Connected Edge List] Why is a map subdivided into labelled regions not stored simply as a collection of line segments?
Operations like reporting the boundary of a region would be complicated: the structure should hold topological information. Which segments bound a region, which regions are adjacent.
[The Doubly-Connected Edge List] What is a planar subdivision, and when is it connected?
The subdivision of the plane induced by a planar embedding of a graph; connected if the underlying graph is connected. Embedded nodes are vertices, embedded arcs are edges (here: straight, open segments, i.e. without their endpoints).
[The Doubly-Connected Edge List] What is a face of a planar subdivision?
A maximal connected subset of the plane that contains no point on an edge and no vertex. So a face is an open polygonal region bounded by edges and vertices of the subdivision.
[The Doubly-Connected Edge List] What is the complexity of a planar subdivision?
The number of vertices plus the number of edges plus the number of faces.
[The Doubly-Connected Edge List] Which operations should a basic representation of a planar subdivision support, and which one is too much to ask?
Supported: walk around a face, step to an adjacent face across an edge, visit the edges around a vertex. Too much: locate the face containing a point. The basic operations are local. Point location gets its own data structure in a later chapter.
[The Doubly-Connected Edge List] In a doubly-connected edge list, why is each edge split into two half-edges?
An edge usually bounds two faces; a half-edge bounds only one, so it has a unique next and previous half-edge. The two half-edges of one edge are twins.
[The Doubly-Connected Edge List] How are the half-edges of a doubly-connected edge list oriented, for an outer boundary and for the boundary of a hole?
The face a half-edge bounds always lies to its left: outer boundaries are traversed counterclockwise, hole boundaries clockwise. So twin half-edges always have opposite orientations.
[The Doubly-Connected Edge List] In a doubly-connected edge list, what does the record of a vertex vvv store?
Coordinates(v)\boldsymbol{\mathit{Coordinates}(v)}Coordinates(v) and IncidentEdge(v)\boldsymbol{\mathit{IncidentEdge}(v)}IncidentEdge(v) , a pointer to an arbitrary half-edge with origin vvv .
[The Doubly-Connected Edge List] In a doubly-connected edge list, what does the record of a face fff store?
OuterComponent(f)\boldsymbol{\mathit{OuterComponent}(f)}OuterComponent(f) : a half-edge on its outer boundary (nil for the unbounded face), and InnerComponents(f)\boldsymbol{\mathit{InnerComponents}(f)}InnerComponents(f) : one half-edge on the boundary of each hole. One pointer is not enough when fff has holes: from one half-edge you can only walk around one boundary component.
[The Doubly-Connected Edge List] In a doubly-connected edge list, what does the record of a half-edge e⃗\vec{e}e store?
Origin(e⃗)\boldsymbol{\mathit{Origin}(\vec{e})}Origin(e) , Twin(e⃗)\boldsymbol{\mathit{Twin}(\vec{e})}Twin(e) , IncidentFace(e⃗)\boldsymbol{\mathit{IncidentFace}(\vec{e})}IncidentFace(e) (the face to its left), Next(e⃗)\boldsymbol{\mathit{Next}(\vec{e})}Next(e) , Prev(e⃗)\boldsymbol{\mathit{Prev}(\vec{e})}Prev(e) .
[The Doubly-Connected Edge List] Why does a half-edge record in a doubly-connected edge list not store the destination of e⃗\vec{e}e ?
It is Origin(Twin(e⃗))\boldsymbol{\mathit{Origin}(\mathit{Twin}(\vec{e}))}Origin(Twin(e)) .
[The Doubly-Connected Edge List] In a doubly-connected edge list, which half-edge is Next(e⃗)\mathit{Next}(\vec{e})Next(e) ?
The unique half-edge on the boundary of IncidentFace(e⃗)\mathit{IncidentFace}(\vec{e})IncidentFace(e) whose origin is the destination of e⃗\vec{e}e . Likewise Prev(e⃗)\mathit{Prev}(\vec{e})Prev(e) is the one on that boundary whose destination is Origin(e⃗)\mathit{Origin}(\vec{e})Origin(e) .
[The Doubly-Connected Edge List] What is the storage of a doubly-connected edge list for a subdivision, and why?
Linear in the complexity of the subdivision. Constant per vertex and per edge. A face's InnerComponents\mathit{InnerComponents}InnerComponents list can be long, but each half-edge is pointed to from at most one such list.
[The Doubly-Connected Edge List] In a doubly-connected edge list, how do you walk around the outer boundary of a face fff ?
Start at OuterComponent(f)\boldsymbol{\mathit{OuterComponent}(f)}OuterComponent(f) and follow Next\boldsymbol{\mathit{Next}}Next pointers until you are back.
[The Doubly-Connected Edge List] In a doubly-connected edge list, how can you visit all edges incident to a vertex vvv ?
Start with e⃗=IncidentEdge(v)\boldsymbol{\vec{e} = \mathit{IncidentEdge}(v)}e=IncidentEdge(v) and repeat e⃗←Next(Twin(e⃗))\boldsymbol{\vec{e} \leftarrow \mathit{Next}(\mathit{Twin}(\vec{e}))}e←Next(Twin(e)) until back at the start. Twin(e⃗)\mathit{Twin}(\vec{e})Twin(e) ends at vvv , so its next half-edge starts at vvv again: the next edge around vvv (clockwise).
[The Doubly-Connected Edge List] In this doubly-connected edge list ( f1f_1f1 is the unbounded face), what are OuterComponent(f1)\mathit{OuterComponent}(f_1)OuterComponent(f1) and InnerComponents(f1)\mathit{InnerComponents}(f_1)InnerComponents(f1) , and which half-edges do you visit following Next\mathit{Next}Next from e⃗1,1\vec{e}_{1,1}e1,1 ?
nil and [e⃗1,1]\boldsymbol{[\vec{e}_{1,1}]}[e1,1] ; e⃗1,1,e⃗4,2,e⃗2,1,e⃗2,2,e⃗3,1\vec{e}_{1,1}, \vec{e}_{4,2}, \vec{e}_{2,1}, \vec{e}_{2,2}, \vec{e}_{3,1}e1,1,e4,2,e2,1,e2,2,e3,1 , then back to e⃗1,1\vec{e}_{1,1}e1,1 . The boundary of the hole of f1f_1f1 runs clockwise, and both half-edges of the dangling edge e2e_2e2 lie on it. OuterComponent(f2)=e⃗4,1\mathit{OuterComponent}(f_2) = \vec{e}_{4,1}OuterComponent(f2)=e4,1 .
[The Doubly-Connected Edge List] Which parts of a doubly-connected edge list can be dropped when vertices carry no attributes, or when faces have no meaning (e.g. a river network)?
No vertex attributes: store the coordinates directly in Origin()\mathit{Origin}()Origin() . Meaningless faces: drop the face records and the IncidentFace()\mathit{IncidentFace}()IncidentFace() fields.
[The Doubly-Connected Edge List] Some doubly-connected edge list implementations make the subdivision's graph connected by adding dummy edges. What are the two advantages?
A simple graph traversal visits all half-edges, and the faces need no InnerComponents()\boldsymbol{\mathit{InnerComponents}()}InnerComponents() list.
[Computing the Overlay of Two Subdivisions] What is the overlay O(S1,S2)\mathcal{O}(\mathcal{S}_1, \mathcal{S}_2)O(S1,S2) of two planar subdivisions S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 ?
The subdivision induced by the edges of both: fff is a face of O(S1,S2)\mathcal{O}(\mathcal{S}_1, \mathcal{S}_2)O(S1,S2) iff fff is a maximal connected subset of f1∩f2f_1 \cap f_2f1∩f2 for some faces f1f_1f1 of S1\mathcal{S}_1S1 , f2f_2f2 of S2\mathcal{S}_2S2 .
[Computing the Overlay of Two Subdivisions] What exactly does the map overlay problem ask for, given S1\mathcal{S}_1S1 and S2\mathcal{S}_2S2 as doubly-connected edge lists?
A doubly-connected edge list for O(S1,S2)\mathcal{O}(\mathcal{S}_1, \mathcal{S}_2)O(S1,S2) in which every face is labelled with the faces of S1\mathcal{S}_1S1 and S2\mathcal{S}_2S2 containing it. Then each region of a vegetation/precipitation overlay knows both its vegetation type and its precipitation.
[Computing the Overlay of Two Subdivisions] When computing the overlay of S1\mathcal{S}_1S1 and S2\mathcal{S}_2S2 , why can half-edge records of edges not crossed by the other map be re-used unchanged?
A half-edge's orientation doesn't change: the face it bounds may change shape but stays on its left. Only half-edges incident to an intersection between edges of different maps need new information.
[Computing the Overlay of Two Subdivisions] How does the overlay algorithm for S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 build the vertex and half-edge records of the overlay's doubly-connected edge list D\mathcal{D}D ?
Copy both edge lists into D\mathcal{D}D , run the intersection sweep on all edges, and fix D\mathcal{D}D locally at events with edges of both maps. Cross pointers link the segments in the status T\mathcal{T}T to their half-edges in D\mathcal{D}D . An event with edges of only one map needs no change: its vertex is re-used.
[Computing the Overlay of Two Subdivisions] What invariant does the overlay sweep for S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 maintain?
The part of the overlay above the sweep line has been computed correctly (vertex and half-edge records).
[Computing the Overlay of Two Subdivisions] Overlay of S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 : an edge eee of S1\mathcal{S}_1S1 passes through a vertex vvv of S2\mathcal{S}_2S2 .How is eee split, and how are the pointers at the endpoints of eee fixed?
Two new half-edges with origin vvv , twinned with the two old ones; each new one copies Next()\mathit{Next}()Next() of the old half-edge that is not its twin. So eee becomes e′e'e′ and e′′e''e′′ , each one old and one new half-edge. The old half-edges keep the endpoints of eee as origin. The half-edges those copied Next()\mathit{Next}()Next() pointers point to set their Prev()\mathit{Prev}()Prev() to the new half-edges.
[Computing the Overlay of Two Subdivisions] Overlay of S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 : an edge of S1\mathcal{S}_1S1 through a vertex vvv of S2\mathcal{S}_2S2 has been split into e′e'e′ and e′′e''e′′ .How are the pointers around vvv set?
e′e'e′ into vvv : Next\mathit{Next}Next is the first half-edge clockwise from e′e'e′ leaving vvv . e′e'e′ out of vvv : it is Next\mathit{Next}Next of the first half-edge counterclockwise into vvv . Same for e′′e''e′′ : four Next/Prev\mathit{Next}/\mathit{Prev}Next/Prev pairs in total. First e′e'e′ and e′′e''e′′ are located in the cyclic order around vvv .
[Computing the Overlay of Two Subdivisions] How long does the local update of the overlay's doubly-connected edge list take at an event point, and what does that give for the vertex and half-edge records?
O(m)\boldsymbol{O(m)}O(m) for mmm edges at the event, so all vertex and half-edge records take O(nlogn+klogn)\boldsymbol{O(n \log n + k \log n)}O(nlogn+klogn) . nnn : total complexity of S1\mathcal{S}_1S1 and S2\mathcal{S}_2S2 ; kkk : complexity of the overlay. Only locating e′,e′′e', e''e′,e′′ around vvv is not constant: linear in degv\deg vdegv . Every intersection found is a vertex of the overlay.
[Computing the Overlay of Two Subdivisions] How many face records does a subdivision's doubly-connected edge list need, in terms of boundary cycles?
The number of outer boundaries plus one (the unbounded face). Every bounded face has a unique outer boundary.
[Computing the Overlay of Two Subdivisions] How do you decide whether a boundary cycle of half-edges is an outer boundary or the boundary of a hole?
At its leftmost vertex (lowest among ties): angle inside the incident face below 180∘180^\circ180∘ means outer boundary, otherwise a hole. The incident face lies to the left of the half-edges. The test only works at the leftmost vertex.
[Computing the Overlay of Two Subdivisions] For the faces of the overlay, what are the nodes and arcs of the graph G\mathcal{G}G on boundary cycles?
Nodes: the boundary cycles, plus one for the unbounded face. Arcs: each hole cycle to the cycle immediately left of its leftmost vertex. That is the cycle of the half-edge directly left of that vertex; if there is none, the node of the unbounded face (the imaginary outer boundary). Outer boundary cycles are double circles, hole cycles single circles.
[Computing the Overlay of Two Subdivisions] Lemma 2.5 G\mathcal{G}G : a node per boundary cycle of a subdivision (plus one for the unbounded face), an arc from each hole cycle to the cycle immediately left of its leftmost vertex. Then each connected component of G\mathcal{G}G … ?
corresponds exactly to the set of cycles incident to one face.
[Computing the Overlay of Two Subdivisions] G\mathcal{G}G : a node per boundary cycle (plus one for the unbounded face), an arc from each hole cycle to the cycle immediately left of its leftmost vertex.Why does every hole cycle of a face fff end up in the component of the outer boundary of fff ?
Take the leftmost such failing hole cycle C\mathcal{C}C : its arc leads to a cycle C′\mathcal{C}'C′ further left, which is in the outer boundary's component, so C\mathcal{C}C is too. C′\mathcal{C}'C′ is the outer boundary of fff or a hole of fff whose leftmost vertex lies further left, so by the choice of C\mathcal{C}C it does not fail.And arcs only join cycles of the same face, because fff lies locally left of the leftmost vertex of a hole of fff .
[Computing the Overlay of Two Subdivisions] How is the graph G\mathcal{G}G on boundary cycles of the overlay built, and at what extra cost?
During the sweep, store at each vertex the half-edge immediately left of it; afterwards add the arcs: O(n+k)\boldsymbol{O(n + k)}O(n+k) additional time. The sweep finds the segment left of each event point anyway, to test it against the leftmost new segment. Each half-edge points to the node of its cycle.
[Computing the Overlay of Two Subdivisions] In the overlay of S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 , how are the labels of a face fff found from a vertex vvv of fff ?
v=e1∩e2v = e_1 \cap e_2v=e1∩e2 for edges of both maps: their IncidentFace()\mathit{IncidentFace}()IncidentFace() . vvv a vertex of S1\mathcal{S}_1S1 only: locate vvv in S2\mathcal{S}_2S2 by a plane sweep. The book leaves that sweep as an exercise; it can also be done in the intersection sweep itself.
[Computing the Overlay of Two Subdivisions] What are the steps of MapOverlay( S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 )?
Copy into D\mathcal{D}D ; sweep (intersections, update D\mathcal{D}D ); boundary cycles; graph G\mathcal{G}G and its components; a face record per component; labels. Per component: OuterComponent\mathit{OuterComponent}OuterComponent from its unique outer cycle, InnerComponents\mathit{InnerComponents}InnerComponents from its hole cycles, and IncidentFace\mathit{IncidentFace}IncidentFace of all their half-edges.
[Computing the Overlay of Two Subdivisions] Theorem 2.6 Let S1,S2\mathcal{S}_1, \mathcal{S}_2S1,S2 be planar subdivisions of complexities n1,n2n_1, n_2n1,n2 , and n:=n1+n2n := n_1 + n_2n:=n1+n2 . The overlay of S1\mathcal{S}_1S1 and S2\mathcal{S}_2S2 can be constructed in … ?
O(nlogn+klogn)\boldsymbol{O(n \log n + k \log n)}O(nlogn+klogn) time, with kkk the complexity of the overlay. Copying O(n)O(n)O(n) , sweep O(nlogn+klogn)O(n \log n + k \log n)O(nlogn+klogn) , face records linear in the overlay's complexity (components by depth-first search), labelling O(nlogn+klogn)O(n \log n + k \log n)O(nlogn+klogn) .
[Boolean Operations] How are P1∩P2\mathcal{P}_1 \cap \mathcal{P}_2P1∩P2 , P1∪P2\mathcal{P}_1 \cup \mathcal{P}_2P1∪P2 and P1∖P2\mathcal{P}_1 \setminus \mathcal{P}_2P1∖P2 of two polygons computed by map overlay?
Overlay the two maps whose bounded faces are labelled P1\mathcal{P}_1P1 and P2\mathcal{P}_2P2 , then extract the faces labelled with P1\mathcal{P}_1P1 and P2\mathcal{P}_2P2 / P1\mathcal{P}_1P1 or P2\mathcal{P}_2P2 / P1\mathcal{P}_1P1 and not P2\mathcal{P}_2P2 . The result need not be a polygon: it can be several polygonal regions, some with holes.
[Boolean Operations] Corollary 2.7 Let P1,P2\mathcal{P}_1, \mathcal{P}_2P1,P2 be polygons with n1,n2n_1, n_2n1,n2 vertices, n:=n1+n2n := n_1 + n_2n:=n1+n2 . Then P1∩P2\mathcal{P}_1 \cap \mathcal{P}_2P1∩P2 , P1∪P2\mathcal{P}_1 \cup \mathcal{P}_2P1∪P2 and P1∖P2\mathcal{P}_1 \setminus \mathcal{P}_2P1∖P2 can each be computed in … ?
O(nlogn+klogn)\boldsymbol{O(n \log n + k \log n)}O(nlogn+klogn) time, with kkk the complexity of the output. kkk can be the output's complexity (not the overlay's), because every intersection of an edge of P1\mathcal{P}_1P1 with one of P2\mathcal{P}_2P2 is a vertex of the result, whichever operation.
[Notes and Comments] Who gave the O(nlogn+klogn)O(n \log n + k \log n)O(nlogn+klogn) plane sweep for segment intersection, and who solved the detection problem (is there any intersection?) earlier?
Bentley and Ottmann (1979); detection in O(nlogn)O(n \log n)O(nlogn) by Shamos and Hoey.
[Notes and Comments] What is the lower bound for reporting all kkk intersections among nnn segments, and which algorithms reach it deterministically?
Ω(nlogn+k)\boldsymbol{\Omega(n \log n + k)}Ω(nlogn+k) ; reached by Chazelle and Edelsbrunner (1988) with O(n+k)O(n + k)O(n+k) storage, and by Balaban with O(n)O(n)O(n) space. So the plane sweep, O(nlogn+klogn)O(n \log n + k \log n)O(nlogn+klogn) , is not optimal for large kkk . Randomized algorithms by Clarkson and Shor and by Mulmuley take O(nlogn+k)O(n \log n + k)O(nlogn+k) expected time.
[Notes and Comments] What is the red-blue segment intersection problem, and how fast can it be solved?
Two sets of segments, no two from the same set intersect: report the red/blue intersections. O(nlogn+k)\boldsymbol{O(n \log n + k)}O(nlogn+k) time and O(n)\boldsymbol{O(n)}O(n) storage (Mairson and Stolfi). This is exactly the network overlay problem; the chapter's sweep doesn't use this structure.
[Notes and Comments] How fast can the overlay of two connected subdivisions be computed ( nnn total complexity, kkk intersections)?
O(n+k)\boldsymbol{O(n + k)}O(n+k) (Finke and Hinrichs).