> n|e$PKm%PNG
IHDREE+SgAMAPLTEޜٌ؊քҡpkjihgfedc^TN<9841Z/,Ȱ>12,0-.*,*)!o #𗗗y쌌@؋~∈凇kւՁ
̀~~~}}}|||{{{zzzyyyxxxwwwvvv-uuutttsssrrrqqqpppooonnnmmmlllkkkjjjiiighhgggfffeeedddcccbbbaaaFir```___^^^]]]\\\z[[[ZZZYYYXXXsWWWjVVVrUUUTTToSSSRRRQQQPPPiNNNMMMc]tSjShRg} pHYs~
IDATxkTgp
7A@hP:n!UD[dRCBٖ
WHFǦP܌&!XA,F)DhT˾3bU=@!xd>A.>2?}/U_9}(exׯ]tb_FJџݾuj|wקo>w֭kΝ;~zĩ3y@)ErY\L2§1sg)9q̩3A%swoR[[yW1ǎ903%ѻwV]]݄r쟻wxꉯDy{˕X;v{r꩓@)\#t#\]Wرc1DRHybUrǇ{vuY
0ǓSOup{XL..+WtY}xW)Eʇ8|n۶f%e;j8rccë?ZY-[-XS>{96rrhˊk-[S+"h4:IRH!=[@rgClopy-Ɣcѓp8#e#0;-!.&I|phŒ͛gpflLvO
&f喔Juu2IqNFBdĝ'ȵpe.vv܀_6~~mOZ,甗%QYfs=:fSL&S'!ao@lUw;Tmu07WxN8`a"]Ai$DP^;ܣt4-ꎚMP\bQjLrQ sN_)djUL *Tm>Bͭ
8Ć:Ȭ_RDNnSRwvTin
Փ"4E^Ô5E~NIk$f/+DIdM*InR|T3fC;;aZ4P[e
^@-S *5"ˠ1{J`a0bMW!DӫJť%7:=]jc+(wv#UУҎiPkL{RBKRl8ai(84: PNP^lՋM%f0̚^|G(:AbqY%J]
g00AWuZQ %9byPG
+A<[
kf͎Jth=1E\?2T'Nu2,Y@I7x
uHP1C |/ğ:M$
)6(l4nՈ❖tBM(Kg!F$IajQ2au ve@e%[`
֠O9x"v 5W)D5!s0"աT'А5#MmJzۂ-0iP#HcΈ46^#@ *5
s"6=2#@r,x&ٰ9Bi`y
R5B$h
D<0
zN2{Xj8Wy0{".;d$n9?!KcR|);I/~O+WAdIENDB`in(X
X
0Ob
Image "Photoshop.Image.40*Adobe Photoshop Image0Pb
Image "Photoshop.Image.40*Adobe Photoshop Image/00DTimes New Roman8b8b`b0bb0DArialNew Roman8b8b`b0bb0" DWingdingsRoman8b8b`b0bb00DSymbolgsRoman8b8b`b0bb0
@n?" dd@ @@``Pi \93 ^_
,'
,''b
7a
/$$$$$$$$$$$$$$$$$b$e$PKm%0e0e
A@ Ao 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCD|E|| ̙=,fff@8>g42d2db0bVppp@<4!d!d܋v8bM
g42d2db0bp,p?%O=VPolygon TriangulationU
Chapter 3 of the Textbook
Driving Applications
Guarding an Art Gallery
3D Morphing l%
%Guarding an Art GalleryPlace as few cameras as possible
Each part of the gallery must be visible to at least one of them
Problems: how many cameras and where should they be located?
x!A=!A= Transform to a Geometric ProblemDFloor plan may be sufficient and can be approximated as a simple polygon.
A simple polygon is a region enclosed by single closed polygonal chain that doesn t self-intersect
A camera s position corresponds to a point in the polygon
A camera sees those points in the polygon to which it can be connected with an open segment that lies in the interior of the polygon
assuming we have omni-cam that sees all directionsJe3Jd:3Problem AnalysisVA convex polygon can always be guarded by 1
Bound the number of cameras needed in terms of n, number of vertices in the polygon
2 polygons with the same number of vertices may not be equally easy to guard
Find the minimum number of cameras for a specific polygon is NP-hard
(Finding the triangulation of a specific polygon is NP-hard),TMEA,/$M=BTriangulation of a PolygonDefinition: A decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals
Triangulations are usually NOT unique
Every simple polygon admits a triangulation, and any triangulation of a simple polygon with n vertices consists of exactly n-2 trianglesi&i&\iObservations4We can guard a gallery by n-2 cameras
We can do better by placing cameras at the diagonals, then we only need n/2
Even better by placing cameras at vertices of the polygons => n/3 needed by using 3-coloring scheme of a triangulated polygon (ex) comb-shape like polygon
3-coloring of a polygon always exists&L&%H>Z&Polygon TriangulationsOFind a diagonal and triangulate the two resulting subpolygons recursively: O(n2)
Triangulation of a convex polygon: O(n)
First decompose a nonconvex polygon into convex pieces and then triangulate the pieces. But, it is as hard to do a convex decomposition as to triangulate the polygon
=> Decompose a polygon into monotone piecesR(-O
(
=,=,(=,,2P
(Partition a Polygon into Monotone Pieces)("&A simple polygon is monotone w.r.t. a line l if for any line l perpendicular to l the intersection of the polygon with l is connected
Property: If we walk from a topmost to a bottom-most vertex along the left (or right) boundary chain, then we always move downwards or horizontally, never upwards
Strategy to triangulate P: By first partition P into y-monotone pieces, then triangulate the pieces<e+&
4Turn VertexhImagine walking from the topmost vertex of P to the bottommost vertex on the left/right boundary chain& ...
Definition: A vertex where the direction in which we walk switches from downward to upward or vice versa
To partition a polygon into y-monotone pieces, get rid of turn vertices by adding diagonals~m+=,=,>=,
i
\kTypes of Turn Vertices0Start Vertex - its two neighbors lie below it and the interior angle < 180
End Vertex - its two neighbors lie above it and the interior angle < 180
Split Vertex - its two neighbors lie below it and the interior angle > 180
Merge Vertex - its two neighbors lie above it and the interior angle > 180LJLLL
J
L
LObservationsThe split and merge vertices are sources of local non-monotonicity
A polygon is y-monotone if it has no split or merge vertices
Use the plane-sweep method to remove split & merge verticesL<C
=
<6
{Removing Split/Merge Verticesv1 & vn: a counter-clock enumeration of vertices of P
e1 & en: a set of edges of P, where ei = segment (ei , ei+1)
Events are stored in event queue, ordered by y-coord.
If a split vertex, connect it to the lowest vertex (helper of its left edge) between the edges to its left and right
If a merge vertex, connect it to the highest vertex between the edges to its left and right
Store the edges (and their helpers) of P in the leaves of dynamic binary search tree T, left-to-right order reflects in order of leaves. Helpers may be replaced. Store only edges that have P to their right (or the left edges).
Pc.
/-i&bU3MakeMonotone(P)Input: A simple polygon P stored in a doubly-connected edge list D
Output: A partitioning of P into monotone subpolygons stored in D
1. Construct a priority queue Q on the vertices of P, using their y-coordinates as priority. If two points have the same y-coordinates, the one with smaller x has higher priority
2. Initialize an empty binary search tree T
3. while Q is not empty
4. do Remove vi with the highest priority from Q
5. Call the appropriate procedure to handle the vertex,
depending on its type~=,=,(=,=,=,=,%=,=,6"@ jmHandleStartVertex(Vi)$,1. Insert ei in T and set helper(ei) to vi-
,HandleEndVertex(Vi)$y1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from Tz8>H
HandleSplitVertex(Vi)$^1. Search in T to find the edge ej directly left of vi
2. Insert diagonal connecting vi to helper(ej ) in D
3. helper(ej ) vi
4. Insert ei in T and set helper(ei ) to vi b!A HandleMergeVertex(Vi)$L1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from T
4. Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diagonal connecting vi to helper(ej) in D
7. helper(ej ) vi
'
8
H*#F HandleRegularVertex(Vi)$,1. if the interior of P lies to the right of vi
2. then if helper(ei-1) is a merge vertex
3. then Insert diag. connect vi to helper(ei-1) in D
4. Delete ei-1 from T
5. Insert ei in T and set helper(ei) to vi
6. else Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diag. connect vi to helper(ej) in D
7. helper(ej ) vi
E+.%) Partitioning Algorithm AnalysisConstruct priority queue: O(n)
Initialize T: O(1)
Handle an event: O(log n)
one operation on Q: O(logn)
at most 1 query, 1 insertion & 1 deletion on T: O(logn)
insert at most 2 diagonals into D: O(1)
Total run time: O(n log n)
Storage: O(n)
RL~+
, =,,c4X
Triangulate a Monotone PolygonOrder the vertices in decreasing y-coordinates
Initialize an empty stack S; later it contains vertices that have been encountered
When handling a vertex, add as many diagonals from it to vertices on S as possible
Lowest vertex, encountered last, is on top of S
The part not yet triangulated looks like a funnel
This funnel is an invariant of the algorithm
consisted of a singe edge & a chain of reflex vertices
only the highest vertex (at the bottom of S) is convex
doI};_a
Next Vertex Vj to be Handled$
{On the single edge side
must be the lower end point of the edge: add diagonals to all reflex edges, except last one.
This vertex and first are pushed back to stack
On the chain of reflex vertices
Case 1
pop one; this one is already connected to Vj
pop vertices from stack till not possible
push the last one and Vj back
Case 2
pot & push the unable-to-connect one and push Vj
u4=, =,+
A
/
6@9TriangulateMontonePolygon(P)Input: A strictly y-monotone polygon P stored in a d.-c. e. list D
Output: A triangulation of P stored in doubly-connected edge list D
1. Merge the vertices on the left and right chains of P into one sequence, sorted on decreasing y-coordinate, with the leftmost comes first. Let u1 ...un denote sorted sequence
2. Push u1 and u2 onto the stack S
3. for j 3 to n 1
4. do if uj and vertex on top of S are on different chains
5. then Pop all vertices from S
6. Insert into D a diagonal from uj to each
popped vertex, except the last one
7. Push uj-1 and uj onto S
C *%=,=,=,=,=,=,&=,=,
=,7[!
&bt ^ : TriangulateMontonePolygon(P)h8. else Pop one vertex from S
9. Pop the other vertices from S as long as the diagonals from uj to them are inside P.
Insert these diagonals into D. Push the
last vertex that has been popped back onto S.
10. Push uj onto S
11. Add diagonals from un to all stack vertices except the
first and last one.
&i$*"$?=Pr "
Triangulation Algorithm Analysis7A strictly y-montone polygon with n vertices can be triangulated in linear time
A simple polygon with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storage
A planar subdivision with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storagePqu"-
!
"
!
"
#/Pb ` f3|` 3f3` ___>?" dd@(?lPfd@ d =," @̙ `" n?" dd@ @@``PV @ ` `p>>
F( @
R
s*?40
N!vgֳgֳ ?v
T Click to edit Master title style!
!.
H!vgֳgֳ ??_v
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
T"vgֳgֳ
?v
EUNC Chapel Hill
Tt#vgֳgֳ ? v
c M. C. Lin
`AO?o?Of
Nvdh@? ? f3| OG
(
Z?@?
Z?'d@?
Ngֳgֳ ?p
T Click to edit Master title style!
!
Hdgֳgֳ ?
p
W#Click to edit Master subtitle style$
$
Tĳgֳgֳ ?0`P
:
T$gֳgֳ ?0P
<
Tgֳgֳ ?0 P
<
R
s*?
`AP?o?Pf
Nvh@? ? f3|40@( 0
Cxrere1 ?e
v
Y*AAAaaX
C
v^
Cx4rere1 ?
Gv
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
Cxrere1 ? v
[*AAAaa
S~rere1 ?:eX v
Y*AAAaa!
S~T
rere1 ?: Xv
[*AAAaaB
s*i ? ̙33vF>0<( ld
<
<
Cx4 rere1 ?e
v
QName:AAAaa
<
Cx rere1 ? v
]August 27, 1998AAAaa7
<
S~
rere1 ?:eX v
q%Computational Geometry & Applications&&AAAaa!
<
S~rere1 ?: Xv
[*AAAaaH
<0i ? ̙33
P(
l
C
v
l
C4?_v
H
0h ? f3|
`(
l
CT
l
C|
H
0h ? f3|
p(
l
C}
r
S~
H
0h ? f3|
(
l
C
l
C-M
H
0h ? f3|
<(
<l
< C$
l
< COI
H
<0h ? f3|
@(
@l
@ C$
v
l
@ CZOezv
H
@0h ? f3|
T(
Tl
T C$
l
T C89_X
H
T0h ? f3|
D(
Dl
D Cı
l
D C$?_
H
D0h ? f3|
X( {|
Xl
X CD
l
X C?_
H
X0h ? f3|
\(
\l
\ C䵵
l
\ CD?_
H
\0h ? f3|
`(
`l
` Cd
l
` Cķ?_
H
`0h ? f3|
d( 8
dl
d C
v
l
d Ct?}_v
H
d0h ? f3|
h( 8
hl
h C$
l
h C"B
H
h0h ? f3|
l(
ll
l C
l
l C0P
H
l0h ? f3|
p( 'p
pl
p CD}
l
p C4!tW
H
p0h ? f3|
0t(
tl
t CT
l
t C f(
H
t0h ? f3|
@x(
xl
x Ct
l
x C
W
H
x0h ? f3|
P|(
|l
| C
l
| CTt
H
|0h ? f3|
`(
l
C
l
Ct
?"_
H
0h ? f3|
p(
l
C4
l
C
H
0h ? f3|
(
l
CT
l
C}
H
0h ? f3|
(
l
C4
l
C
H
0h ? f3|
(
l
C
l
C?_
H
0h ? f3|
( @@
l
Cd
l
C?_
H
0h ? f3|0xL( >--------->
LR
L 3
~
L C
G
H
L0i ? ̙334xXSٶW6g,cF:2*6D%PAzt"*j *2tD0"%}::oF}u}Z>9{s|25grrؿM N_C>T#a\IIId<&q=iO"Ci>H$cw
,}`JSPY[~1Yx;/̥<|/Pi.wzS~\:?6}L
Cy~lriޣz[Sc}EX[ΞL_/!$b$)%H"}Տi9
V"BZi-:Hd6"mBEڌi+6H;v"#`sgl75ӆC+=wZ5blklLg`6vy9+q%e9~Ve}{{gIpKI
/{ެY6K&nQU
m9iܺ2.ezggf}y̌D*D15*"2&6.qK?^dJН{g7nM,l;%;]1kk=Ek3*ǏPU;m@]E4;w@i3Ʃ3|vՆk5ht^G?p}aIA4trrR<<}cw4=3kԌ,Zi@6I H_Iƹ2슎V]]S?9@*:фz?#?39Yizuȟib߯˿ig
2'g25_w&b_7T39?6:S&'ٟo:gn{qwA]{_r
q qG)y?a{kj7njn?ttZLGM
pdw}ÑmܵG߽GNqs#nd?ʍA6z.
X}Q8C q$LbW+kRh`XxDdTtLllL\ToaEuCPOɣ6Ն=YYzCgǛĈ/ZBk<]kc^T~ݭuݑ7QmK
/kZL4t}9
ےހO}[:%;r!%3TV8MbspfX HMM(Khk%%{ZٞFdo5Y4O,8ti_ms`dlS~dߧ쬟{TܥtDP1/mصuN~
v"
$Ym;~V}aF\g1x
Rفyv%auy]4:v X.3cg1胹E%=o{b;~?w;7<
0Gϻ4+v& x[SƸZkoPS3wg`z`CX"5zzj#ͯ^ܓfA:iNk]KgWmIΤQޕF<{әmErnX[\v#au5qF7EbbP+èpg2|ٶ₠bv@b]'Fϲ~`\9hFelq~vӀaz,3ҩRm9d|G0ytbBl+2HQ+RH$oIa~No.ע>N!vn%mݰ#%1$F~~__#?H,IA\^;R+ޑpN x"O$I=DSEac!H,Y Ǎ"R"O!xlGs/'۞C'$ wנE⭨VŽg jK zT8zA:.N<
4CC;p^g10Ek3.37 Diz&1wY_QkWۿs7 Tbp?9
Ozvm>B%wEℸ_E!ؖ>;{T1f\?`0WtJ0q6@__hoo6hiif3hhhzt:0LTz #!" 9Cmm-*P]]
UUUMǨ4@GCECEE*u.!]D҆2TjÇJJJо*ܿG
!//W<m$y9lTfdggCVVdfffw2M@!##ӁF=# &!--
RSS
)))0^ai3$%!-0"JYHLLDPTwޅIz-
0YA||}N:f'O} PSSoS_TUU1
8q?ǎG=G#Gr>ګډ?15(+?00p4UW;sPGlc~꧃G7$)9}8:1 A(ҝkdm6]FG俆\@AQYYdw|bi\G+L9Y2=
LgɠP
JXFv5a1Mq~EP PC"[b3>7͙pJ(e)\LJOC\L܋j
N"]1l$Z4giPJz?FWn:eNBZXg0%ujdn0拜}RJU'%1Z`F&ҝ {NI)a%uP( LRt37H_SQ)}v":sgQLOg=꜀:)A^8=WLqS`#}['k0n/'m*+Ma;rQ ݇BJʕ{QgID UG/pMKX
jz̓M/jrcGasɎJJk;P Jfg@;CUW莣+ɪ8T?d&;e*qbnդϞpu{
Yg9S}1Xt)v,/(w´+}cQP^S:b%JW"MR
1mJ&f$zԾeloĂ@QR
M$8 )s(7)*k
+Rj[ 'ǅE6'丶hw8
%2fCKc`G
=}peQywV2ax+!'eU3[V懒>VRݏKZj
uQ>} e&MO j dRI+f1k+ 1 Շw5c+
EcySjRRtqq%8PhEU/,ƣJf]%ʬma!.F{f.|YYK9n@I}T1fwut*m̺=>jBӜ:dC~qCwͼrNh^(dcjo`֖ӏhGNqn/w5捑scPf7A(vW[[Zd^{Z9xn~
}琌d3{d^~%q? xih9ӫ?
;jJWU^K~#lo]Chm}V[AU%fĽϞ>fɒ%`,ݸ
fܪ?0MUI+0CgO\,`" b8O5OyP{l*g$_Nq⵰\db
-qi\u$G0J+AZϫ^d\Ng-rq.M縂6v\rzVуE`wCƑSUgy,X$qlmj^ut
=]m,to2rVcY-\0 99tM#OPWP }]MC#FG~Io%$bfΝv]qrPGkk(((Uktؓ.;wuW3E忏c?))(CE.FAoltt]KZΝܲ~ݚrJ]XZN2
%d_$aZj^qr!yV;mE 9i.hͺ5r{s)?Fa
ހR[Na~urd#AAr!ʊۜ/s~y7#N&z7>&'Cm{3ˌ8J^(3z0?05::ڏD"Y_>fqKEif%ѷ/^\X;SE{?),,r0w߹4sRK{~af4ΝFb9\
3eWI?}Q}OZ@ٙw.L9?/.uf7.ܿwO4xXSٶW6g,cF:eTlJ(HD0n2(P")B ww)k^}Ρ얈' ĳY|S܉'cV6$>u
P)]sa$$Q$$?4H#-@ߵc`KT`6bZط^Xo5O'&HO's5b6sML~D/?g}TXǦovŷ"bh»eL),@jao~vC}b[#K&3,s'&
F{N6~oW9'zt-Ka!^,ϻKpKA9?(Cb'lo\->Ma:C@k#ԐG6֧>[969^"S}˛oפ>,|-3Mgߡ)l VjdѢhQ-(mH;ОZ-hل&
SzLƯC
4.GZP)4ʠV-@S0V{./0&' 7
1S` :*>7bs͔@Jh6a>2};CBrw,]&Z!RFfѢy$/^fڵ-EV@"/^Ns
c瑃;hrW .^9]&+4 οaB9E3W]6mڼYv(rr"fXݤM[o۾yYc+JKs@ MIǝ\eѝceƑn"Z'JGb߾n߄ơUUFDgpw,X秽{;p]uͫq
ذ~W'FPZmmǱx/KX|R2~oj4Ngd3dEg0C欔Z>
,^S?:y[$Q\"P$X$
Խ/1gWJمqoiE{GQX7/ZYPnzw5Vе"5(!S43#xIZZC
!nw}-s>>wkP9ڊGCEwdmSܪtNgw7426nl&:\-Zw^qk[~~9)gݓ_vhڦ7k?Ī;gdteBXGYw%dhј̰F:^6J^q-GnEBO[9-QzQGEiuuQ riChC
u#Yv}(|ä0[Z*""^Od`D{?d`T>+:ŉڝHy0.!2('8Uuqwvv`F fjhy{Ma8Lևw=%+}Q#^"'ekF azCyϛۃFZa_qWBsZ[Nv$j
Me(AJ>>d
kF
δԞֺR5>mB%RX5O
NSVns~(oa}*9$Qsb۠HJ6#6)Ϛx!.Ԓaь{dt}"1,78oȄ<
A7' ߡ4.$Ӻ`o|3Ne] =3
0ھǷ;mBA8sK:P^U@
gFfe'ۥ1@{j[jjʻo@7vs
~RLȈVTHԔ߉\Ѝ&_z7 3Q|mj[V]Y攮,:]y\LkA_796M$1) Y`^UY3tIT&HV[Gĥ]@ux|Ytۯ89v:{L:=6ھF$^/)|kKÈisIʅvEs%qQenm{:sь&
f$289\ܜ8JI{C2zcĸVOT>ح3ZhHh ]{JxC>2B@OycL"
{O.҉#FS)Y0A7b~=.,Ǜm4B#bY $r8BYF$_>ƶ僜Zew-lc.I?6g\*_<c2Fi=7X;F8M"]i|Ĉ1@O(IxX8rA># H,I+n]PCi.H88z<r
$c$$ 0Q`s*I@6 w4F_EK$ّI|#9Н% w8WL;poTZR&WT3
I¾vj#o#['o#P 8EvxM
>~NiWT\?
ط?B^CπP[c8Cq^%*<=3@`cTxjx~xIq``z{{^nN/^@[[Bss3455߄hhhgϞA}}=<}F
,^HHHHnHP[[J$"TWWCUUD}3x*PQQJ=HtԂCYY}u{.*Cqq1Aaa!@~~>:LCۊH
L&r9̆1yɁlʂMp`7`@ff&dddNFf2LBzz:ARSSav'D&HNF>O7D,* )) FD}6L֢mYHLLj] >> 3)bcc!&&!**
"##݃ũaaa0x[͛0P*!!!)T*FJp+s 888ÿڵk
! ^
A`dڀ?/, oooȏtiz*P<==-<<<-tssWWW1pvvZ \rjnhZF0:>kJUU_J#l
-C孽Z[aU%z䝊 gO(3zv(-&&&D" ^:>buCMyzeC/^RT%7[iE{?.**q&1^n<}rK{AQV+֭iF`Eqq< 3eWIO 7'+-.F $nW>Ak eed())9y铊ܜ܂kjJ>`v?)Jr@Hqnw кPh(HȞhH(ȭhH(
MbGn(X
X
0Ob
Image "Photoshop.Image.40*Adobe Photoshop Oh+'0t-
px
,8@3D Polyhedral MorphingglablyhlabDept. of Computer Sciencei141Microsoft PowerPoint 7.0i@`E/@/ѽ@"'M@JPԽG,,oM & &&#TNPP0D
v
&
TNPP &&TNPP
&& "--&&e-$--d-$--ZZc-$ZZa-$^-$[-$V-$;;Q-$;;hhL-$hhF-$A-$*Z-021,,/1489<NT^cdefghijkprrjUrKKUUUUUUUUUUjjrK;KUUUUUUUUUUUUUUUe==KUUUUjXjUjUUUUUUUj5KUUU55UUUUUUUUUUUUUUUKUUUU5UUU5KU5UUUUUUUUUUUUUUUKUUj5UK55UUUUUUUUUUUUUUUUUUUUUUKU5UU5&UUUUUjjUUUUUUUUjjUUUUUUKUrUU&5UKUUU=rϹUUUUUU5eUUUUKUUKK&;UUUUU;rϊUUUUU;rUUUUUUKjK5&UUUUU;ՊUUUU; rrUUUUUUKeK5;KUKUKK;;uUUU55rUUUUUUUKUjK5UUjr;=ՂU;K;rςUUKUUUKKUKKU5(j;UKr;&UU;rςKUejKUUUeKU5j;UU=r&UU;eϜU35UUKKe5;&U;UUU;((;jUHU՜& rjKeKj5UUUKU;&5=U;U;Kς jjUUKj KKUUK;(&&;;UHKςH;KՂUUK&&jKU;;&5KrU;&HϸKKK;ϡUKjj3&KrX5&(;j;ϼUUK5ϡKKjj55K5j&5KrU3;j3Kj55Kjj&;&=U;H5̼ U5̀K555Kjj;5KHrUU&;5ϡjKK5KKK;55K;UUUU&5K5K١KK555KK55;;5j=&;UUUU&j&eոjKK55KKKHKKKKjU=UUK5r55ي5jչKKK5K5K5KjjjKj5K(U&(&&Ur5չHjռjKK55555HKjjrjj5XUUrϼ&;uU;չKU۹jKK5555KjjjjjuUjUKj&XuK;ټUH̡jjKKK555KKjjKj&X==&uտrUH۹j5ϡjjKK5555K5K5K&&rՊKKj3աjjKK55555&3jj5=թUKjr3١jK5555j=55UUթKUrre3ۡjKK555K55KjXթHUrςUHۡjK55;KKjjrurrrϊeeقKK۹jjK5mjuuա5j۹jjK53&UKOWe̡jjK5&5HWTSQQۡݡjjK5535;"8QQQQQ}թjjjK55555"$.8QQQQQ}jjKK55555KKm$....QQQQQgŹjjKK555555555KKOj"8...QQQQQQӸjjjKKKKKKjjjjW!....QQQQQڳjjT!8...QQQJJ仳i....JQJggη!!.8Jgggg}ڳ$8J8JggggoT!88AAQggggڳ!J8J8JggggT.!!8A8Qogg}!J8J8gggoѳi!!!8J8ggogo}ڻi!88JJgQoo}T.88JJJggQT!888JJJgggT!.88JJgggi$!88JJQgggogi$!8JJQgggoooogomSJ8JJQooogggzizSSSSSz&--yo--
Times New Roman- .'2
_Polygon Triangulation!
$.--fJ-- Wingdings- f.2
Tl."Arialng- .-2
xChapter 3 of the Textbook.Wingdings- f.2
qTl."Arialng- .%2
qxDriving Applications."Arialng- .2
."Arialng- =,.*2
Guarding an Art Gallery
."Arialng- .2
."Arialng- =,.2
3D Morphing
.--"Systemn-&TNPP &Ob
Image "Photoshop.Image.40*Adobe Photoshop Image0Pb
Image "Photoshop.Image.40*Adobe Photoshop Image/00DTimes New RomanbbDb0hbhb0DArialNew RomanbbDb0hbhb0" DWingdingsRomanbbDb0hbhb00DSymbolgsRomanbbDb0hbhb0
@n?" dd@ @@``Pi \93 ^_
,'
,''b
7a
/$$$$$$$$$
1_Dept. of Computer Science՜.+,D՜.+,
$,
41On-screen Show,University of North Carolina at Chapel Hill
Times New RomanArial
WingdingsSymbolDefauImage0Pb
Image "Photoshop.Image.40*Adobe Photoshop Image/00DTimes New RomanbbDb0hbhb0DArialNew RomanbbDb0hbhb0" DWingdingsRomanbbDb0hbhb00DSymbolgsRomanbbDb0hbhb0
@n?" dd@ @@``Pi \93 ^_
,'
,''b
7a
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry
dO)lֽ Pictures&'()*+,-./056789:;<=Current User9SummaryInformation(-PowerPoint Document(DocumentSummaryInformation8
/$$$$$$$$$$$$$$$$$b$e$PKm%0e0e
A@ Ao 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCD|E|| ̙=,fff@8>g42d2dtb0lbVppp@<4!d!dlӴbM
g42d2dtb0lbp,p?%O=VPolygon TriangulationU
Chapter 3 of the Textbook
Driving Applications
Guarding an Art Gallery
3D Morphing l%
%Guarding an Art GalleryPlace as few cameras as possible
Each part of the gallery must be visible to at least one of them
Problems: how many cameras and where should they be located?
x!A=!A= Transform to a Geometric ProblemDFloor plan may be sufficient and can be approximated as a simple polygon.
A simple polygon is a region enclosed by single closed polygonal chain that doesn t self-intersect
A camera s position corresponds to a point in the polygon
A camera sees those points in the polygon to which it can be connected with an open segment that lies in the interior of the polygon
assuming we have omni-cam that sees all directionsJe3Jd:3Problem AnalysisA convex polygon can always be guarded by 1
Bound the number of cameras needed in terms of n, number of vertices in the polygon
2 polygons with the same number of vertices may not be equally easy to guard
Find the minimum number of cameras for a specific polygon is NP-hard
,TME,/$M=Triangulation of a PolygonDefinition: A decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals
Triangulations are usually NOT unique
Every simple polygon admits a triangulation, and any triangulation of a simple polygon with n vertices consists of exactly n-2 trianglesi&i&\iObservations4We can guard a gallery by n-2 cameras
We can do better by placing cameras at the diagonals, then we only need n/2
Even better by placing cameras at vertices of the polygons => n/3 needed by using 3-coloring scheme of a triangulated polygon (ex) comb-shape like polygon
3-coloring of a polygon always exists&L&%H>Z&Polygon TriangulationsOFind a diagonal and triangulate the two resulting subpolygons recursively: O(n2)
Triangulation of a convex polygon: O(n)
First decompose a nonconvex polygon into convex pieces and then triangulate the pieces. But, it is as hard to do a convex decomposition as to triangulate the polygon
=> Decompose a polygon into monotone piecesR(-O
(
=,=,(=,,2P
(Partition a Polygon into Monotone Pieces)("&A simple polygon is monotone w.r.t. a line l if for any line l perpendicular to l the intersection of the polygon with l is connected
Property: If we walk from a topmost to a bottom-most vertex along the left (or right) boundary chain, then we always move downwards or horizontally, never upwards
Strategy to triangulate P: By first partition P into y-monotone pieces, then triangulate the pieces<e+&
4Turn VertexhImagine walking from the topmost vertex of P to the bottommost vertex on the left/right boundary chain& ...
Definition: A vertex where the direction in which we walk switches from downward to upward or vice versa
To partition a polygon into y-monotone pieces, get rid of turn vertices by adding diagonals~m+=,=,>=,
i
\kTypes of Turn Vertices0Start Vertex - its two neighbors lie below it and the interior angle < 180
End Vertex - its two neighbors lie above it and the interior angle < 180
Split Vertex - its two neighbors lie below it and the interior angle > 180
Merge Vertex - its two neighbors lie above it and the interior angle > 180LJLLL
J
L
LObservationsThe split and merge vertices are sources of local non-monotonicity
A polygon is y-monotone if it has no split or merge vertices
Use the plane-sweep method to remove split & merge verticesL<C
=
<6
{Removing Split/Merge Verticesv1 & vn: a counter-clock enumeration of vertices of P
e1 & en: a set of edges of P, where ei = segment (ei , ei+1)
Events are stored in event queue, ordered by y-coord.
If a split vertex, connect it to the lowest vertex (helper of its left edge) between the edges to its left and right
If a merge vertex, connect it to the highest vertex between the edges to its left and right
Store the edges (and their helpers) of P in the leaves of dynamic binary search tree T, left-to-right order reflects in order of leaves. Helpers may be replaced. Store only edges that have P to their right (or the left edges).
Pc.
/-i&bU3MakeMonotone(P)Input: A simple polygon P stored in a doubly-connected edge list D
Output: A partitioning of P into monotone subpolygons stored in D
1. Construct a priority queue Q on the vertices of P, using their y-coordinates as priority. If two points have the same y-coordinates, the one with smaller x has higher priority
2. Initialize an empty binary search tree T
3. while Q is not empty
4. do Remove vi with the highest priority from Q
5. Call the appropriate procedure to handle the vertex,
depending on its type~=,=,(=,=,=,=,%=,=,6"@ jmHandleStartVertex(Vi)$,1. Insert ei in T and set helper(ei) to vi-
,HandleEndVertex(Vi)$y1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from Tz8>H
HandleSplitVertex(Vi)$^1. Search in T to find the edge ej directly left of vi
2. Insert diagonal connecting vi to helper(ej ) in D
3. helper(ej ) vi
4. Insert ei in T and set helper(ei ) to vi b!A HandleMergeVertex(Vi)$L1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from T
4. Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diagonal connecting vi to helper(ej) in D
7. helper(ej ) vi
'
8
H*#F HandleRegularVertex(Vi)$,1. if the interior of P lies to the right of vi
2. then if helper(ei-1) is a merge vertex
3. then Insert diag. connect vi to helper(ei-1) in D
4. Delete ei-1 from T
5. Insert ei in T and set helper(ei) to vi
6. else Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diag. connect vi to helper(ej) in D
7. helper(ej ) vi
E+.%) Partitioning Algorithm AnalysisConstruct priority queue: O(n)
Initialize T: O(1)
Handle an event: O(log n)
one operation on Q: O(logn)
at most 1 query, 1 insertion & 1 deletion on T: O(logn)
insert at most 2 diagonals into D: O(1)
Total run time: O(n log n)
Storage: O(n)
RL~+
, =,,c4X
Triangulate a Monotone PolygonOrder the vertices in decreasing y-coordinates
Initialize an empty stack S; later it contains vertices that have been encountered
When handling a vertex, add as many diagonals from it to vertices on S as possible
Lowest vertex, encountered last, is on top of S
The part not yet triangulated looks like a funnel
This funnel is an invariant of the algorithm
consisted of a singe edge & a chain of reflex vertices
only the highest vertex (at the bottom of S) is convex
doI};_a
Next Vertex Vj to be Handled$
{On the single edge side
must be the lower end point of the edge: add diagonals to all reflex edges, except last one.
This vertex and first are pushed back to stack
On the chain of reflex vertices
Case 1
pop one; this one is already connected to Vj
pop vertices from stack till not possible
push the last one and Vj back
Case 2
pot & push the unable-to-connect one and push Vj
u4=, =,+
A
/
6@9TriangulateMontonePolygon(P)Input: A strictly y-monotone polygon P stored in a d.-c. e. list D
Output: A triangulation of P stored in doubly-connected edge list D
1. Merge the vertices on the left and right chains of P into one sequence, sorted on decreasing y-coordinate, with the leftmost comes first. Let u1 ...un denote sorted sequence
2. Push u1 and u2 onto the stack S
3. for j 3 to n 1
4. do if uj and vertex on top of S are on different chains
5. then Pop all vertices from S
6. Insert into D a diagonal from uj to each
popped vertex, except the last one
7. Push uj-1 and uj onto S
C *%=,=,=,=,=,=,&=,=,
=,7[!
&bt ^ : TriangulateMontonePolygon(P)h8. else Pop one vertex from S
9. Pop the other vertices from S as long as the diagonals from uj to them are inside P.
Insert these diagonals into D. Push the
last vertex that has been popped back onto S.
10. Push uj onto S
11. Add diagonals from un to all stack vertices except the
first and last one.
&i$*"$?=Pr "
Triangulation Algorithm Analysis7A strictly y-montone polygon with n vertices can be triangulated in linear time
A simple polygon with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storage
A planar subdivision with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storagePqu"-
!
"
!
"
#/Pbr
h_b#n(X
X
0lt DesignPolygon TriangulationGuarding an Art Gallery!Transform to a Geometric ProblemProblem AnalysisTriangulation of a Polygon
ObservationsPolygon Triangulations)Partition a Polygon into Monotone PiecesTurn VertexTypes of Turn Vertices
ObservationsRemoving Split/Merge VerticesMakeMonotone(P)HandleStartVertex(Vi)HandleEndVertex(Vi)HandleSplitVertex(Vi)HandleMergeVertex(Vi)HandleRegularVertex(Vi) Partitioning Algorithm AnalysisTriangulate a Monotone PolygonNext Vertex Vj to be HandledTriangulateMontonePolygon(P)TriangulateMontonePolygon(P)!Triangulation Algorithm AnalysisFonts UsedDesign TemplateEmbedded OLE Servers
Slide Titles 6>
_PID_GUIDAN{0EF19320-3D95-11D2-8E33-00A024A3E91B}24A3E91B}$$$$$$$$b$e$PKm%0e0e
A@ Ao 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCD|E|| ̙=,fff@8>g4BdBdtb0lbppp@<4!d!dvbM
g42d2dtb0lbp,p?%O=VPolygon TriangulationU
Chapter 3 of the Textbook
Driving Applications
Guarding an Art Gallery
3D Morphing l%
%Guarding an Art GalleryPlace as few cameras as possible
Each part of the gallery must be visible to at least one of them
Problems: how many cameras and where should they be located?
x!A=!A= Transform to a Geometric ProblemDFloor plan may be sufficient and can be approximated as a simple polygon.
A simple polygon is a region enclosed by single closed polygonal chain that doesn t self-intersect
A camera s position corresponds to a point in the polygon
A camera sees those points in the polygon to which it can be connected with an open segment that lies in the interior of the polygon
assuming we have omni-cam that sees all directionsJe3Jd:3Problem AnalysisA convex polygon can always be guarded by 1
Bound the number of cameras needed in terms of n, number of vertices in the polygon
2 polygons with the same number of vertices may not be equally easy to guard
Find the minimum number of cameras for a specific polygon is NP-hard
,TME,/$M=Triangulation of a PolygonDefinition: A decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals
Triangulations are usually NOT unique
Every simple polygon admits a triangulation, and any triangulation of a simple polygon with n vertices consists of exactly n-2 trianglesi&i&\iObservations4We can guard a gallery by n-2 cameras
We can do better by placing cameras at the diagonals, then we only need n/2
Even better by placing cameras at vertices of the polygons => n/3 needed by using 3-coloring scheme of a triangulated polygon (ex) comb-shape like polygon
3-coloring of a polygon always exists&L&%H>Z&Polygon TriangulationsOFind a diagonal and triangulate the two resulting subpolygons recursively: O(n2)
Triangulation of a convex polygon: O(n)
First decompose a nonconvex polygon into convex pieces and then triangulate the pieces. But, it is as hard to do a convex decomposition as to triangulate the polygon
=> Decompose a polygon into monotone piecesR(-O
(
=,=,(=,,2P
(Partition a Polygon into Monotone Pieces)("&A simple polygon is monotone w.r.t. a line l if for any line l perpendicular to l the intersection of the polygon with l is connected
Property: If we walk from a topmost to a bottom-most vertex along the left (or right) boundary chain, then we always move downwards or horizontally, never upwards
Strategy to triangulate P: By first partition P into y-monotone pieces, then triangulate the pieces<e+&
4Turn VertexhImagine walking from the topmost vertex of P to the bottommost vertex on the left/right boundary chain& ...
Definition: A vertex where the direction in which we walk switches from downward to upward or vice versa
To partition a polygon into y-monotone pieces, get rid of turn vertices by adding diagonals~m+=,=,>=,
i
\kTypes of Turn Vertices0Start Vertex - its two neighbors lie below it and the interior angle < 180
End Vertex - its two neighbors lie above it and the interior angle < 180
Split Vertex - its two neighbors lie below it and the interior angle > 180
Merge Vertex - its two neighbors lie above it and the interior angle > 180LJLLL
J
L
LObservationsThe split and merge vertices are sources of local non-monotonicity
A polygon is y-monotone if it has no split or merge vertices
Use the plane-sweep method to remove split & merge verticesL<C
=
<6
{Removing Split/Merge Verticesv1 & vn: a counter-clock enumeration of vertices of P
e1 & en: a set of edges of P, where ei = segment (vi , vi+1)
Events are stored in event queue, ordered by y-coord.
If a split vertex, connect it to the lowest vertex (helper of its left edge) between the edges to its left and right
If a merge vertex, connect it to the highest vertex between the edges to its left and right
Store the edges (and their helpers) of P in the leaves of dynamic binary search tree T, left-to-right order reflects in order of leaves. Helpers may be replaced. Store only edges that have P to their right (or the left edges).
Pc.
/-i&>UFMakeMonotone(P)Input: A simple polygon P stored in a doubly-connected edge list D
Output: A partitioning of P into monotone subpolygons stored in D
1. Construct a priority queue Q on the vertices of P, using their y-coordinates as priority. If two points have the same y-coordinates, the one with smaller x has higher priority
2. Initialize an empty binary search tree T
3. while Q is not empty
4. do Remove vi with the highest priority from Q
5. Call the appropriate procedure to handle the vertex,
depending on its type~=,=,(=,=,=,=,%=,=,6"@ jmHandleStartVertex(Vi)$,1. Insert ei in T and set helper(ei) to vi-
,HandleEndVertex(Vi)$y1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from Tz8>H
HandleSplitVertex(Vi)$^1. Search in T to find the edge ej directly left of vi
2. Insert diagonal connecting vi to helper(ej ) in D
3. helper(ej ) vi
4. Insert ei in T and set helper(ei ) to vi b!A HandleMergeVertex(Vi)$L1. if helper(ei-1) is a merge vertex
2. then Insert diagonal connecting vi to helper(ei-1) in D
3. Delete ei-1 from T
4. Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diagonal connecting vi to helper(ej) in D
7. helper(ej ) vi
'
8
H*#F HandleRegularVertex(Vi)$,1. if the interior of P lies to the right of vi
2. then if helper(ei-1) is a merge vertex
3. then Insert diag. connect vi to helper(ei-1) in D
4. Delete ei-1 from T
5. Insert ei in T and set helper(ei) to vi
6. else Search in T to find the edge ej directly left of vi
5. if helper(ej) is a merge vertex
6. then Insert diag. connect vi to helper(ej) in D
7. helper(ej ) vi
E+.%) Partitioning Algorithm AnalysisConstruct priority queue: O(n)
Initialize T: O(1)
Handle an event: O(log n)
one operation on Q: O(logn)
at most 1 query, 1 insertion & 1 deletion on T: O(logn)
insert at most 2 diagonals into D: O(1)
Total run time: O(n log n)
Storage: O(n)
RL~+
, =,,c4X
Triangulate a Monotone PolygonOrder the vertices in decreasing y-coordinates
Initialize an empty stack S; later it contains vertices that have been encountered
When handling a vertex, add as many diagonals from it to vertices on S as possible
Lowest vertex, encountered last, is on top of S
The part not yet triangulated looks like a funnel
This funnel is an invariant of the algorithm
consisted of a singe edge & a chain of reflex vertices
only the highest vertex (at the bottom of S) is convex
doI};_a
Next Vertex Vj to be Handled$
{On the single edge side
must be the lower end point of the edge: add diagonals to all reflex edges, except last one.
This vertex and first are pushed back to stack
On the chain of reflex vertices
Case 1
pop one; this one is already connected to Vj
pop vertices from stack till not possible
push the last one and Vj back
Case 2
pot & push the unable-to-connect one and push Vj
u4=, =,+
A
/
6@9TriangulateMontonePolygon(P)Input: A strictly y-monotone polygon P stored in a d.-c. e. list D
Output: A triangulation of P stored in doubly-connected edge list D
1. Merge the vertices on the left and right chains of P into one sequence, sorted on decreasing y-coordinate, with the leftmost comes first. Let u1 ...un denote sorted sequence
2. Push u1 and u2 onto the stack S
3. for j 3 to n 1
4. do if uj and vertex on top of S are on different chains
5. then Pop all vertices from S
6. Insert into D a diagonal from uj to each
popped vertex, except the last one
7. Push uj-1 and uj onto S
C *%=,=,=,=,=,=,&=,=,
=,7[!
&bt ^ : TriangulateMontonePolygon(P)h8. else Pop one vertex from S
9. Pop the other vertices from S as long as the diagonals from uj to them are inside P.
Insert these diagonals into D. Push the
last vertex that has been popped back onto S.
10. Push uj onto S
11. Add diagonals from un to all stack vertices except the
first and last one.
&i$*"$?=Pr "
Triangulation Algorithm Analysis7A strictly y-montone polygon with n vertices can be triangulated in linear time
A simple polygon with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storage
A planar subdivision with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storagePqu"-
!
"
!
"
#/Pbr_
x_b__