(Categoria _Geometrie_, Autori _Savin Tiberiu_ si _Sima Mihai Cotizo_)

h2. Drepte

(toc){width: 27em}*{text-align:center} *Conţinut:*
* '**0. Introducere**':notiuni-de-geometrie-si-aplicatii#introducere
* '1. Arii':notiuni-de-geometrie-si-aplicatii/arii
** '- triunghi':notiuni-de-geometrie-si-aplicatii/arii#triunghi
** '- patrulater':notiuni-de-geometrie-si-aplicatii/arii#patrulater
** '- poligon':notiuni-de-geometrie-si-aplicatii/arii#poligon
* '2. Drepte':notiuni-de-geometrie-si-aplicatii/drepte
** '- elemente generale':notiuni-de-geometrie-si-aplicatii/drepte#general
** '- ecuaţii':notiuni-de-geometrie-si-aplicatii/drepte#ecuatii
** '- distanţa punct-linie':notiuni-de-geometrie-si-aplicatii/drepte#dpl
** '- distanţa punct-segment(semidreaptă)':notiuni-de-geometrie-si-aplicatii/drepte#dps
* '3. Punct în poligon':notiuni-de-geometrie-si-aplicatii/punct-in-poligon
** '- crossing-number':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#cn
** '- winding-number (?)':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#wn
** '- şmenuri':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#smen
* '4. Intersecţii de drepte şi segmente':notiuni-de-geometrie-si-aplicati/intersectii-drepte-si-segmente
* 5. Distanţe
** - între linii
** - între segmente şi semidrepte
** - cea mai mică distanţă între două mobile
* 6. Bounding ...
** - ... box
** - ... circle
* '7. Infaşurătoare convexă':notiuni-de-geometrie-si-aplicatii/infasuratoare-convexa
* 8. Puncte extreme şi distanţa poligon-linie
* 9. Tangente
* 10. Probleme de concurs

h3. {+Ecuatiile dreptei+}

h2(#introducere). 0. Introducere

Dreptele sunt locuri geometrice ce indeplinesc _ecuatia dreptei_. Cu alte cuvinte, ecuatia unei drepte reprezinta o relatie care este respectata de toate punctele aflate pe dreapta. Forma generala a ecuatiei unei drepte in sistemul $xOy$ este

**Geometria** (din greaca veche - {_geo_}=pământ, {_metria_}=a măsura) este partea matematicii care se ocupă cu problemele privind dimensiunile, forma şi poziţia figurilor. Introducerea coordonatelor de către René Descartes a dus la dezvoltarea geometriei analitice, a cărei scop devine studierea geometriei prin funcţii şi ecuaţii.

<tex>(d): a*x + b*y + c = 0</tex>

În problemele de olimpiadă este necesară cunoaşterea câtorva noţiuni şi idei de bază pentru a facilita găsirea unui algoritm eficient într-un timp scurt. Prezentul articol are ca scop explicarea acestor noţiuni privitoare la geometria plană (2D) şi studierea câtorva idei aplicate în problemele de concurs.

In cazul in care dreapta nu se afla in plan, fiecare punct $A$ ( $x1$ , $x2$ , $x3$ ,... $Xn$ ) (pentru n dimensiuni) de pe ea va indeplini conditiile:
<tex>
$$\left\{\begin{array}{lr}
x_1 = a_1\cdot x_0_1 + b_1; \\
x_2 = a_2\cdot x_0_2 + b_2; \\
... \\
x_n = a_n\cdot x_0_n + b_n;
\end{array}\right
$$
</tex>
 
A nu se confunda cu ecuatia planului:
 
<tex>(d): a*x + b*y + c*z + d = 0</tex>
 
*Feedback (Stefan):* Ai cam incurcat treburile. Asta e ecuatia planului. :)
*Edit (Cotizo):* Fixed :)
 
Pentru simplitate, de aici inainte ne vom referi numai la drepte in plan. De mentionat este faptul ca daca trecem pe $y$ in partea dreapta si impartim prin $-b$ (consideram un caz general, nu cel nefericit in care $b=0$), obtinem:
 
<tex>(d): y = \frac{(-a)}{b}*x + \frac{(-c)}{b}</tex>
 
<tex>(d): y = m*x + n</tex>, unde <tex>m=-\frac{a}{b}, n=-\frac{c}{b}</tex>
 
De asemenea, fiind date doua puncte $A(x{~1~}, y{~1~})$ si $B(x{~2~}, y{~2~})$, ecuatia dreptei determinate de ele se poate scrie
 
<tex>(d): \frac{x-x_1}{x_2-x_1} = \frac{y-y_1}{y_2-y_1}</tex>
 
Aceasta poate sa nu ne fie de prea mare ajutor, dar facand produsul mezilor cu extremii si desfacand parantezele vom obtine <tex>(d): (y_1-y_2)*x + (x_2-x_1)*y + (x_1*y_2-x_2*y_1) = 0</tex>, de unde putem deduce foarte usor cine sunt $a$, $b$, $c$ din scrierile precedente.
 
Se stie ca orice dreapta imparte planul in 2 semiplane: cel cu puncte pentru care, daca aplicam ecuatia, vom obtine o valoare strict pozitiva, si cel pentru care vom obtine o valoare strict negativa. De aceea, daca avem o dreapta data prin 2 puncte $A(x{~1~}, y{~1~})$ si $B(x{~2~}, y{~2~})$ de pe aceasta, atunci punctul $C(x{~3~}, y{~3~})$ va apartine dreptei $AB$ daca si numai daca
 
<tex>\left| \begin{array}{ccc}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
x_3 & y_3 & 1 \end{array} \right| = 0</tex>
 
*Feedback (Stefan):* Pare destul de trivial/pueril/nefondat raspunsul la intrebarea "de ce toate ecuatiile sunt (in general) egale cu 0?". Se poate gasi o motivatie mai buna sau se poate renunta la ea.
*Edit (Cotizo):* Fixed, de asemenea... fac topic pentru articol si bag acolo sugestiile + TODO existent ?
 
h3. {+Punctul de intersectie a 2 drepte+}
 
Dupa cum am vazut, o dreapta reprezinta un loc geometric. Sa zicem ca avem 2 drepte $d{~1~}$ si $d{~2~}$ si dorim sa aflam punctul $A(x, y)$ cu propietatea ca acesta apartine atat dreptei $d{~1~}$, cat si dreptei $d{~2~}$. Scriem ecuatiile celor 2 drepte:
 
<tex> a_1 * x + b_1 * y + c_1 = 0</tex>
<tex> a_2 * x + b_2 * y + c_2 = 0</tex>
 
Am ajuns astfel la un sistem de 2 ecuatii cu 2 necunoscute. Pentru a ajunge la niste formule mai directe de calculare a celor 2 coordonate vom inmulti prima relatie cu $b{~2~}$ si pe cea de-a doua cu $b{~1~}$.
 
<tex>a_1 * b_2 * x + b_1 * b_2 * y + c_1 * b_2 = 0</tex>
<tex>a_2 * b_1 * x + b_1 * b_2 * y + c_2 * b_1 = 0</tex>
 
Scadem cele doua relatii si ajungem la o singura ecuatie cu o singura necunoscuta:
 
<tex>(a_1 * b_2 - a_2 * b_1) * x + c_1 * b_2 - c_2 * b_1 = 0 \Leftrightarrow</tex>
<tex>x = \frac{\mbox{c_2 * b_1 - c_1 * b_2}}{\mbox{a_1 * b_2 - a_2 * b_1}}</tex>
 
O data ce l-am aflat pe $x$, descoperirea celeilalte coordonate e destul de triviala:
 
<tex>a_1*x + b_1 * y + c_1 = 0</tex>
<tex>y = \frac{\mbox{-c_1 - a_1 * x}}{\mbox{b_1}}</tex>
*TODO:* Fractiile arata prea mici cu LaTeX. Asta trebuie fixat cumva. FIXED (desi nu merge peste tot)
 
h3. {+Panta unei drepte+}
 
Panta unei drepte se poate defini ca fiind tangenta unghiului facut de dreapta cu orizontala, mai exact cu orice dreapta paralela cu axa $OX$. Ea se calculeaza astfel:
 
<tex>m = \frac{y_1-y_2}{x_1-x_2}</tex> sau <tex>m = -\frac{a}{b}</tex>
 
In a doua ecuatie $a$ si $b$ reprezinta coeficientii ecuatiei dreptei respective
 
<tex>(d): a*x + b*y + c = 0</tex>
 
Proprietati:
 {*} Doua drepte care au pantele egale sunt ori paralele ori confundate.
 {*} Doua drepte care au produsul pantelor egal cu $-1$ sunt perpendiculare.
 
h2. Distante
 
h3. {+Distanta dintre 2 puncte+}
 
Consideram $2$ puncte $A(x{~1~},y{~1~})$ si $B(x{~2~},y{~2~})$, si vrem sa aflam distanta dintre ele. Pentru a face acest lucru construim un al treilea punct $C(x{~2~},y{~1~})$ si observam ca triunghiul $ACB$ este dreptunghic iar distanta dintre punctele $AB$ este intocmai ipotenuza acestui triunghi. Folosind "teorema lui Pitagora":http://mathworld.wolfram.com/PythagoreanTheorem.html ajunge la urmatoarea formula:
 
<tex>d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}</tex>
 
h3. {+Distanta dintre un punct si o dreapta+}
 
Pentru a calcula distanta care ne trebuie noua vom calcula panta dreptei $d{~1~}$ notata cu $m{~1~}$. Acum vrem sa construim o dreapta $d{~2~}$ perpendiculara pe dreapta $d{~1~}$ care trece prin punctul $A$. Stim ca $m{~1~}*m{~2~}=-1$ si de aici aflam usor $m{~2~}$ (panta dreptei $d{~2~}$). In acest moment avem panta dreptei $d{~2~}$ si un punct care ii apartine. Avand aceste 2 informatii putem sa calculam usor ecuatia ei si punctul de intersectie cu dreapta $d{~1~}$ ({_Vezi capitolul Drepte_}). Distanta dintre dreapta si punct va fi egala cu distanta dintre punct si punctul de intersectie al celor $2$ drepte.
 
De asemenea exista si o formula pt a determina distanta de la un punct la o dreapta: considerand punctul $A(x{~0~},y{~0~})$ si dreapta $d:ax+by+c=0$, vom avea :
<tex> d(A,d) = \frac{|\mbox{a\cdot x_0+b\cdot y_0+c}|}{\mbox{\sqrt{a^2+b^2}}}</tex>
 
h3. {+Distanta dintre un punct si un segment+}
 
Sa presupunem un punct $A(x{~1~},y{~1~})$ si un segment determinat de punctele $B(x{~2~},y{~2~})$ si $C(x{~3~},y{~3~})$ si vrem sa aflam distanta dintre punct si segment.
 
$D$=min(dist({$A$},{$B$}),dist({$A$},{$C$})) in cazul in care perpendiculara din punctul $A$ pe dreapta $BC$ *nu* cade in interiorul segmentului $BC$, altfel distanta va fi egala cu distanta dintre punctul $A$ si dreapta $BC$, lucru care l-am tratat mai sus.
 
h2. Arii
 
h3. {+Aria unui triunghi+}
 
Aria unui triunghi determinat de punctele $A(x{~1~},y{~1~})$, $B(x{~2~},y{~2~})$ si $C(x{~3~},y{~3~})$ este egala cu :
 
<tex>A = \frac{1}{2} * abs \left( \left| \begin{array}{ccc}
\ x_1 & y_1 & 1\\
x_2 & y_2 & 1\\
x_3 & y_3 & 1\end{array} \right| \right)
</tex>
 
Unde $abs(x)$ reprezinta valoarea absoluta a lui $x$. Determinantul de mai sus poate fi folosit si pentru a vedea daca cele $3$ puncte sunt in sens invers sau direct trigonometric, el fiind negativ in cazul in care punctele sunt in sens invers trigonometric.
 
h3. {+Aria unui poligon+}
 
Aria unui poligon convex cu $n$ laturi o putem calcula foarte usor folosind formula pentru aria unui triunghi astfel.
 
<tex>\displaystyle \sum_{i=2}^{i<n} Arie(p_{1},p_{i},p_{i+1})</tex>
 
Unde <tex>Arie(p_{x},p_{y},p_{z})</tex> reprezinta aria triunghiului determinat de punctele $p{~x~}$, $p{~y~}$, $p{~z~}$.
 
Aria unui poligon concav se calculeaza la fel doar ca atunci cand calculam <tex>Arie(p_{1},p_{i},p_{i+1}</tex> renuntam la abs, si tinem minte semnul determinantului si luam valoarea absoluta dupa ce am calculat intreaga suma.
 
h2. Probleme rezolvate
 
h3. {+Infasuratoarea convexa+}
 
Enuntul problemei: Se da un set de puncte in plan, sa se determine un poligon convex de arie minima care contine toate punctele in interiorul sau.
Rezolvare: O posibila solutie este sa fixam punctul cu abscisa minima ,iar in caz de egalitate luam punctul cu ordonata minima, si sa translatam toate punctele pana cand acesta ajunge in punctul de coordonate $(0,0)$. Acum vom sorta punctele dupa formula <tex> \frac{y}{x} </tex> unde $x$ si $y$ sunt coordonatele punctului, iar in caz de egalitate dupa distanta fata de punctul $(0,0)$. In cazul nefericit in care $x=0$ vom considera ca <tex> \frac{y}{x} = INF </tex>. Apoi vom parcurge punctele in ordine si le vom introduce intr-o stiva. Inainte sa introducem un punct in stiva trebuie insa sa ne uitam daca nu cumva punctele $st[vf-1] , st[vf]$ si $P$ sunt in ordine invers trigonometrica ( $st$ - stiva, $vf$ - varful stivei, $P$ - punctul curent). Aici ne vom folosi de o alta proprietate a determinantului cu ajutorul caruia determinam aria unui triunghi. Mai exact vom calcula
<tex>D=\left| \begin{array}{ccc}
\ x_1 & y_1 & 1\\
x_2 & y_2 & 1\\
x_3 & y_3 & 1\end{array} \right|
</tex>
pentru $st[vf-1] = (x{~1~}.y{~1~}) , st[vf]= (x{~2~},y{~3~}), P(x{~3~},y{~3~})$. Daca $D$ este negativ atunci inseamna ca unghiul cu originea in $st[vf]$ face o intoarcere la dreapta si trebuie scos din stiva. Repetam procedeul pana cand ramanem cu un singur punct in stiva sau pana cand intalnim un $D >= 0$ dupa care adaugam punctul in stiva. Dupa ce am terminat e posibil ca poligonul nostru inca sa fie convex deoarece nu am verificat unghiul care are originea in $st[vf]$, asa ca il vom calcula pe $D$ pentru punctele $st[vf-1],st[vf],st[ 1 ]$ si vom scoate punctul din varf atata timp cat $D$ va fi negativ. Punctele ramase reprezinta infasuratoarea convexa a setului de puncte primite la intrare.
*devilkind*: E posibil sa nu fi inteles eu bine, dar la faza cand y/x e 0 cred ca trebui sa pui INF sau -INF in functie de semnul lui y. nush daca merge doar cu INF. - FIXED
 
h3. {+Punct in interiorul unui triunghi+}
 
Se da un triunghi prin coordonatele varfurilor. Se cere sa se afiseze pentru un set de $N$ puncte din plan daca apartin sau nu interiorului triunghiului. Pentru a rezolva aceasta problema, sa consideram triunghiul $ABC$ si punctul $P$, interior acestuia.
!http://infoarena.ro/notiuni-de-geometrie-si-aplicatii?action=download&file=triunghi.jpg!
 
Observam ca vectorii ( **AB**, **BP** ), ( **BC**, **CP** ), ( **CA**, **AP** ) vor realiza mereu acelasi tip de intoarcere (in acest caz spre stanga). De aceea, determinantii:
 
det( ((xA,yA,1),(xB,yB,1),(xP,yP,1)) ), det( ((xB,yB,1),(xC,yC,1),(xP,yP,1)) ), det( ((xC,yC,1),(xA,yA,1),(xP,yP,1)) )
 
trebuie sa aiba acelasi semn. In caz contrar, $P$ este in exteriorul triunghiului. In imaginea precedenta, se observa ca in cazul punctului $P'$, vectorii **BC**, **CP** fac o intoarcere la dreapta, deci determinantul corespunzator nu va avea acelasi semn cu ceilalti doi.
 
Aceasta idee poate fi generalizata pentru a fi determina daca un punct se afla in interiorul unui poligon convex in $O(N)$. Mai exact se calculeaza det( (x{~i~},y{~i~},1), (x{~i+1~}, y{~i+1~}, 1) (x{~p~},y{~p~},1) ) pentru $i$ luand valori de la $1$ la $N$ (cand $i$=={$N$} vom considera $i+1=1$) . Punctul P(x{~p~},y{~p~}) se afla in interiorul poligonului daca si numai daca toti determinanti au acelasi semn. ( "+" daca parcurgem poligonul in sens direct trigonometric, "-" altfel)
 
h3. {+Punct in interiorul unui poligon oarecare+}
 
Se da un poligon oarecare cu $N$ varfuri si un punct $P$ prin coordonatele carteziene. Se cere sa se determine daca punctul $P$ este in interiorul sau in exteriorul poligonului.
 
Se va trasa o semidreapta orizontala cu originea in punctul $P$. Daca aceasta semidreapta intersecteaza un numar impar de muchii ale poligonului, atunci punctul se afla in interiorul acestuia. Mentionam ca trebuie avut in vedere cazul in care semidreapta trece chiar printr-un varf de poligon (capat a doua muchii). Vom considera imaginea urmatoare:
 
 !http://infoarena.ro/notiuni-de-geometrie-si-aplicatii?action=download&file=poligon-raza.jpg!
 
In cazul punctului P{~1~}, respectiv P{~2~}, semidreptele intersecteaza 3, respectiv 1 latura (numere impare) deci punctele se afla in interior. Semidreapta corespunzatoare lui P{~3~} intersecteaza o latura si un varf de poligon. Pentru a rezolva acum aceasta problema, o solutie ar fi ca in loc sa alegem semidreapta orizontala, sa luam o semidreapta random, astfel posibilitatea ca ea sa intersecteze varfurile poligonului tinde spre 0. O alta solutie posibila - si mai usor de implementat - este sa consideram ca facand parte dintr-o latura doar punctul cu coordonata y mai mare. Se garanteaza astfel ca laturile care contin punctul de pe semidreapta vor fi numarate de numar par de ori (2 pt punctul de sus, 0 pt punctul de jos) si ca, implicit, nu vor afecta corectitudinea algoritmului.
 
 
*devilkind* - am dat eu o solutie care merge destul de bine ptr cazul in care semidreapta orizontala intersecteaza varfuri insa e cam jegoasa asa (cu semidrepte random si e cam aiurea). Era un smen in care considerai ca numai un capat al laturii face parte din ea, dar nu mai stiu cum era.
*EDIT Gcosmin (tip)* : in cazul in care semidreapta aleasa (sa zicem ca e paralela cu OX (e bine sa fie asa)) trece fix prin varful unui segment din poligon atunci segmentul il numaram doar daca semidreapta aleasa trece prin varful cu y-u mai mare. chestia asta scoate cazurile particulare si merge (da niste exemple si o sa vezi). e total aiurea sa iei o dreapta random pentru ca se complica mult treaba aiurea.
*cotizo* - multumim mult :) orice ajutor e binevenit :D pastram ambele variante pt ca si eu in concurs as fi bagat un random.
 
h3. {+Punct in poligon convex+}
 
Enunt: Se da un poligon convex cu $N$ laturi si apoi $M$ interogari caracterizate prin coordonatele unui punct $P$, iar dumneavoastra trebuie sa determinati rapid daca punctul respectiv se afla sau nu in interiorul poligonului.
 
*{+Solutia 1+}*
 
Se ia un varf al poligonului, si se traseaza cele $n-3$ diagonale care pornesc din el. Astfel poligonul nostru se imparte in mai multe triunghiuri. Vom adauga intr-un vector aceste drepte plus cele $2$ laturi care au originea in varful ales de noi si le sortam dupa panta. Cand primim un query vom cauta binar dupa panta si vom afla intre ce diagonale se incadreaza acesta si verificam daca punctul nostru se afla sau nu in triunghiul respectiv.
 
Sa luam un exemplu:
!notiuni-de-geometrie-si-aplicatii?polig12!
 
In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ reprezinta interogarile. Cu rosu sunt trasate diagonalele care delimiteaza sectoarele, si le vom tine ca drepte, sortate dupa panta, impreuna cu dreptele suport pentru cele 2 laturi care au un capat in punctul $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. Vom proceda asemanator si pentru celelalte interogari cu mentiunea ca trebuie sa avem grija la cazurile in care punctul nu se afla in nici unul din sectoare (P{~9~}), insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.
 
Aceasta solutie are complexitate O(NlogN + MlogN).
 
*{+Solutia 2+}*
 
O alta solutie este sa impartim planul in fasii. Astfel din fiecare varf al poligonului vom trasa o dreapta verticala. Acum pentru 2 drepte consecutive vom lua laturile care il intersecteaza si le vom sorta crescator dupa y (e clar ca aceste laturi nu se intersecteaza deci putem alege orice punct de pe latura si sa sortam dupa y-ul acestuia). Acum pentru a raspunde la interogari, vom face 2 cautari binare. Vom cauta odata sa vedem in ce fasie se incadreaza punctul nostru, iar apoi vom cauta inca odata binar sa vedem cate laturi din acea fasie sunt au y-ul mai mic decat punctul nostru. Daca acest numar este impar atunci punctul este in interior, altfel este in exterior. De mentionat ca aceasta solutie se poate aplica si la poligoane concave, de altfel in cazul poligoanelor convexe nu pot fi decat 2 laturi pe o fasie si nu ar mai fi nevoie de a doua cautare binara.
 
Sa luam un exemplu:
 
 
!notiuni-de-geometrie-si-aplicatii?polig22!
 
Observam cu rosu dreptele care delimiteaza fasiile verticale. De asemenea vedem ca punctul $P{~6~}$ are in fasia lui 2 laturi cu y-ul mai mic ca al lui si este in afara poligonului, spre deosebire de punctul $P{~7~}$ care are o singura latura cu y-ul mai mic ca al sau si este in interior.
Avantajul acestei metode este ca functioneaza si in cazul poligoanelor concave, insa are dezavantajul faptului ca pot exista interogari in care punctele sa se afle pe dreapta care delimiteaza fasiile. Practic aceasta metoda este echivalenta cu metoda explicata mai sus, pentru a verifica daca un punct se afla sau nu in interiorul unui poligon oarecare.
In cazul poligoanelor convexe complexitatea este aceeasi ca si la metoda de mai sus, insa in cazul poligoanelor concave complexitatea teoretica e O(N^2 log N + M log N).
*devilkind* uitativa putin la solutia asta ptr ca nu sunt foarte sigur pe complexitati - in special cand e vb de poligoane concave. Mie mi se pare ca aia e complexitatea insa e posibil sa ma insel
 
h1. TODO
 
*Feedback (Stefan):* Articolul trebuie imbracat intr-o forma mai prezentabila. Nu trebuie sa ramana doar o lista de formule si schelete de probleme. De asemenea, trebuie compactat si eliminate spatiile mari care il fac greu de citit.
*TODO:* Adaugati si centru de greutate a unui poligon si eventual explicati de ce merge formula de mai sus pt aria unui poligon concav.
 
sugestii de probleme de adaugat
 
punct in poligon:
  - punct in triunghi
  - punct in poligon oarecare
  - punct in poligon convex 2 solutii cautare binara dupa unghi sau dupa y
  - punct in poligon stelat
  - problema poligon din arhiva
 
infasuratoare convexa - DONE
  vreo 5 metode
 
gasire rapida a celui mai de sus punct din un poligon convex
 
determinare daca un poligon e convex sau concav
 
determinare a sensului de parcurgere a varfurilor unui poligon
 
intersectii de drepte cu un poligon convex
 
rotating calipers
  - perechea de puncte cele mai departate
  - dreptunghiul de arie minima ce contine un set de puncte
 
halplane intersection