Dorim sa separam acum dreptele vizibile din origine de celelalte drepte. Sa vedem daca nu putem lucra cumva cu punctele duale. Intuitiv, ce inseamna o dreapta INvizibila din origine? Inseamna o dreapta "departata" de origine (in sensul ca alte drepte vor fi mai aproape decat ea si o vor obtura). In limbaj dual, asta inseamna ca punctul dual va fi mai aproape de origine, in sensul ca vor fi alte puncte mai departe decat el.
Asta cred ca deja va sugereaza ideea de rezolvare. Daca v-ati gandit la infasuratoare convexa, ati pus punctul pe y. Algoritmul este urmatorul:

* Se da multimea de drepte (a ~i~ *x+b ~i~ *y+c ~i~ =0)
* Aducem toate dreptele la forma a ~i~ *x+b ~i~ *y+1=0, impartind prin c ~i~

* Se da multimea de drepte !voronoi?img14.bmp!
* Aducem toate dreptele la forma !voronoi?img15.bmp!, impartind prin c ~i~

* Aflam infasuratoarea convexa a multimii de puncte (a ~i~ ,b ~i~ )
* Punctele de pe aceasta infasuratoare convexa corespund dreptelor vizibile din origine.

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

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

Fie !voronoi?img16.bmp!
!voronoi?img17.bmp!

Deci noua ecuatie este

ax + by + t =0

!voronoi?img18.bmp!

Cu alte cuvine, pentru a translata dreapta cu -Pi.x si -Pi.y, scadem din c valoarea a*Pi.x + b*Pi.y.