•popoiu.george
|
|
« : Decembrie 31, 2010, 18:27:26 » |
|
Am doua intrebari la care nu am reusit sa gasesc un raspuns, asa ca apelez la voi : 1) Cum compar unghiurile polare a doua puncte P 1 si P 2 in raport cu un al treilea P 0 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 P 1 in raport cu P 0 si asa : m = arctg( (y 1 - y 0 ) / ( x 1 - x 0 ) ) . E corect ? 2) Cum imi dau seama in timp liniar daca un set de puncte {p 0, p 1, ..., p n-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
|
|
« 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 : 1) Cum compar unghiurile polare a doua puncte P 1 si P 2 in raport cu un al treilea P 0 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 P 1 in raport cu P 0 si asa : m = arctg( (y 1 - y 0 ) / ( x 1 - x 0 ) ) . E corect ? 2) Cum imi dau seama in timp liniar daca un set de puncte {p 0, p 1, ..., p n-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
Mesaje: 21
|
|
« 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
|
|
« Răspunde #3 : Ianuarie 02, 2011, 10:49:19 » |
|
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. 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
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« 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
Mesaje: 21
|
|
« 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
|
|
« 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
|
|
« 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 p 0) 2) parcurgi lista de puncte; pentru trei puncte consecutive p i, p i+1, p i+2 (ca in carte, indicii sunt modulo n), verifici ca unghiurile pe care le fac cu p 0 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
|
|
« 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
|
|
« Răspunde #9 : Februarie 01, 2011, 23:33:53 » |
|
Revin cu o nelamurire (mai mult o nesiguranta, mai vreau o parere ) si un exercitiu care nu mi-a iesit . 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 ? 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. 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.
|
|
« Ultima modificare: Februarie 04, 2011, 19:12:19 de către George Popoiu »
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #10 : Februarie 06, 2011, 22:39:59 » |
|
LE : Am reusit sa fac exercitiul pana la urma. Cum ai facut?
|
|
|
Memorat
|
|
|
|
•popoiu.george
|
|
« 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.
|
|
« Ultima modificare: Februarie 08, 2011, 14:11:17 de către George Popoiu »
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« 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
|
|
« Răspunde #13 : Februarie 08, 2011, 14:10:49 » |
|
Am modificat postul, ma refeream la diametre, nu raze.
|
|
|
Memorat
|
|
|
|
|