Geometrie - clasa a 8 a

[•miculprogramator]

Salut ! Sunt in clasa a 8-a si vreau sa ma apuc de studiat geometria computationala, am vazut ca se cere pentru Olimpiada. Am lucrat destul de putine probleme de acest fel si nu prea stiu pe ce trebuie sa ma axez ...

Mi-ati putea da niste sfaturi sau materiale de pe care sa invat ?

[•pauldb]

La clasa a 8-a nu cred ca pot veni probleme prea serioase de geometrie computationala. Ce ar trebui sa stii ar fi notiuni de baza: distanta intre doua puncte, aria unui triunghi (poligon), ecuatia dreptei, etc.

Exista pe infoarena un articol de geometrie deocamdata neterminat care trateaza si ce cauti tu.

In rest, ai putea sa incerci sa lucrezi probleme din arhiva: drepte2, copaci, trapez, triunghi2, triang, geometry, geom, points, cercuri, campion, etc.

[•miculprogramator]

M-am uitat si pe articolul cu puncte laticiale .

La aria unui triunghi in care am numai pct de coordonate pot  face distanta dintre 2 puncte si apoi sa aplic formula lui Heron sau ar fi mai bine sa invat determinanti ?  

[•Mishu91]

Poți face și cu Heron aria unui triunghi, dar este destul de complicat și poți pierde la precizie. Cel mai bine faci aria cu determinanți (însă având în vedere că ești a8a, cred că ești cam tânără pentru determinanți).

[•pauldb]

Este de preferat sa calculezi aria folosind formula cu determinanti. Formula este mai simpla si nu apar probleme de precizie (exista o singura impartire la 2). La Heron ai de calculat radicali, care pot produce probleme mai serioase de precizie. (Am cam repetat ce deja scrisese Andrei, el a postat in timp ce eu scriam.)

In plus, nu trebuie sa inveti determinanti in general. Trebuie doar sa stii cum sa calculezi determinantii de ordin <= 3 (poti sa ii vezi ca pe niste formule, care nu sunt greu de retinut). Acesti determinanti au multe aplicatii in geometrie si ti se vor dovedi utili mai departe.

[•miculprogramator]

Redeschid subiectul pentru ca am o nelamurire legata de ecuatia unei drepte care trece prin 2 puncte date A (xA, yA) si B (xB, yB) :

(x - Xa) (yB - yA) == (xB - xA) (y-yA)

Nu inteleg cine sunt x si y in cazul asta, cand e vorba doar de xA, yA, xB, yB.

[•Mishu91]

Oricare alt punct de pe dreapta respectivă. Cred că este mai explicită relația în forma (x - XA)/(y - YA) = (XB - XA)/(YB-YA), pentru că (XB - XA)/(YB - YA) este panta dreptei respective (cotangenta unghiului pe care dreapta o face cu dreapta Ox).

[•miculprogramator]

Acum am inteles. Deci folosesc una din relatiile de mai sus daca vreau sa verific daca punctul M de coord (x, y) se afla pe dreapta determinata de pct A (xA, yA) si B (xB, yB). 

Am invatat, repetat si aplicat cam tot ce ati scris voi aici, ar mai fi ceva?

[•pauldb]

Ce spune Andrei e gresit. Panta unei drepte este tangenta unghiului determinat de dreapta si axa Ox.

Ecuatia dreptei are mai multe forme, cea mai intuitiva dintre ele dupa parerea mea este y = mx + n, unde m este panta dreptei dorite, n este ordonta prin care taie dreapta axa Oy. Perechile de coordonate (x, y) care respecta egalitatea de mai sus este multimea punctelor din plan aflate pe dreapta respectiva. Panta dreptei este evident m = (yB-yA) / (xB - xA) (duci o paralela prin B la Ox si se observa ca unghiul format de segmentul AB cu dreapta paralela este congruent cu unghiul format de dreapta AB cu Ox si deci si tangentele sunt egale). Cum punctul (xA, yA) apartine si el dreptei, putem determina n din relatia yA = m*xA + n (m e deja stiut). Inlocuind valorile astfel obtinute, vei vedea ca vei obtine egalitatea scrisa de tine mai sus.

Forma y = mx + n este mai utila, deoarece cel mai frecvent vei dori o forma de a retine o dreapta si nu o formula cu care sa determini daca un punct apartine dreptei (ceea ce oricum se poate verifica si cu y = mx + n).

Poti sa rezolvi probleme mai complicate de geometrie daca doresti cum ar fi drepte3, regiuni sau sa citesti despre algoritmi mai avansati: infasuratoare convexa, cele mai apropiate/departate puncte din plan, etc. Poti, de asemenea, sa incepi sa inveti si alte lucruri din alte domenii.

[•Mishu91]

Dap, întradevăr panta este tangenta, dar în general este același lucru, dacă iei tangenta sau cotangenta.

[•miculprogramator]

Multumesc mult, o sa ma uit si pe celelalte articole.

Am vazut la mai multe probleme ca lucrul cu nr reale poate aduce pierderi de punctaj, din cauza preciziei. Este mai ok sa lucrez pe int si sa nu mai fac impartirile (ex la aria unui triunghi cu determinanti) ?

[•nash]

In primul rand nu trebuie sa te gandesti la "aria cu determinanti" ci trebuie sa te gandesti la arie... Ca sa fiu mai explicit trebuie sa te gandesti la produs vectorial.  A X B (  A si B -> vectori ) ... A(xa,ya) B(xb,yb)

ai asa :

A X B = |A| * |B| * sin(alpha ) // unde alpha este unghiul dintre cei doi vectori (A,B) . ( e bine de sa desenezi ca o sa fie intuitiv )
produsul vectorial nu este comutativ : A X B != B X B deoarece  A X B = |A|*|B|*sin(A,B) si B X A = |B| * |A| * sin( B , A) => |A| * |B| * sin(A,B ) = - |B|*|A|*sin(B,A) // doarece functia sin este functie inpara adica sin( - alpha ) = - sin(alpha) .

|A| = modulul vectorului , adica lungimea vectorului, adica sqrt(A.x*A.x + B.y*B.y)

Daca scriem vectorii A si B ca sume de vectori pe cele doua axe si facem produsul vectorial ajungem la :

A(xa,ya) * B(xb,yb) * sin(alpha) = xa * xb * sin(xa,xb) + xa * yb * sin(xa , yb ) + ya * xb * sin(ya, xb) + ya * yb * sin(ya,yb)

sin( 0 ) = 0
sin (90 grade ) = 1
sin(-90 grade ) = -1

rezulta
xa * xb * sin(xa,xb)  = 0
ya * yb * sin(ya,yb) = 0

xa * yb * sin(xa , yb ) = xa * yb;
ya * xb * sin(ya, xb) = - ya * xb;

de unde rezulta ca expresia este :
A * B * sin(alpha)  = xa * yb - ya * xb ;   // vestitul determinant care calculeaza aria paralelogramului format de adunarea vectorilor A si B . Daca vrei aria triunghiul ... trebuie sa imparti la 2.

Aria unui triunghi este baza  * inalatimea  /2  . Baza o poti considera un vectori si inaltimea este celalalta vector * sinus( alpha) . de unde rezulta ca produsul vectorial / 2 este aria triunghiului dintre cei doi vectori.
Daca nu iti este clara de unde vine faptul ca este aria ... iti pot arata mai clar . Gasesti foarte frumos explicat in Cormen la capitolul de geometrie computationala toate chestiile astea si daca sti sa lucrezi un pic cu vectori nu e greu deloc.

A se observa ca daca ai o intoarcere in sens trigonometric aria este pozitiva daca ai intoarcere in sens invers trigonemetric atunci aria este negativa ( din cauza sinusului care are unghi negativ ... ) chestia asta te poate ajuta sa vezi cum este un punct fata de o drepta. Daca ai arie pozitiva este "deasupra" .. daca ai arie negativa este "sub dreapta". [ faci produs vectorial dintre vectorii determinati de doua puncte care se gasesc pe drepta si un punct dintre cele doua si punctul exterior ]. Daca aria e 0 atunci punctul este pe drepta.

// sper sa nu fi gresit vre-un indice

Despre ecuatia dreptei :

Orice drepta poate fi determinata de un punct si o panta, de doua puncte, de un punct si un vectori...

Consideram ca avem un punct fixat A(x0,y0) o panta fixata "m" si un punct B(x,y) care se plimba pe drepta. atunci panta dreptei este :
 m = (y - y0) / ( x - x0) care este si tangenta daca desenezi si vezi triunghiul.
se poate scrie si asa :
(x - x0)* m  = (y - y0)
daca desfacem ajungem la  :
x*m - y + y0 - x0*m = 0;
Forma generala a ecuatiei dreptei este :  A*X + B*Y + C = 0; de unde rezulta ca m = A , -1 = B si y0 - x0*m = C

Pentru cazul in care ai ecuatia dreptei determinata de doua puncte fixate : A(x0,y0)  si B(x1,y1) avem :
m = (x0 - x1) / (y0 - y1) // panta ecuatiei.
Avem panta si un punct problema se reduce la explicatia deasupra.

Ai un vecor V(x,y) si pun punct P care fiseaza vectorul. Calculeazi x/y ( panta vectorului , adica panta dreptei tale ) si ajungi in cazul 1 adica ai panta si un punct.

Referitor la chestia cu int vs. float. In primul rand  cand ai impartire la 2 rezultatul se termina in .0 sau in .5 deci nu trebuie sa iti faci griji pentru precizie. Daca in problema trebuie sa faci comparatii intre doua produse vectoriale ... evident daca a < b => a / 2  < b/2 .
Frumusetea produsului vectorial este data de faptul ca daca ai puncte de coordonare numere intregi rezultatul se termina in .0 sau in 0.5 ( aria ) .