h2. Diagrame Voronoi
In primul rand ce sunt alea. Sa consideram un poligon convex (pentru simplitate vom lua un dreptunghi) si n puncte P~1~, P~2~, ..., P~n~ in acel dreptunghi. Poligonul Voronoi al unui punct P~i~ este format din multimea acelor puncte P din dreptunghi care sunt mai aproape de P~i~ decat de orice alt punct P~j~. Impartirea dreptunghiului in poligoane se numeste diagrama Voronoi.
In primul rand ce sunt alea. Sa consideram un poligon convex (pentru simplitate vom lua un dreptunghi) si $n$ puncte $P ~1~, P ~2~, ..., P ~n~$ in acel dreptunghi. Poligonul Voronoi al unui punct $P ~i~$ este format din multimea acelor puncte $P$ din dreptunghi care sunt mai aproape de $P ~i~$ decat de orice alt punct $P ~j~$. Impartirea dreptunghiului in poligoane se numeste diagrama Voronoi.
Exemple:
Pentru n=1, exista un singur poligon Voronoi care este intregul dreptunghi.
Pentru n=2, ducem mediatoarea lui P ~1~ si P ~2~ si o intersectam cu dreptunghiul, obtinand doua poligoane. Punctele din poligonul lui P ~1~ sunt mai aproape de P ~1~ decat de P ~2~ si invers.
Pentru n=3, ducem cele trei mediatoare ale segmentelor P ~1~ P ~2~, P ~2~ P ~3~ si P ~3~ P ~1~ . Mediatoarele se intalnesc intr-un punct (cercul cercului circumscris) si le prelungim pana intersecteaza dreptunghiul. Pentru n=3, cand P ~1~ P ~2~ si P ~3~ sunt coliniare, dreptunghiul este sectionat in trei "felii".
Pentru $n=1$, exista un singur poligon Voronoi care este intregul dreptunghi.
Pentru $n=2$, ducem mediatoarea lui $P ~1~$ si $P ~2~$ si o intersectam cu dreptunghiul, obtinand doua poligoane. Punctele din poligonul lui $P ~1~$ sunt mai aproape de $P ~1~$ decat de $P ~2~$ si invers.
Pentru $n=3$, ducem cele trei mediatoare ale segmentelor $P ~1~ P ~2~, P ~2~ P ~3~$ si $P ~3~ P ~1~$ . Mediatoarele se intalnesc intr-un punct (cercul cercului circumscris) si le prelungim pana intersecteaza dreptunghiul. Pentru $n=3$, cand $P ~1~ P ~2~ si P ~3~$ sunt coliniare, dreptunghiul este sectionat in trei "felii".
Se poate defini diagrama Voronoi si fara constrangerile dreptunghiului, adica pe intregul plan xOy, dar in acest caz poligoanele sunt "deschise" (se duc la infinit). In orice caz, nu este greu de demonstrat ca poligoanele Voronoi sunt convexe.
Se poate defini diagrama Voronoi si fara constrangerile dreptunghiului, adica pe intregul plan $xOy$, dar in acest caz poligoanele sunt "deschise" (se duc la infinit). In orice caz, nu este greu de demonstrat ca poligoanele Voronoi sunt convexe.
O metoda "barbara" de a afla poligoanele Voronoi porneste de la observatia ca daca duc mediatoarea dintre P ~i~ si P ~j~ , atunci in mod sigur punctele de partea lui P ~j~ nu au cum sa fie in poligonul lui P ~i~ , pentru ca sunt mai aproape de P ~j~ decat de P ~i~ . Dec algoritmul este:
O metoda "barbara" de a afla poligoanele Voronoi porneste de la observatia ca daca duc mediatoarea dintre $P ~i~$ si $P ~j~$ , atunci in mod sigur punctele de partea lui $P ~j~$ nu au cum sa fie in poligonul lui $P ~i~$ , pentru ca sunt mai aproape de $P ~j~$ decat de $P ~i~$ . Dec algoritmul este:
* Pentru fiecare i afla poligonul lui P ~i~ astfel:
* Pentru fiecare i afla poligonul lui $P ~i~$ astfel:
* Porneste cu un poligon egal cu intregul dreptunghi
* Pentru fiecare j<>i
* Intersecteaza poligonul cu mediatoarea lui P ~i~ P ~j~ si "arunca" bucata din partea lui P ~j~
* Poligonul ramas este poligonul lui P ~i~
* Pentru fiecare $j<>i$
* Intersecteaza poligonul cu mediatoarea lui $P ~i~ P ~j~$ si "arunca" bucata din partea lui $P ~j~$
* Poligonul ramas este poligonul lui $P ~i~$
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.
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
* 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
(**) 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:
(**) 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 !voronoi?img16.bmp!
!voronoi?img17.bmp!
