<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 !voronoi?ec1.bmp!, cu !voronoi?ec2.bmp!. Atunci le vom aduce pe toate la forma ax+by+1=0 (evident, impartind prin c).</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 !voronoi?ec1.bmp!, cu !voronoi?ec2.bmp!. Atunci le vom aduce pe toate la forma !voronoi?img1.bmp! (evident, impartind prin c).</p>

Si-acum sa vedem ce este principiul dualitatii. El asociaza fiecarei drepte de forma ax+by+1=0 un punct de coordonate (a,b) in plan. Vom numi spatiul dreptelor "spatiu primal", iar spatiul punctelor corespunzatoare "spatiu dual". De aici decurg o multime de observatii foarte interesante, din care nici eu nu-mi aduc aminte decat cateva:

Si-acum sa vedem ce este principiul dualitatii. El asociaza fiecarei drepte de forma !voronoi?img1.bmp! un punct de coordonate (a,b) in plan. Vom numi spatiul dreptelor "spatiu primal", iar spatiul punctelor corespunzatoare "spatiu dual". De aici decurg o multime de observatii foarte interesante, din care nici eu nu-mi aduc aminte decat cateva:

# Oricarui punct din spatiul dual ii corespunde o dreapta in spatiul primal, si ce este mai interesant, oricaror doua puncte distincte din spatiul dual le corespund drepte distincte in spatiul primal
# Oricarei drepte din spatiul primal ii corespunde un punct in spatiul dual. Exceptia o constituie dreptele care trec prin origine, pentru ca ele au c=0 si nu pot fi normalizate. Totusi, daca extindem spatiul dual ca sa contina si puncte de la infinit, atunci fiecarei drepte care trece prin origine in spatiul primal ii corespunde un punct de la infinit in spatiul dual. Cu asta, bijectia intre cele doua spatii este completa.
# Sa ne inchipuim acum doua drepte in spatiul primal, care se intersecteaza intr-un punct:

<p>ax+by+1=0
dx+ey+1=0</p>

!voronoi?img1.bmp!
!voronoi?img2.bmp!

Fie (p,q) punctul lor de intersectie, care are proprietatile:

<p>ap+bq+1=0
dp+eq+1=0</p>

!voronoi?img3.bmp!
!voronoi?img4.bmp!

<p>Sa dualizam acum cele doua drepte. Obtinem punctele (a,b) si (d,e). Sa analizam ecuatia dreptei care trece prin aceste doua puncte:
!voronoi?ec52.bmp!</p>
<p>Dar ap+bq+1=dp+eq+1 --> (d-a)p + (e-b)q = 0 --> (d-a) = -(e-b)q/p</p>