Transcript Document

COSC 6114
Prof. Andy Mirzaian
TOPICS
 Line Segments Intersections
 Planar Subdivision
 Thematic Map Overlay
Line Segments Intersections
Thematic Map Overlay
Photos courtesy of ScienceGL
Applications:
•
•
•
•
•
•
•
•
Graphics: hidden line/surface removal
GIS: Geographic Information Systems
Cartography
VLSI circuit layout
Pattern recognition
Optimization: Linear Programming
Arrangement of lines, planes, hyper-planes
Visibility, kernels, etc.
References:
• [CLRS] chapter 33
• [M. de Berge et al] chapter 2
• [Preparata-Shamos’85] chapter 7
• [O’Rourke’98] chapter 7
Line Segments Intersection Problem
Given a set L={ l1,l2, … , ln } of n line segments in the plane,
report all pair-wise intersections in L.
(Modes: reporting, counting or disjointness.)
• Naïve approach: check every pair in L in O(n2) time.
• Can we make this output sensitive?
• Suppose there are a total of R intersecting pairs to report,
where 0  R  (n2).
 O(n log n)
time for counting & disjointness mode.
 O(R + n log n) time is achievable for reporting mode.
See also end of Lecture Slide 7.
Special Case: rectilinear L
Assume segments in L are vertical (blue) or horizontal (red),
and each intersection is between a red-blue pair.
e.g., in VLSI
Special Case: rectilinear L
Assume segments in L are vertical (blue) or horizontal (red),
and each intersection is between a red-blue pair.
Sweep-line
d
d
c
D
a
a
b
e
b
Plane Sweep Method: vertical sweep-line moving left-to-right.
• Active segments: horizontal segments that intersect the sweep-line.
• Sweep event schedule: x-sorted segment endpoints (2 per red, 1 per blue).
• Sweep Status: y-ordering of the active horizontal segments maintained
in an efficient dictionary D.
Special Case: rectilinear L
Assume segments in L are vertical (blue) or horizontal (red),
and each intersection is between a red-blue pair.
Sweep-line
d
d
c
c
D
a
a
b
e
b
Plane Sweep Method: vertical sweep-line moving left-to-right.
• Active segments: horizontal segments that intersect the sweep-line.
• Sweep event schedule: x-sorted segment endpoints (2 per red, 1 per blue).
• Sweep Status: y-ordering of the active horizontal segments maintained
in an efficient dictionary D.
Special Case: rectilinear L
Assume segments in L are vertical (blue) or horizontal (red),
and each intersection is between a red-blue pair.
Sweep-line
d
d
c
e2
c
D
a
a
b
e2
e
e1
b
e1
Plane Sweep Method: vertical sweep-line moving left-to-right.
• Active segments: horizontal segments that intersect the sweep-line.
• Sweep event schedule: x-sorted segment endpoints (2 per red, 1 per blue).
• Sweep Status: y-ordering of the active horizontal segments maintained
in an efficient dictionary D.
Special Case: rectilinear L
Assume segments in L are vertical (blue) or horizontal (red),
and each intersection is between a red-blue pair.
Sweep-line
d
c
a
b
e
Plane Sweep Method: vertical sweep-line moving left-to-right.
• Active segments: horizontal segments that intersect the sweep-line.
• Sweep event schedule: x-sorted segment endpoints (2 per red, 1 per blue).
• Sweep Status: y-ordering of the active horizontal segments maintained
in an efficient dictionary D.
• Computational Complexity:
 O(n) space
 O(R + n log n) time
- reporting mode
 O(n log n) time
- counting or disjointness modes.
Algorithm Rectilinear-Intersection-Report(L)
Q  {x-sorted end-points of segments in L}
Sweep Schedule
D 
Sweep Status
for each event (p,s)Q in sorted order do
O(n) iterations
if p is left-end of horizontal s then Insert (s,D)
O(log n) time
if p is right-end of horizontal s then Delete (s,D)
O(log n) time
if s is vertical then RangeReport (s,D)
O(Rs+ log n) time
end
s2
RangeReport (s,D)
O(Rs+ log n) time
Rs = #  with s
D
s
O(log n) for
counting or
disjointness
test
s1
s1
s2
Total time = O( n log n + s(Rs+ log n) ) = O(R + n log n).
General Case
Bentley-Ottman [1979], “Algorithms for reporting and counting geometric
intersections,” IEEE Trans. Comput. C-28:643-647.
O((R+n) log n) reporting time & O(n) space.
D
A
See also AAW
C
E
Sweep status:

CBA
B

Improvements:
• Balaban [1995], “An optimal algorithm for finding segments intersections,”
Proc. SoCG, pp:211-219.
O(R + n log n) reporting time & O(n) space.
• Lecture Slide 7: Randomized Algorithm in O(R + n log n) expected time.
Bentley-Ottman
Data Structures:
• Sweep Status D: an efficient dictionary to maintain the linear order of
active segments in the order they intersect the sweep-line.
• Sweep Schedule Q: a priority queue of sweep events (priority=x-coordinate).
segments left/right end points
Event points =
pair-wise segments intersection points
Book-keeping: a constant number of two-way pointers between
each segment and its contributed events in Q.
Bentley-Ottman
Temporary assumption: No two events have the same priority. (lexicographic)
FACT: Let p = lilj be an intersection event, and q its predecessor event.
Just after q is processed, both li and lj are active and adjacent
in the linear ordering of the sweep status D.
Proof: The shaded region must be empty of segments.
li
q
p
lj
Corollary: Every intersection event can eventually be detected and
inserted into Q before the sweep-line gets past it.
Proof: Each time the sweep status D changes, check its affected adjacent
active segment pairs to see if they intersect to the right of the sweep-line.
Algorithm Bentley-Ottman(L)
Q  {the 2n end-points of segments in L}
D
while Q   do
e  DeleteMin(Q)
ProcessEvent(e)
O( (R+n) log n ) time
n=|L|
2n+R iterations
O(log n) time
O(log n) time
end
Time = O( (R+n) log n )
Space used:
|D| = O(n) size
O(R+n) without “trimming” (see next slide)
|Q| =
O(n) with “trimming”
Procedure ProcessEvent(e)
O(log n ) time
1. If e is left end-point of segment s then
Insert (s,D); A  Above(s,D); B  Below(s,D)
Insert As and/or Bs into Q if they are “future” events
Trim: Delete AB from Q if it’s a “future” events
A
s
e
B
A
2. If e is right end-point of segment s then
A  Above(s,D); B  Below(s,D); Delete(s,D)
Insert AB into Q if it’s a “future” event
s
e
B
A
3. If e is si  sj then
{ suppose si = Above(sj,D) }
Interchange(si,sj,D); A  Above(sj,D); B  Below(si,D)
Insert Asj and/or Bsi into Q if they are “future” events
Trim: Delete Asi and Bsj from Q if “future” events
REPORT (e = si  sj)
end
si
e
sj
B
How to search in Dictionary D:
•
•
•
•
D maintains the y-ordering of the active line segments.
Each item in D is a line segment, with no explict “key”.
How do we search in D for an event point e?
Ask “is e vertically above/below node segment?”,
then go to right/left subtree accordingly.
B
E
D
A
D
e
C
C
E
B
A
Search path of e in the dictionary
sweep
line
Generalizations of Bentley-Ottman
edge – vertex intersections

edges with common end-points

Trapezoidal Decomposition (or Vertical Visibility Map)
These can be done during the plane-sweep without increase in computational complexity.
Sweep technique for intersection of
other kinds of objects
CONVEX
NON-CONVEX
A is above B
Is A above B?
A
A
B
B
Planar Subdivision
Planar Subdivision
Euler’s Formula: V – E + F – C = 1
vertex
edge
face
V =10
E =16
F=8
C =1
# vertices
# edges
# faces
# connected components
Planar Subdivision
Dual
vertex  face
edge  edge
face  vertex
Planar Subdivision
Dual
vertex  face
edge  edge
face  vertex
Planar Subdivision
Dual
Euler’s Formula
V–E+F=2
for connected planar graphs
For a spanning tree of the graph E=V-1, F=1.
(V) – (V-1) + (1) = 2. Formula is satisfied.
Now add the missing edges one by one.
Each such edge increments E and F by 1.
Euler’s Formula
V–E+F=2
for connected planar graphs
For a spanning tree of the graph E=V-1, F=1.
(V) – (V-1) + (1) = 2. Formula is satisfied.
Now add the missing edges one by one.
Each such edge increments E and F by 1.
Furthermore, if V  3 & each face has  3 boundary edges
(i.e., no parallel or self-loop edges, e.g., straight-line connected planar subdivision)

3F  2E
E  3V –6
F  2V –4
In the dual graph each vertex has degree  3.
Sum of vertex degrees = 2E.
Now apply the above inequality
to Euler’s formula.
Linear size Data structures for planar subdivisions
• DCEL: Doubly Connected Edge List
[Muller-Preparata 78]
• WEDS: Winged-Edge Data Structure
[Baumgart 75]
• QEDS: Quad-Edge Data Structure
[Guibas-Stolfi 85]
 These can also be used for 3D polyhedral boundary representation.
 DCEL can also represent disconnected planar graphs.
 QEDS can represent graphs embedded on arbitrary 2-manifolds.
DCEL: Doubly Connected Edge List
• Half-Edge-List: Each edge as a pair of oppositely oriented twin half-edges.
For each half-edge e: Origin(e), Twin(e), Next(e), Prev(e), IncidentFace(e).
Twin(e)
Origin(e)
v
e
the face on the
right side of e
IncidentFace(e)
• Vertex-List: For each vertex v: IncidentEdge(v) is an arbitrary half-edge e,
such that v = Origin(e).
• Face-List: For each face f:
OuterComp(f) : an arbitrary half-edge e incident to the outer boundary of f
such that f = IncidentFace(e)
InnerComps(f) : list of one such incident half-edge per inner-face boundary.
f
Components of WEDS and QEDS
• Face List: a list indexed by faces.
face-edge(f) = an arbitrary edge on the boundary of f.
• Vertex List: a list indexed by vertices.
vertex-edge(v) = an arbitrary edge incident on vertex v.
• Edge Data Structure: This is where WEDS and QEDS differ.
WEDS: Winged Edge Data Structure
e1 +
f0
e0 -
v1
e1 -
e
f1
v0
e0 +
record(e) =  v0 , v1 , f0 , f1 , e0- , e0+ , e1- , e1+ 
QEDS: Quad Edge Data Structure
Simultaneously represents primal & dual on any 2-manifold.
Primal graph
h
4
d
e
A
5
C
3
c
Dual graph
g
B
b
2
4
f
1
D
d’
A
e’
a’
a 1
0
C
g’
3
B
c’
b’
f’
2
h’
0
D
each edge-record is in 4 cycles:
h
5
C
4
d
g
D
3
e
B
A
0
a
1
c
b
2
5
f
Overlay of two planar straight-line subdivisions
Maps S1 and S2
Trapezoidal Decomposition
of the overlay map OM(S1,S2)
THEOREM: Let S1 and S2 be straight-line planar subdivisions of complexity
n1 and n2 respectively, and n= n1+n2. The overlay map OM(S1,S2)
can be constructed by generalization of Bentley-Ottman in
O((R+n) log n) time, where R is the complexity of the overlay.
Proof: Let D1 = DCEL(S1) and D2 = DCEL(S2).
We want to compute D = DCEL( OM(S1,S2) ).
Start with D  D1  D2 and do Bentley-Ottman.
• edge-edge intersection:
e1
e2
• vertex-edge intersection:
e
v
How to compute several boundary cycles of a face in the overlay
(an outer-face and several inner-face boundaries).
• Use the info from the trapzoidization to find which boundary cycles
belong to the same face as follows:
• v(C)  topmost vertex of boundary cycle C.
• The half-edges of C incident to v(C) determine whether C is an outer
boundary or a hole.
• Use Up-Vertical visibility chord of v(C) for every hole C to construct the
Cycle-Incidence-Graph G
• Vertices of each connected component of G are boundary cycles of the
same face of the subdivision.
C
v(C1)
Cycle-Incidence-Graph G:
C1
C2
C
C3
C5
C4
C7
C8
C3
C1
C0
C6
C0
outer
hole
C2
C7
C4
C6
C5
C8
Boolean Operations: An application of the map overlay algorithm.
Given simple polygons P1 and P2 , compute:
P1  P2
P1  P2
This also takes O( (R+n) log n) time, where
n = input complexity, R = output complexity.
P1  P2
U. Finke and K. Hinrichs [1995],
“Overlaying simply connected planar subdivisions in linear time,”
SoCG’95, pp: 119-126.
Show that OM(S1,S2) can be computed in O(R+n) time
if S1 and S2 are connected straight-line planar graphs.
Intersection of two Convex Sets
Fact 0: Intersection of any two convex sets is convex (possibly empty).
Proof: A,B [ (A,B  P Q)  (A,BP)(A,BQ) 
(AB  P)  (AB  Q)  (AB  PQ) ].
P
Q
B
A
Examples of convex sets:
Lines, line segments, convex polygons, half-planes, etc.
Line: ax + by = c
Half-plane: ax + by  c (or ax + by  c )
Intersection of two Convex Polygons
Let P and Q be convex polygons with, respectively, n and m vertices.
Consider the convex (possibly empty) polygon R = PQ.
Fact 1: R has at most n+m vertices.
Proof:
Let e be any edge of P.
e’ = eQ is convex, hence, either empty, a single vertex of Q,
or a sub-segment of e. In the latter case e’ is an edge of R.
(Similarly, with e an edge of Q and e’ = eP.)
Each edge e of P or Q can contribute at most one such edge e’ to R.
P and Q have n and m edges, respectively.
Hence, R can have at most n+m edges.
Intersection of two Convex Polygons
Fact 2: R = PQ can be computed in O(n+m) time.
Proof: Use the plane-sweep method. The upper and lower chains of P and Q are
x-monotone (from leftmost to rightmost vertex each). In O(n+m) time, merge these
4 x-sorted vertex-lists to obtain the n+m vertices of P and Q in x-sorted order.
This forms the sweep-schedule. These n+m vertical sweep-lines partition the plane
into n+m-1 vertical slabs. The intersection of each slab with P or Q is a trapezoid.
The two trapezoids within a slab can be intersected in O(1) time.
Hence, we can obtain PQ in O(n+m) time.
slab
Intersection of n Half-Planes
Problem: Given n half-planes H1, H2, … , Hn, compute their intersection
R = H1  H2  …  Hn .
Input: Hi: ai x + bi y  ci , i = 1..n
Output: convex polygon R (empty, bounded or unbounded).
R
Intersection of n Half-Planes
Problem: Given n half-planes H1, H2, … , Hn, compute their intersection
R = H1  H2  …  Hn .
Divide-&-Conquer in O(n log n) time: (Use Facts 1 and 2.)
(H1  …  H n/2 )  (H n/2 +1  …  Hn
Convex P,
|P|  n/2
T(n/2) time
Convex Q,
|Q|  n/2
T(n/2) time
Convex R = PQ, |R|  |P|+|Q|  n
O(n) time
T(n) = 2 T(n/2) + O(n) = O(n log n).
An Art Gallery Problem
We are given the floor-plan of an art gallery (with opaque walls) represented
by a simple polygon P with n vertices.
Is it possible to place a single point camera guard (with 360 vision) in the
gallery so that it can “see” every point inside the gallery?
 The set of all such points is called the “Kernel” of P.
 If Kernel(P) is not empty, then P is called a “star” polygon.
P
An Art Gallery Problem
We are given the floor-plan of an art gallery (with opaque walls) represented
by a simple polygon P with n vertices.
Is it possible to place a single point camera guard (with 360 vision) in the
gallery so that it can “see” every point inside the gallery?
 The set of all such points is called the “Kernel” of P.
 If Kernel(P) is not empty, then P is called a “star” polygon.
 Kernel(P) is the intersection of n half-planes defined by P’s edges.
P
An Art Gallery Problem
We are given the floor-plan of an art gallery (with opaque walls) represented
by a simple polygon P with n vertices.
Is it possible to place a single point camera guard (with 360 vision) in the
gallery so that it can “see” every point inside the gallery?
 The set of all such points is called the “Kernel” of P.
 If Kernel(P) is not empty, then P is called a “star” polygon.
 Kernel(P) is the intersection of n half-planes defined by P’s edges.
 Kernel(P) can be computed in O(n log n) time by divide-&-conquer.
 It can be computed in O(n) time by a careful incremental method that scans
the edges of P in order around its boundary. How?
P
Exercises
1.
Nested Circles: We are given a set C = {C1 , ... , Cn} of n circles in the plane. Each
circle is given by the xy-coordinates of its center and its radius. One of these circles
is the bounding circle and encloses the remaining n -1 circles in C. All circles in C
have disjoint boundaries. So, for any pair of circles Ci and Cj in C, either they are
completely outside each other, or one encloses the other. Therefore, we may have
several levels of nesting among these circles. (See Figure 1(a) below.) We say Ci is
immediately enclosed by Cj, if Cj is the smallest circle that encloses Ci. This
relationship corresponds to the parent-child relationship in the Nesting Tree of C.
(See Figure 1(b) below.) The problem is: given C, construct its Nesting Tree by
parent pointers, that is, output the array p[1.. n] such that p[i] = j means Ci is
immediately enclosed by Cj .
(a) Briefly describe a simple O(n2) time algorithm to solve the problem.
(b) Design and analyze an O(n log n) time algorithm to solve the problem.
2.
We are given a set T of n triangles and a set P of n points, all in the plane. The
triangles in T have disjoint boundaries, but some triangles may enclose some
others. There may be several nested levels of such enclosures. Design and
analyze an O(n log n) time algorithm that reports all points in P that are outside
all triangles in T.
3.
Design efficient plane-sweep algorithms to decide whether a given set S of n
objects from a certain object class is pair-wise disjoint for the following cases:
(a) Objects are circular disks. (A disk includes the interior.)
(b) Objects are circles. (A circle does not include the interior.)
(c) Objects are axis-parallel rectangular areas.
4.
We are given n axis-parallel rectangular areas in the plane. Assume the plane
background is white and the given rectangle areas are painted blue. Design an
O(n log n) time algorithm to compute the total blue area.
5.
We are given two simple polygons P and Q with n and m vertices, respectively.
(a) Devise an efficient algorithm to test whether P is completely inside Q?
(b) Show an O(n+m) time solution if in addition we know Q is convex.
6.
Show the kernel of a given simple polygon can be computed in linear time.
END