Povrsina mnogougla i pripadnost tacke istom

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.

Potpis

Badges? We don't need no stinking badges.

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

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

Potpis

Badges? We don't need no stinking badges.

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

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?

Potpis

Badges? We don't need no stinking badges.

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

Potpis

Badges? We don't need no stinking badges.