Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Exercitii din Introducere in algoritmi (Geometrie computationala)  (Citit de 9520 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« : Decembrie 31, 2010, 18:27:26 »

Am doua intrebari la care nu am reusit sa gasesc un raspuns, asa ca apelez la voi  Fool :

1) Cum compar unghiurile polare a doua puncte P1 si P2 in raport cu un al treilea P0 folosind produsul incrucisat (ex. 35.1-2 (prima editie) si ex. 33.1-3 (a doua editie) ).

Off-topic : stiu ca se poate calcula unghiul polar a lui P1 in raport cu P0 si asa : m = arctg( (y1 - y0 ) / ( x1 - x0 ) ) . E corect ? Smile

2) Cum imi dau seama in timp liniar daca un set de puncte {p0, p1, ..., pn-1} formeaza un poligon convex. In carte scrie ca daca verificam sa avem numai intoarceri la stanga sau numai intoarceri la dreapta nu produce intotdeauna rezultatul corect. Sunt nedumerit ca eu nu am reusit sa gasesc un contraexemplu. (ex. 35.1-4 (prima editie) si ex. 33.1-5 (a doua editie) ).

Multumesc anticipat !

Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #1 : Decembrie 31, 2010, 22:02:26 »

Am doua intrebari la care nu am reusit sa gasesc un raspuns, asa ca apelez la voi  Fool :

1) Cum compar unghiurile polare a doua puncte P1 si P2 in raport cu un al treilea P0 folosind produsul incrucisat (ex. 35.1-2 (prima editie) si ex. 33.1-3 (a doua editie) ).

Off-topic : stiu ca se poate calcula unghiul polar a lui P1 in raport cu P0 si asa : m = arctg( (y1 - y0 ) / ( x1 - x0 ) ) . E corect ? Smile

2) Cum imi dau seama in timp liniar daca un set de puncte {p0, p1, ..., pn-1} formeaza un poligon convex. In carte scrie ca daca verificam sa avem numai intoarceri la stanga sau numai intoarceri la dreapta nu produce intotdeauna rezultatul corect. Sunt nedumerit ca eu nu am reusit sa gasesc un contraexemplu. (ex. 35.1-4 (prima editie) si ex. 33.1-5 (a doua editie) ).

Multumesc anticipat !

1) (x1-x0)*(y2-y0)-(x2-x0)(y1-y0)>0  rezulta ca unghiul polar al lui P2 e mai mare ca unghiul polar al  lui P1.
2) Cred ca ceea ce vrei este in desenul de mai jos:
« Ultima modificare: Decembrie 31, 2010, 22:14:11 de către Dragos » Memorat
mrares
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #2 : Ianuarie 01, 2011, 23:39:55 »

Pe desenul ala ... numai cu intoarceri la stanga si da bine.

Iei oricare 2 puncte prima oara, si urmatorul sa fie la stanga sau la dreapta fata de dreapta ... urmatorul sa fie la fel la stanga sau la dreapta (cum ai ales inainte) fata de ultima dreapta formata ... bla bla bla etc tra la la .
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #3 : Ianuarie 02, 2011, 10:49:19 »

Citat
Pe desenul ala ... numai cu intoarceri la stanga si da bine.

La ce te referi ca "da bine" ? Ala e un contraexemplu care demonstreaza ca algoritmul pe care l-am spus eu este gresit.

Citat
Iei oricare 2 puncte prima oara, si urmatorul sa fie la stanga sau la dreapta fata de dreapta ... urmatorul sa fie la fel la stanga sau la dreapta (cum ai ales inainte) fata de ultima dreapta formata ... bla bla bla etc tra la la .

Explica mai detaliat si fii mai concis. Cineva care vede asta nu intelege nimic daca nu stie dinainte despre ce este vorba.

@Dragos good post  Smile
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #4 : Ianuarie 02, 2011, 12:06:55 »

Algoritmul cu intoarcerile se aplica abea dupa ce ai ordonat punctele dupa unghiul pe care-l facea dreapta care le unea cu un anumit punct de referinta (in general cel din stanga jos) cu axa Ox. Nu ar fi conditia asta suplimentara suficienta?
Memorat
mrares
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #5 : Ianuarie 02, 2011, 15:28:06 »

iei dreapta 1-2, 3 e la stanga.. iei dreapta 2-3, 4 e la stanga.. iei dreapta 3-4, 5 e la stanga.. iei dreapta 4-5, 6 e la stanga ... etc
primele 2 puncte selectate nu conteaza.. poti incepe si din 5-6 ...
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #6 : Ianuarie 02, 2011, 17:42:10 »

Da si nu e corect ! Dupa acest algoritm iti da ca poligonul din poza este convex si nu e !

@Sima Cotizo da, dar daca sortez nu mai am O(n).

LE :
Cred ca am gasit o solutie.
Pasul 1) Luam ca punct de referinta P0, primul din lista punctelor.
Pasul 2) Pentru un i=1,n-1 trebuie ca unghiurile polare ale varfurilor Pi sa creasca sau sa descresca, dar nu ambele.

In exemplul lui Dragos, daca luam P1 ca punct de referinta, unghiurile polare cresc pana in P5 iar in P6 unghiul polar este mai mic decat in P5 => poligon neconvex.
« Ultima modificare: Ianuarie 02, 2011, 18:16:31 de către George Popoiu » Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #7 : Ianuarie 02, 2011, 23:56:04 »

@Sima Cotizo da, dar daca sortez nu mai am O(n).
Nu sortezi, doar verifici ca o lista de puncte sa fi fost deja sortata crescator dupa o proprietate.
Imi cer scuze daca nu am fost perfect atent la discutie si gresesc in reply-urile mele.

PS: dupa ce am citit problema in Cormen, cred ca metoda pe care am sugerat-o ar respecta toate conditiile. Re-explic:
1) afla punctul stanga-jos (sa ii zicem p0)
2) parcurgi lista de puncte; pentru trei puncte consecutive pi, pi+1, pi+2 (ca in carte, indicii sunt modulo n), verifici ca unghiurile pe care le fac cu p0  sa fie in ordine crescatoare / descrescatoare, iar toate intoarcerile sa fie la stanga / dreapta.

Timpul e liniar (doar parcurgi lista), nu sunt sigur ca este si complet. Dar momentan exemplul dat de apocalypto nu mai trece.
« Ultima modificare: Ianuarie 03, 2011, 00:10:08 de către Sima Cotizo » Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #8 : Ianuarie 03, 2011, 09:42:45 »

Mult mai clar, multumesc !

PS : eu verificam doar daca unghiurile polare cresc / descresc.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #9 : Februarie 01, 2011, 23:33:53 »

Revin cu o nelamurire (mai mult o nesiguranta, mai vreau o parere Very Happy ) si un exercitiu care nu mi-a iesit  Confused.

1) In Introducere in algoritmi, la capitolul Geometrie Computationala este prezentat un algoritm de complexitate O(NlogN) pentru a determina daca exista o intersectie intre N segmente din plan. (Capitolul 35.2 in editia 1). In carte se sugereaza folosirea Red-Black-Trees pentru a retine starile liniei de baleiere, dar sunt foarte greu de implementat, sa nu mai vorbim de cazul cand esti sub presiune si nu mai ai foarte mult timp. In esenta ne trebuie o structura asupra careia sa se poate efectua operatiile Deasupra(s) si Dedesubt(s) in O(logN) si eu m-am gandit ca ar merge si cu Treapuri, din moment ce mentin invariantul arborilor de cautare, putem afla primul element de dupa s, si dinaintea lui s in parcurgerea inordine in O(logN). E corect ce zic ?  Confused

2) In exercitiul 35.2-6 se cere sa se afle daca oricare 2 discuri din N discuri din plan se intersecteaza in O(NlogN). Discurile se dau prin coordonatele centrului si raza. La asta chiar ca nu am nici o idee. sad

Tin sa multumesc in acest post pentru raspunsurile clare pe care le-am primit pana acum in acest topic si sa multumesc anticipat !

PS : Scuze daca intrebarile suna scolaresti, dar m-am gandit destul de bine si mult inainte sa postez.

LE : Am reusit sa fac exercitiul pana la urma.  Smile
« Ultima modificare: Februarie 04, 2011, 19:12:19 de către George Popoiu » Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #10 : Februarie 06, 2011, 22:39:59 »

LE : Am reusit sa fac exercitiul pana la urma.  Smile

Cum ai facut?
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #11 : Februarie 07, 2011, 08:35:39 »

Retii razele diametrele paralele cu Ox ca segmente si sortezi punctele dupa x si in caz de egalitate dupa y. De aici faci ca la intersectia de segmente in O(logN) numai ca la introducerea si scoaterea segmentelor din structura de date (arbore echilibrat, daca vrei complexitate O(logN)) verifici pentru intersectia discurilor, nu a segmentelor. Cred ca e corect, nu am gasit o solutie oficiala la problema aia pe net, de aia am si postat.  Smile
« Ultima modificare: Februarie 08, 2011, 14:11:17 de către George Popoiu » Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #12 : Februarie 08, 2011, 10:57:11 »

Da dar la tine daca cercul i nu se intersecteaza cu cercul i+1 atunci mai are vreo sansa sa se intersecteze cu cercul i+2?
In cazul de mai jos are:

Acum poate omit eu ceva din mesajul tau.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #13 : Februarie 08, 2011, 14:10:49 »

Am modificat postul, ma refeream la diametre, nu raze.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines