h1. Minimal enclosing circle

(Categoria _Geometrie analitica_, Autor _Bogdan Tataroiu_)

(Categoria _Geometrie_, Autor _Bogdan Tataroiu_)

In cadrul acestui articol vom analiza problema determinarii unui cerc de raza minima ce contine in interior sau pe circumferinta toate punctele dintr-un set dat. Aceasta problema mai poate fi gasita si sub denumirea de _Smallest Enclosing Circle_ sau _Mininum Spanning Circle_.

h2. Algoritm {$O(N^2^)$} !>minimal-enclosing-circle?schema.gif!

Algoritmul acesta se bazeaza pe aceeasi observatii ca mai sus. Se porneste de la un cerc mare care sigur cuprinde toate punctele si se micsoreaza la fiecare pas raza cercului cat mai mult posibil.

Algoritmul acesta se bazeaza pe aceleasi observatii ca mai sus. Se porneste de la un cerc mare care sigur cuprinde toate punctele si se micsoreaza la fiecare pas raza cercului cat mai mult posibil.

# Se construieste un cerc de raza suficient de mare incat sa cuprinda toate punctele in mod sigur (raza infinit) si un centru ales aleator.
# Se gaseste punctul cel mai departat de centrul cercului, notat cu {$A$}, si se micsoreaza raza cercului pana cand acesta atinge punctul.

* {!>minimal-enclosing-circle?figura.png 40%!} Dandu-se doua cercuri de raza {$R{~1~}$} si {$R{~2~}$}, avand {$R{~1~} < R{~2~}$}, atunci intersectia cercului de raza {$R{~2~}$} cu interiorul cercului de raza {$R{~1~}$} formeaza un arc de cerc de lungime mai mica decat {$&pi;$} (cel albastru in poza alaturata). Daca arcul de cerc ar avea o lungime mai mare ca {$&pi;$} atunci acesta ar trebui sa contina 2 puncte diametral opuse, aflate la o distanta de {$2R{~2~}$}, insa in cercul de raza {$R{~1~}$} cea mai mare distanta intre 2 puncte din interiorul sau poate fi maxim {$2R{~1~}$}. Cum {$R{~1~} < R{~2~}$}, acest lucru este imposibil.
* Presupunem prin reducere la absurd ca {$P$} nu apartine circumferintei cercului {$C{~I &#8746; {P}~}$}. Este usor de vazut ca raza cercului {$C{~I~}$} este mai mica ca cea a cercului {$C{~I &#8746; {P}~}$}, deoarece {$C{~I &#8746; {P}~}$} cuprinde un punct care nu este cuprins de {$C{~I~}$}. Daca notam cu {$R{~1~}$} raza cercului {$C{~I~}$} si cu {$R{~2~}$} raza cercului {$C{~I &#8746; {P}~}$}, atunci intersectia cercului {$C{~I &#8746; {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica ca {$&pi;$}.

* Datorita faptului ca {$P$} nu apartine circumferintei cercului {$C{~I ∪ {P}~}$}, punctele care definesc cercul {$C{~I ∪ {P}~}$} se afla printre punctele din setul {$I$}. Cum toate aceste puncte se afla in interiorul cercului {$C{~I~}$} si intersectia cercului {$C{~I ∪ {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica decat {$π$}, punctele care determina cercul {$C{~I ∪ {P}~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~I ∪ {P}~}$} care formeaza un arc de cerc de lungime mai mare {$π$} (cel albastru in rosu alaturata).

* Datorita faptului ca {$P$} nu apartine circumferintei cercului {$C{~I ∪ {P}~}$}, punctele care definesc cercul {$C{~I ∪ {P}~}$} se afla printre punctele din setul {$I$}. Cum toate aceste puncte se afla in interiorul cercului {$C{~I~}$} si intersectia cercului {$C{~I ∪ {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica decat {$π$}, punctele care determina cercul {$C{~I ∪ {P}~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~I ∪ {P}~}$} care formeaza un arc de cerc de lungime mai mare {$π$} (cel rosu in poza alaturata).

* Acest lucru intra in contradictie cu faptul ca cercul are raza minima. Astfel {$P$} trebuie sa se afle pe circumferinta cercului {$C{~I ∪ {P}~}$}.
Acum trebuie doar sa calculam cel mai mic cerc care contine punctele din setul I in interior si care are punctul {$P$} pe circumferinta. Vom extinde {$C{~I~}$} adaugand un nou parametru. Astfel notam cu {$C{~I,B~}$} cercul de raza minima ce contine setul {$I$} de puncte in interior si punctele din setul {$B$} pe circumferinta (pot exista si alte puncte pe circumferinta, dar cele din setul {$B$} sunt fortate). Cercul de raza minima care contine toate punctele va fi {$C{~S,Ø~}$}.

3684