Complexitatea este O(N^3^), iar numarul de cazuri particulare este mare. In continuare revenim la principiul dualitatii si la problema de mai sus, a vizibilitatii unor drepte dintr-un punct.
Sa ne imaginam punctul Pi inconjurat de n+3 drepte: cele n-1 mediatoare ale segmentelor PiPj si cele 4 laturi ale dreptunghiului. Atunci poligonul Voronoi al lui Pi are drept laturi exact segmentele "vizibile" din Pi ale acestor n+3 drepte. Si dupa cum am vazut mai sus, aceasta problema se reduce la infasuratoare convexa. Trebuie avut grija pentru ca in rezolvarea de mai sus a problemei vizibilitatii am presupus ca punctul de observare este originea. Deci in cazul general va trebui sa translatam totul in asa fel incat Pi sa ajunga in origine, pentru a putea aplica principiul dualitatii. Un ultim aspect care trebuie abordat este acela ca problema de mai sus indica numai care drepte sunt vizibile, nu exact ce segmente din acele drepte.
Sa ne imaginam punctul P ~i~ inconjurat de n+3 drepte: cele n-1 mediatoare ale segmentelor P ~i~ P ~j~ si cele 4 laturi ale dreptunghiului. Atunci poligonul Voronoi al lui P ~i~ are drept laturi exact segmentele "vizibile" din P ~i~ ale acestor n+3 drepte. Si dupa cum am vazut mai sus, aceasta problema se reduce la infasuratoare convexa. Trebuie avut grija pentru ca in rezolvarea de mai sus a problemei vizibilitatii am presupus ca punctul de observare este originea. Deci in cazul general va trebui sa translatam totul in asa fel incat P ~i~ sa ajunga in origine, pentru a putea aplica principiul dualitatii. Un ultim aspect care trebuie abordat este acela ca problema de mai sus indica numai care drepte sunt vizibile, nu exact ce segmente din acele drepte.
Algoritmul pentru aflarea poligonului Voronoi al lui Pi este:
Algoritmul pentru aflarea poligonului Voronoi al lui P ~i~ este:
* Translateaza tot sistemul pentru a suprapune Pi peste origine (**)
* Construieste colectia de n+3 drepte D1, D2, ..., Dn+3
* Rezolva infasuratoarea convexa si afla colectia de drepte vizibile din origine, fie ele V1, V2, ..., Vk (in ordine trigonometrica)
* Calculeaza varfurile poligonului Voronoi: Wi = Vi-1 int. cu Vi
* Retranslateaza originea si {Wi} pentru a duce Pi in pozitia originala
(**) Cum se translateaza colectia de puncte este clar: din fiecare Pj.x se
scade Pi.x si din fiecare Pj.y se scade Pi.y; in acest fel Pi.x si pi.y
devin 0. Cum translatam laturile dreptunghiului (sau in cazul general o
dreapta oarecare) ? Daca ecuatia originala era ax+by+c=0, scriem aceasta
ecuatie relativ la Pi.x si Pi.y:
* Translateaza tot sistemul pentru a suprapune P ~i~ peste origine (**)
* Construieste colectia de n+3 drepte D ~1~ , D ~2~ , ..., D ~n+3~
* Rezolva infasuratoarea convexa si afla colectia de drepte vizibile din origine, fie ele V ~1~ , V ~2~ , ..., V ~k~ (in ordine trigonometrica)
* Calculeaza varfurile poligonului Voronoi: W ~i~ = V ~i-1~ int. cu V ~i~
* Retranslateaza originea si {W ~i~ } pentru a duce P ~i~ in pozitia originala
Fie t=a*Pi.x + b*Pi.y + c
a(x-Pi.x) + b(y-Pi.y) + t =0
(**) Cum se translateaza colectia de puncte este clar: din fiecare P ~j~.x se scade P ~i~.x si din fiecare P ~j~.y se scade P ~i~.y; in acest fel P ~i~.x si P ~i~.y devin 0. Cum translatam laturile dreptunghiului (sau in cazul general o dreapta oarecare) ? Daca ecuatia originala era ax+by+c=0, scriem aceasta ecuatie relativ la P ~i~.x si P ~i~.y:
Fie t=a*P ~i~.x + b*P ~i~.y + c
a(x-P ~i~.x) + b(y-P ~i~.y) + t =0
Deci noua ecuatie este
ax + by + t =0
Cu alte cuvine, pentru a translata dreapta cu -Pi.x si -Pi.y, scadem din c valoarea a*Pi.x + b*Pi.y.
Cu alte cuvine, pentru a translata dreapta cu -P ~i~.x si -P ~i~.y, scadem din c valoarea a*P ~i~.x + b*P ~i~.y.
Complexitatea noului algoritm este (pentru un singur poligon):
* O(N) translatia
* O(N) constructia poligonului Voronoi
* O(N) translatia inapoi
Pentru intreaga diagrama complexitatea este O(N^2 log N).
Pentru intreaga diagrama complexitatea este O(N^2^ log N).
Programul este implementat si testat. Nu este chiar scurt daca il construiti de la 0, dar daca puteti scrie fara greseala rutinele pentru infasuratoare convexa, intersectii de drepte si asa mai departe, cam in 1.5 - 2 ore ar trebui sa puteti programa toata povestea asta.
