Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-10-12 20:46:01.
Revizia anterioară Revizia următoare

Notiuni elementare de geometrie si aplicatii

(Categoria Geometrie, Autori Savin Tiberiu si Sima Mihai Cotizo)

Drepte

Ecuatiile dreptei

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

$(d): a*x + b*y + c = 0$

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:
$\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$

A nu se confunda cu ecuatia planului:

$(d): a*x + b*y + c*z + d = 0$

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:

$(d): y = \frac{(-a)}{b}*x + \frac{(-c)}{b}$

$(d): y = m*x + n$ , unde $m=-\frac{a}{b}, n=-\frac{c}{b}$

De asemenea, fiind date doua puncte A(x₁, y₁) si B(x₂, y₂), ecuatia dreptei determinate de ele se poate scrie

$(d): \frac{x-x_1}{x_2-x_1} = \frac{y-y_1}{y_2-y_1}$

Aceasta poate sa nu ne fie de prea mare ajutor, dar facand produsul mezilor cu extremii si desfacand parantezele vom obtine $(d): (y_1-y_2)*x + (x_2-x_1)*y + (x_1*y_2-x_2*y_1) = 0$ , 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₁, y₁) si B(x₂, y₂) de pe aceasta, atunci punctul C(x₃, y₃) va apartine dreptei AB daca si numai daca

$\left| \begin{array}{ccc} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{array} \right| = 0$

Punctul de intersectie a 2 drepte

Dupa cum am vazut, o dreapta reprezinta un loc geometric. Sa zicem ca avem 2 drepte d₁ si d₂ si dorim sa aflam punctul A(x, y) cu propietatea ca acesta apartine atat dreptei d₁, cat si dreptei d₂. Scriem ecuatiile celor 2 drepte:

$a_1 * x + b_1 * y + c_1 = 0$
$a_2 * x + b_2 * y + c_2 = 0$

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₂ si pe cea de-a doua cu b₁.

$a_1 * b_2 * x + b_1 * b_2 * y + c_1 * b_2 = 0$
$a_2 * b_1 * x + b_1 * b_2 * y + c_2 * b_1 = 0$

Scadem cele doua relatii si ajungem la o singura ecuatie cu o singura necunoscuta:

$(a_1 * b_2 - a_2 * b_1) * x + c_1 * b_2 - c_2 * b_1 = 0 \Leftrightarrow$
$x = \frac{\mbox{c_2 * b_1 - c_1 * b_2}}{\mbox{a_1 * b_2 - a_2 * b_1}}$

O data ce l-am aflat pe x, descoperirea celeilalte coordonate e destul de triviala:

$a_1*x + b_1 * y + c_1 = 0$
$y = \frac{\mbox{-c_1 - a_1 * x}}{\mbox{b_1}}$

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:

$m = \frac{y_1-y_2}{x_1-x_2}$ sau $m = -\frac{a}{b}$

In a doua ecuatie a si b reprezinta coeficientii ecuatiei dreptei respective

$(d): a*x + b*y + c = 0$

Proprietati:
• Doua drepte care au pantele egale sunt ori paralele ori confundate.
• Doua drepte care au produsul pantelor egal cu -1 sunt perpendiculare.

Distante

Distanta dintre 2 puncte

Consideram 2 puncte A(x₁,y₁) si B(x₂,y₂), si vrem sa aflam distanta dintre ele. Pentru a face acest lucru construim un al treilea punct C(x₂,y₁) si observam ca triunghiul ACB este dreptunghic iar distanta dintre punctele AB este intocmai ipotenuza acestui triunghi. Folosind teorema lui Pitagora ajunge la urmatoarea formula:

$d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$

Distanta dintre un punct si o dreapta

Pentru a calcula distanta care ne trebuie noua vom calcula panta dreptei d₁ notata cu m₁. Acum vrem sa construim o dreapta d₂ perpendiculara pe dreapta d₁ care trece prin punctul A. Stim ca m₁*m₂=-1 si de aici aflam usor m₂ (panta dreptei d₂). In acest moment avem panta dreptei d₂ si un punct care ii apartine. Avand aceste 2 informatii putem sa calculam usor ecuatia ei si punctul de intersectie cu dreapta d₁ (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₀,y₀) si dreapta d:ax+by+c=0, vom avea :
$d(A,d) = \frac{|\mbox{a\cdot x_0+b\cdot y_0+c}|}{\mbox{\sqrt{a^2+b^2}}}$

Distanta dintre un punct si un segment

Sa presupunem un punct A(x₁,y₁) si un segment determinat de punctele B(x₂,y₂) si C(x₃,y₃) 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.

Arii

Aria unui triunghi

Aria unui triunghi determinat de punctele A(x₁,y₁), B(x₂,y₂) si C(x₃,y₃) este egala cu :

$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)$

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.

Aria unui poligon

Aria unui poligon convex cu n laturi o putem calcula foarte usor folosind formula pentru aria unui triunghi astfel.

$\displaystyle \sum_{i=2}^{i<n} Arie(p_{1},p_{i},p_{i+1})$

Unde $Arie(p_{x},p_{y},p_{z})$ 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 $Arie(p_{1},p_{i},p_{i+1}$ renuntam la abs, si tinem minte semnul determinantului si luam valoarea absoluta dupa ce am calculat intreaga suma.

Probleme rezolvate

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 $\frac{y}{x}$ 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 $\frac{y}{x} = INF$ . 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
$D=\left| \begin{array}{ccc} \ x_1 & y_1 & 1\ x_2 & y_2 & 1\ x_3 & y_3 & 1\end{array} \right|$
pentru st[vf-1] = (x₁.y₁) , st[vf]= (x₂,y₃), P(x₃,y₃). 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

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.

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)) )
cotizo - :) trebuie LaTeX :)

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)

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:

In cazul punctului P₁, respectiv P₂, semidreptele intersecteaza 3, respectiv 1 latura (numere impare) deci punctele se afla in interior. Semidreapta corespunzatoare lui P₃ 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.

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:

In imaginea de mai sus punctele P₁,..P₆ reprezinta varfurile poligonului iar punctele P₇, P₈, P₉ 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₁. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul P₈ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor P₄ si P₅. Astfel vom verifica daca punctul P₈ se afla in interiorul triunghiului determinat de punctele P₁, P₄, P₅. 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₉), 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:

Observam cu rosu dreptele care delimiteaza fasiile verticale. De asemenea vedem ca punctul P₆ are in fasia lui 2 laturi cu y-ul mai mic ca al lui si este in afara poligonului, spre deosebire de punctul P₇ 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). Acest algoritm poate fi aplicat in rezolvarea problemei poligon din arhiva de probleme.

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
cotizo da e corect - asta e si rezolvarea problemei "poligon"

Cele mai departate doua puncte

Enunt: Se da o multime de N puncte in plan. Sa se determine perechea de puncte pentru care distanta dintre cele doua este maxima.

O prima solutie ar fi calcularea distantei intre fiecare pereche de 2 puncte si pastrarea ca solutie a perechei cu distanta maxima. Desigur, aceasta solutie are complexitate O(N²) si nu este eficienta.

O rezolvare mai eficienta porneste de la observatia ca perechea cautata se afla in mod evident pe infasuratoarea convexa a punctelor. Vom incepe prin a fixa un punct oarecare pe infasuratoare si vom parcurge restul punctelor de pe infasuratoare in oricare sens (trigonometric sau orar). Distanta intre punctul fixat si punctul la care am ajuns in parcugere va creste pana la un moment dat si apoi va incepe sa scada. Retinem punctul aflat la distanta maxima fata de cel fixat. Vom avea acum perechea de puncte X (punctul fixat initial), Y (cel mai departat punct de acesta) care este o posibila solutie.

Apoi vom pleca de la X si vom continua sa parcurgem restul punctelor de pe infasuratoare in sensul ales initial. Pentru fiecare punct din aceasta parcurgere, vom incerca sa gasim punctul de pe infasuratoare pentru care se obtine o distanta maxima. Daca am reface algoritmul folosit pentru X am obtine o complexitate de O(N²) ceea ce este ineficient. Ca sa reducem complexitatea, notam punctul la care am ajuns in parcurgere cu A, si observam ca pentru oricare punct dintre A si Y in sensul ales, distanta intre acesta si A va fi mai mica decat distanta dintre X si Y, asadar nu poate fi o solutie. Astfel, pentru fiecare punct A, parcurgem punctele incepand cu punctul Y in sensul ales pana cand distanta dintre A si punctul la care am ajuns va incepe sa scada. Pastram distanta maxima, inlocuim perechea X, Y cu perechea A, cel mai departat punct de el, verificam daca este mai buna decat solutia obtinuta pana acum si apoi trecem la urmatorul punct A.

Complexitatea acestei solutii este de O(N*log N) pentru infasuratoare si O(N) pentru aflarea celor mai departate 2 puncte asadar O(N*log N).

Algoritmul asta e gresit sunt cazuri pe care nu merge. Sunt poligoane pe care daca mergi cu al 2-lea punct la inceput distanta creste, apoi scade apoi creste si iar scade. De aia tii tot timpu un segment pe contur si cauti cel mai departat punct de segment. E un algoritm ce il bushesti usor si ar merita explicat clar si explicat de ce nu merge cu 2 puncte.

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 [ok]
- punct in poligon oarecare [ok]
- punct in poligon convex 2 solutii cautare binara dupa unghi sau dupa y [ok]
- punct in poligon stelat [ce e poligon stelat?] poligon ce are un punct din care vezi tot interiorul http://www.spoj.pl/problems/FSHEEP/
- problema poligon din arhiva [ok, cred]

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 [ok i guess]
- dreptunghiul de arie minima ce contine un set de puncte

halplane intersection

infoarena informatica de performanta