[ Dusannn @ 22.12.2004. 16:14 ] @
Zdravo svima!

C++ problem...

Na osnovu niza tacaka formira se mnogougao (to je ok), treba naci povrsinu tog mnogougla (i to je ok...donekle) medjutim problemi nastaju u slucaju nekonveksnog mnogougla.
Poceo sam tako sto sam ga izdelio na trouglove ( metod funkcionise), medjutim u slucaju nekonveksnih mnogouglova desava se da je neki trougao "napolju" (tj. van povrsine mnogougla). On ne sme ulaziti u konacnu sumu. Po kom kriterijumu da to prepozna u petlji za povrsinu i da ga kao takvog ne sabira?
Unapred zahvalan na svakoj ideji.
D.
[ filmil @ 22.12.2004. 16:28 ] @
Citat:
Na osnovu niza tacaka formira se mnogougao (to je ok), treba naci povrsinu tog mnogougla (i to je ok...donekle)
Postoji jednostavna formula za računanje površine mnogougla. Ako imaš tačaka sa koordinatama
, površina je data sa:

.

Formula je posledica Grin-Rimanove teoreme (ako se dobro sećam tako se zove) i radi za svaki mnogougao, bez obzira da li je konveksan ili ne.

f
[ Dusannn @ 22.12.2004. 16:36 ] @
Veliko hvala, Filipe!
Da li bi mozda znao metod kojim se odredjuje pripadnost tacke (x,y) mnogouglu sa n definisanih temena (xn,yn)...i problem je resen
[ filmil @ 22.12.2004. 16:41 ] @
Ako ti je pripadnost trebala za računanje površine onda si slobodan pošto po gornjoj formuli ne moraš da znaš pripadnost.

Ako ti pripadnost treba sama po sebi, onda imaš problem.

Ne znam da li postoji pametniji način u opštem slučaju, osim po definiciji: tačka je u mnogouglu ako poluprava povučena iz te tačke seče mnogougao neparan broj puta. Kad to znaš, onda samo ostaje da napišeš ispravan program koji ovo računa. (ovo pod uslovom da ne postoji neki drugi, elegantan način da se stvar uradi).

Za konveksan mnogougao imaš prečicu: samo treba da ispitaš da li se tačka nalazi sa iste strane svih stranica kao i težište.

Ove i razne druge geometrijske štosove imali smo na forumu Matematika pa potraži tamo.

f


[Ovu poruku je menjao filmil dana 22.12.2004. u 17:46 GMT+1]
[ Dusannn @ 22.12.2004. 16:44 ] @
Sto se tice pripadnosti tacke, dao si mi ideju:

1. Izracunati povrsinu trouglova napravljenih od svaka dva susedna temena i te tacke.

2. Ako ta povrsina prevazilazi povrsinu mnogougla, onda je van istog.

3. a ako tako izracunata bude jednaka povrsini monogougla => tacka pripada monogouglu.

Vredi li to za nekonveksne trouglove, posto ce neminovno delovi tih elementarnih trouglova morati da budu van povrsi mnogougla?
[ Dusannn @ 22.12.2004. 16:45 ] @
...ispravka...
...Vredi li to za nekonveksne mnogouglove?
[ zi:: @ 22.12.2004. 21:15 ] @
Filip je već rekao ideju za algoritam, a evo i malo detaljnije:

http://www.geometryalgorithms....orithm_0103/algorithm_0103.htm

Generalno, pregledaj ovaj sajt ako te interesuju geometrijski algoritmi, odličan je. Meni je pomogao već više puta.
[ filmil @ 22.12.2004. 21:34 ] @
Grafički algoritmi, odgovor na ovo i još puno pitanja: http://www.faqs.org/faqs/graphics/algorithms-faq/

f

p.s: Ključne reči: grafika, algoritam, tačka, poligon, računarska grafika, mnogougao. (da pomognemo malo Guglu).
[ Dusannn @ 23.12.2004. 01:28 ] @

Sta ka kazem osim jedno VELIKO HVALA!
Evo, zavrsavam sve ovo veceras, zahvaljujuci vasoj pomoci..

You`ve been most helpful guys!