Przynale?żność do wieląkąta

Problem jest następujący:

Mamy dany dowolny wielokąt (wklęsły, lub wypukły), znamy wszystkie współrzędne wierzchołków tego wielokąta. Jest też punkt x którego współrzędne także znamy. I teraz moje pytanie:

Czy ktoś wie jak sprawdzić czy punkt x należy do wielokąta(tzn czy leży w jego wnętrzu lub na krawędzi) czy też nie(jest na zewnątrz)

nul, prosta sprawa... http://www.google.pl

http://www.google.pl/search?num=20&hl=pl&ie=UTF-8&oe=UTF-8&newwindow=1&q=Przynale%C5%BCno%C5%9B%C4%87+do+wielok%C4%85ta&lr=lang_pl

ehh... naprawde nie wiecie jak dzaiłają wyszukiwarki ?!

Ech szukałem ale niestety to co znajdywałęm nie spełniało moich oczekiwań. Ale i tak wielkie dzięki. Mam problem z głowy.

o ile pamiętam to jest tak :
przez punkt prowadzisz dowolną półprostą , jeżeli przetnie ona odcinki które tworzą tą figurę nieparzystą liczbę razy to punkt jest w tej figurze, jeżeli parzystą lub 0 liczbę razy to jest poza tą figurą

/* 0 też jest liczbą parzystą, gdyż dzieli się przez 2 ;) A co do tego, że nic nie znalazł, to znaczy chyba tylko, że nie szukał. -m.D. */

Jeśli niepotrzebny ci algorytm, tylko rozwiązanie, polecam użycie regionow. Montujesz region o kształcie wielokąta, potem za pomocą funkcji ptinregion() sprawdzasz, czy punkt należy do regionu.

<font color="green"> A co do tego, że nic nie znalazł, to znaczy chyba tylko, że nie szukał </span>
pólprosta zaczynajaca sie w jakims punkcie może się nie przeciąć z odcinkami ktore naleza do figury

pólprosta zaczynajaca sie w jakims punkcie może się nie przeciąć z odcinkami ktore naleza do figury

1. Co to ma do mojego komentarza na temat nieumiejętności szukania?
2. Jeżeli punkt z którego zaczynamy rysować półprostą leży wewnątrz jakiegoś obszaru ograniczonego, to zawsze przetnie się z nim co najmniej raz (w szczególności, jeżeli leży na krawędzi). Jedyny problem jaki powstaje, to jeżeli jeden z boków wielokąta ma część wspólną z półprostą (wtedy ciężko określić ile punktów wspólnych mają. Teoretycznie nieskończenie wiele)

Możesz podzielić wielokąt na trójkąty i sprawdzić czy punkt jest wewnątrz któregoś trójkąta. Jak? Banalka :) Jest sobie taki wzór na pole trójkąta:

P=1/2 [ (y1-x1)(z2-x2)-(y2-x2)(z1-x1)],
gdzie (x1,x2),(y1,y2),(z1,z2) to odpowiednie wierzchołki.

Teraz liczysz pole całego trójkąta, i pola trzech mniejszych (parami wieszchołki i punkt sprawdzany. Jeżeli suma "małych" pól jest większa od pola "dużego" topunkt jest wewnątrz trójkąta. Fajne :P

Najlepsze jest to, że wzór na pole nie jest "mocożerny" (tak mi się wydaje)