[es] - Povrsina mnogougla i pripadnost tacke istom

Dusannn
Dusan Nastasijevic

Član broj: 42815
Poruke: 70
*.beotel.net.

+3 Profil

Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:14 - pre 235 meseci}

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.

Badges? We don't need no stinking badges.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl.

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:28 - pre 235 meseci}

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

Odgovor na temu

Dusannn
Dusan Nastasijevic

Član broj: 42815
Poruke: 70
*.beotel.net.

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:36 - pre 235 meseci}

Veliko hvala, Filipe!
Da li bi mozda znao metod kojim se odredjuje pripadnost tacke (x,y) mnogouglu sa n definisanih temena (x_n,y_n)...i problem je resen

Badges? We don't need no stinking badges.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl.

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:41 - pre 235 meseci}

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]}

Odgovor na temu

Dusannn
Dusan Nastasijevic

Član broj: 42815
Poruke: 70
*.beotel.net.

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:44 - pre 235 meseci}

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?

Badges? We don't need no stinking badges.

Odgovor na temu

Dusannn
Dusan Nastasijevic

Član broj: 42815
Poruke: 70
*.beotel.net.

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 16:45 - pre 235 meseci}

...ispravka...
...Vredi li to za nekonveksne mnogouglove?

Badges? We don't need no stinking badges.

Odgovor na temu

zi::
Igor Marinović
Manufaktura doo Internet inženjering
Palić

Član broj: 18090
Poruke: 642
212.200.52.*

ICQ: 7715569
Sajt: www.marinowski.com

Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 21:15 - pre 235 meseci}

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.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl.

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{22.12.2004. u 21:34 - pre 235 meseci}

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).

Odgovor na temu

Dusannn
Dusan Nastasijevic

Član broj: 42815
Poruke: 70
*.beotel.net.

+3 Profil

Re: Povrsina mnogougla i pripadnost tacke istom

^{23.12.2004. u 01:28 - pre 235 meseci}

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

You`ve been most helpful guys!

Badges? We don't need no stinking badges.

Odgovor na temu