<p>Sa pornim de la urmatoarea problema: Avem o colectie de N drepte in plan, oricare doua neconfundate, astfel incat nici una din ele nu trece prin origine. Sa se indice care din drepte sunt vizibile din origine.</p>

<p>Un algoritm decent functioneaza in O(N^2^), astfel: ia fiecare dreapta d ~i~ , si o intersecteaaza cu fiecare din celelalte drepte d ~j~ . In acest fel, di se imparte in doua semidrepte, din care numai una este vizibila din origine, cealalta fiind obturata de catre dj. In felul acesta tot intersectam semidrepte peste semidrepte, si vedem daca in final ramanem cu vreun segment vizibil din origine. Desigur, pe parcurs apare tot tacamul de cazuri particulare: drepte verticale, drepte orizontale, erori de calcul, radicali, distante etc. Sper ca v-am scarbit destul ca sa vreti sa aflati si o implementare mai eleganta.</p>

<p>Un algoritm decent functioneaza in O(N^2^), astfel: ia fiecare dreapta d ~i~ , si o intersecteaaza cu fiecare din celelalte drepte d ~j~ . In acest fel, d ~i~ se imparte in doua semidrepte, din care numai una este vizibila din origine, cealalta fiind obturata de catre d~j~. In felul acesta tot intersectam semidrepte peste semidrepte, si vedem daca in final ramanem cu vreun segment vizibil din origine. Desigur, pe parcurs apare tot tacamul de cazuri particulare: drepte verticale, drepte orizontale, erori de calcul, radicali, distante etc. Sper ca v-am scarbit destul ca sa vreti sa aflati si o implementare mai eleganta.</p>

<p>Vom prezenta un algoritm foarte dragut si foarte cunoscut (in final) care rezolva problema in O(N log N). Facem intai urmatoarea conventie. De vreme ce dreptele nu trec prin origine, ele au ecuatii de forma ax+by+c=0, cu c<>0. Atunci le vom aduce pe toate la forma ax+by+1=0 (evident, impartind prin c).</p>

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 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.

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.

Algoritmul pentru aflarea poligonului Voronoi al lui P ~i~ este:

Algoritmul pentru aflarea poligonului Voronoi al lui Pi este:

* 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

* 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:

(**) 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

Fie t=a*Pi.x + b*Pi.y + c
a(x-Pi.x) + b(y-Pi.y) + t =0

Deci noua ecuatie este
ax + by + t =0

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.

Cu alte cuvine, pentru a translata dreapta cu -Pi.x si -Pi.y, scadem din c valoarea a*Pi.x + b*Pi.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.