Acoperiri convexe in plan

Report
Acoperiri convexe in plan
Universitatea “Politehnica” Bucuresti
Catedra de Calculatoare
conf. dr. ing. Costin-Anton BOIANGIU
[email protected]
Convexitate
• O multime S este convexa daca pentru orice pereche
de puncte p,q  S avem segmentul pq  S.
p
p
q
convexa
q
nonconvexa
• Formal, daca S este o multime intr-un spatiu
vectorial real sau complex:
Infasuratori convexe (Convex Hull)
Fie o multime S = {p1, p2, …, pN}. Infasuratoarea
convexa CH(S) este:
• Cel mai mic poligon convex care contine toate
punctele din S
• Intersectia tuturor multimilor convexe ce contin S
• Intersectia tuturor semispatiilor ce contin S
• Reuniunea tuturor triunghiurilor determinate de
puncte in S
• Multimea tuturor combinatiile convexe de puncte
din S
Aplicatii
• Detectia coliziunilor
▫ jocuri video: inlocuitor mai bun pentru bounding-box
• Aproximarea si compararea formelor
▫ pattern matching
• Pas de preprocesare pentru multi algoritmi in
geometria computationala
• Diametrului unui set de puncte este distanta
maxima dintre doua puncte din CH
• Infasuratoarea convexa este cea mai raspandita
structura in geometria computationala
Notiuni de baza
Problema: Fiind data o multime de n puncte P in plan, sa se
calculeze infasuratoarea sa convexa CH(P).
▫ CH(P) este un poligon convex
▫ CH(P) este o submultime a lui P
▫ Complexitate similara cu algoritmii de sortare
▫ Complexitate teoretica pentru poligoane cunoscute: O(n)
p3
p1
p5
p2
p9
p
p4 8
p7
p10
p6
p13
Intrare: p1,…, p13
p12
p11
Iesire: p1,p2,p11,p12,p13,p9,p3
Algoritmul naiv
DA
NU
Algoritmul naiv
Algoritm
• Pentru fiecare pereche de puncte se construiesc segmentul
dintre ele si dreapta suport
• Se gasesc toate segmentele ale caror drepte suport impart
planul in doua jumatati, astfel incat un semiplan contine toate
celelalte puncte.
• Se construieste infasuratoarea convexa din aceste segmente.
Complexitate
▫ Toate perechile:
n
n( n  1)
2
O ( )  O (
)  O(n )
2
 2
▫ Se verifica toate punctele pentru fiecare pereche: O(n)
fiecare, O(n3) in total.
Posibile probleme
• Corectitudinea algoritmului poate fi influentata in cazul
in care exista 3 puncte coliniare. Segmentele AB, BC si
AC vor fi toate incluse in infasuratoarea convexa.
A
B
C
• Probleme numerice – se poate concluziona ca nici unul
din cele 3 segmente (sau o pereche eronata a lor)
apartine infasuratorii convexe.
Presupuneri legate de pozitia
punctelor
• Cand se modeleaza un algoritm geometric, mai intai
facem unele presupuneri cu scop de simplificare, ex:
▫ Nu exista 3 puncte coliniare
▫ Nu exista 2 puncte cu aceeasi coordonata x sau y
▫ Altele: nu exista 3 puncte pe acelasi cerc, etc.
• Mai tarziu se ia in considerare cazul general:
▫
▫
▫
▫
Comportamentul algoritmului la cazuri speciale
Va ramane algoritmul corect?
Va ramane timpul de rulare neschimbat?
Se va modifica/extinde algoritmul pentru a trata
aceste situatii.
Extreme
Punct extrem
Unghi interior < pi
p6
p9
p12
p7
p11
p8
p5
p4
p2
p1
p0
Muchie extrema
Un punct nu este extrem pentru o multime S daca este continut intr-un
triunghi ale carui varfuri sunt puncte din S, dar nu este unul din varfurile
sale.
Gift Wrapping (Jarvis’ march)
p
3
Algoritm:
1.
▫
▫
Prima muchie p1 p2 din CH:
p1 punctul extrem cel mai jos
p2 punctul pentru care p1p2 face
unghiul cel mai mic cu orizontala
2. Pentru punctele ramase pi (i > 2) :
• Se calculeaza unghiul αi antiorar
fata de muchia precedenta
• Fie pj punctul cu cel mai mic αi
• Muchia (pi pj) devine o noua
muchie a infasuratorii CH
Figurativ: Se roteste antiorar o linie
prin pi pana atinge un alt punct.
p1
p5
p2
p
p4 8
p7
p13
p10
p6
p2
p1
12
Equatia dreptei
• (x1,y1) si (x2,y2) doua puncte.
• Ecuatia explicita a dreptei:
y  mx  c
y
y2  y1
x2  x1
tan  
x
y1 x2  y2 x1
(x2,y2)
y = mx+c
(x1,y1)
x2  x1
y2  y1
x2  x1
• Caz particular: x1= x2 (dreapta verticala)
m = tan θ
c
Complexitate
• n puncte, la fiecare pas n comparatii: O(n2)
• De fapt complexitatea este O(nh) , h = |CH(S)|
• De obicei h << n si atunci este comparabil cu
algoritmul lui Graham O(n logn)
Algoritmul lui Graham
Algoritm:
• Se gaseste un punct O in interiorul
infasuratorii (ex: centroidul –
media aritmetica a punctelor pe
coordonate)
• Se calculeaza unghiul antiorar αi de
la O la celelalte puncte fata de
orizontala.
• Se sorteaza punctele dupa unghiul
αi si dupa distanta fata de O in caz
de egalitate
• Se construieste infasuratoarea prin
verificarea tripletelor de puncte in
ordinea sortata si prin adaugarea
celor ce reprezinta “viraje la stanga”
(se elimina “virajele la dreapta”).
O
O
O
viraj stanga
viraj dreapta
Exemplu
• Daca p1p2p3 vireaza dreapta sau sunt coliniare, se
elimina p2 din CH(S) si se continua cu p0p1p3
• Daca p1p2p3 vireaza stanga, avanseaza la p2p3p4
p2
p1
p4
p0
O
Parcurgerea punctelor din CH(S)
1.
begin
2.
v = START
3.
w = PRED[v] /* w salveaza punctul dinainte de START */
4.
f = FALSE /* f indica daca scanarea a ajuns din nou la START */
5.
while (NEXT[v]  START or f = FALSE)
6.
if (NEXT[v] = w) then
7.
f = TRUE
8.
endif
9.
if (Left(v, NEXT[v], NEXT[NEXT[v]])) then
10.
v = NEXT[v] /* avanseaza */
11.
else
12.
delete NEXT[v] /* eliminare, operatie cu liste in O(1) */
13.
v = PRED[v] /* backtrack */
14.
endif
15.
endwhile
16. end
Graham: analiza complexitatii
• Se foloseste o stiva pentru procesarea punctelor sortate.
• Complexitate: O(n log n) determinata de pasul de
sortare
• Di = numarul de puncte scoase din stiva la procesarea pi,
• Fiecare punct este adaugat la stiva o singura data.
• Odata ce un punct este scos din stiva nu poate fi adugat
inca o data.
n
• Asadar
D n

i 1
i
Algoritmul Quick Hull (1)
Partitia initiala
• S este partitionata de o dreapta L
determinata de punctele l, r  S cu cea
mai mica si cea mai mare abscisa
(garantat distincte)
• S(1)  S este submultimea lui S
deasupra L.
• S(2)  S este submultimea lui S sub L.
• {S(1), S(2)} nu este o partitie stricta a lui
S, S(1)  S(2)  {l,r}.
• Urmeaza sa se construiasca CH(S(1)) si
CH(S(2)), si apoi concatenate in CH(S).
• Procesul este identic pentru S(1) si S(2),
vom detalia numai S(1).
S(1)
r
l
L
S(2)
Algoritmul Quick Hull (2)
Alegerea extremului
• Se cauta punctul h  S(1) astfel incat
1.
2.
triunghiul hlr are cea mai mare arie
posibila
daca h nu este unic determinat, se alege cel
pentru care unghiul hlr este maxim.
• Aceste conditii implica h  H(S). De ce?
• Se construieste prin h linia L paralela cu L
• Conditia (1) impune ca nu vor exista puncte
din S(1) (sau S) deasupra L,
• Pot fi mai multe puncte pe L, dar h va fi cel
mai din stanga, conform (2)
 h  H(S).
• h poate fi gasit in O(N) verificand fiecare
punct din S(1).
h
S(1)
L
r
l
L
Algoritmul Quick Hull (3)
Partitionarea
• Se construiesc doua linii orientate, L1
S(1,1)
dinspre l catre h, si L2 dinspre h catre
r.
• Fiecare punct din S(1) se poate clasifica
relativ la L1 si L2
• Nici un punct din S(1) nu poate fi situat
in acelasi timp la stanga L1 si L2.
l
• Punctele la dreapta L1 si L2 nu apartin
L L
CH(S) fiind in interiorul triunghiului
1
hlr si sunt eliminate
• Punctele la stanga L1 formeaza S(1,1).
• Punctele la stanga L2 formeaza S(1,2).
S(1,2)
h
r
L2
eliminate
Algoritmul Quick Hull (4)
S(1,2)
Pasul recursiv
• Procesul se reia pentru S(1,1) si S(1,2).
h
L1
S(1,2,2)
r
l
L
• Recurenta continua pana cand S(…)
are 0 puncte (toate punctele
interne au fost eliminate), adica lr
este o muchie din CH(S).
L2
Complexitate
• Gasirea extremelor initiale se face in timp O(n).
• La fiecare impartire, este nevoie de maxim n pasi pentru a
determina h, dar timpul total al apelului recursiv depinde de
marimile multimilor S(1) si S(2) .
Cazul favorabil Partitia este balansata
• T(n) = 2T(n/2) + O(n)

T(n)=O(n log n).
• O(n log n) se intampla pentru puncte distribuite aleator.
Cazul defavorabil Partitie disproportionata
• T(n) = T(n - 1) + O(n) = T(n - 1) + cn

T(n) = O(n2).
Divide et Impera
Algoritm:
• Se gaseste un punct ce are coordonata
x mediana (in timpul O(n) )
• Se partitioneaza multimea de puncte
in 2 jumatati
• Se calculeaza infasuratoarea convexa a
fiecarei jumatati (executie recursiva)
• Se combina cele doua infasuratori
convexe gasind tangentele lor
superioare si inferioare in O(n)
Complexitate de timp: O(n log n)
n
T ( n)  2T    O ( n)
2
mediana
tangente
Infasuratoare
stanga
Infasuratoare
dreapta
Tangente (1)
• Oricare doua poligoane convexe disjuncte au
4 tangente care le impart in doua categorii: in
intregime la stanga (+) si in intregime la
dreapta (-), raportat la dreapta tangentei.
(+,+)
(+,−)
(−,+)
(−,−)
Tangente (2)
Tangenta inferioara:
Se uneste puntul cel mai din
dreapta al poligonului din
stanga cu punctul cel mai din
stanga al poligonului din
dreapta si se parcurg muchiile
pana cand se atinge tangenta
inferioara
Complexitate: O(n).
1: (-,+)
2: (-,*)
Limita inferioara pentru infasuratori
convexe in 2D
Presupunere: Calcularea
infasuratorii convexe dureaza
(n log n)
Demonstratie: reducere de la
Sortare la Infasuratoare
Convexa:
• Fiind date n valori reale xi, se
genereaza n puncte pe graficul
unei functii convexe, ex. (xi,xi2).
• Se calculeaza infasuratoarea
convexa (ordonata) a punctelor. Complexitate(CH)=(n log n)
• Ordinea punctelor infasuratorii Dar exista un algoritm in
convexe corespunde ordinii xi.
timpul O(n log n), rezulta
Complexitate(CH)= (n log n)
Infasuratori convexe in 2D:
complexitate prezisa
• Numarul prezis de varfuri ale infasuratorii convexe a n
puncte alese uniform si independent:
▫ pe un disc:
O(n1/3)
▫ pe un patrat:
O(log n)
▫ pe un triunghi: O(log n)
Infasuratoarea convexa a unui poligon poate fi calculata in O(n).
Infasuratori convexe in 3D
• Idee: se generalizeaza procedurile din 2D
z
y
x
Puncte in 3D
Infasuratoare convexa
Infasuratori convexe in dimensiuni
superioare
Problema: fiind date n puncte in Rd, sa se gaseasca
infasuratoarea lor convexa (numita si politop convex).
• Fetele devin hiperfete de dimensiunea 2,3,…,d–1.
• Hiperfetele formeaza o structura de graf unde adiacentele
intre diferite entitati de dimensiunea i si i-1 sunt stocate.
• Cativa din algoritmii prezentati mai devreme sunt aplicabili
in dimensiuni superioare (in principiu), cu anumite
extensii.
Teorema 1: Infasuratoarea convexa de n puncte in spatiul d-dimensional
are cel mult ( n 
d / 2
) hiperfete.
Teorema 2: infasuratoarea convexa poate fi calculata folosind algorimul
“Gift Wrapping” in ( n 
d / 2 1
)  ( n 
d / 2
log n )

similar documents