Notiuni elementare de geometrie si aplicatii

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

• Conţinut:
• 0. Introducere
• 1. Arii
  • - triunghi
  • - patrulater
  • - poligon
• 2. Drepte
  • - elemente generale
  • - ecuatii
  • - distanta punct-linie
  • - distanta punct-segment(semidreapta)
• 3. Punct in poligon
  • - crossing-number
  • - winding-number (?)
  • - smenuri
• 4. Intersectii de drepte si segmente
• 5. Distante
  • - intre linii
  • - intre segmente si semidrepte
  • - cel mai mica distanta intre doua mobile
• 6. Bounding ...
  • - ... box
  • - ... circle
• 7. Infasuratoare convexa
• 8. Puncte extreme si distanta poligon-linie
• 9. Tangente

Drepte

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:

Arii

Probleme rezolvate

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