Jak sprawdzić czy punkt jest wewnątrz wielokąta. Opcje

[tlaguz]

Witam.

Mam dany wielokąt o liczbie wierzchołków n. Znam x i y każdego wierzchołka i kolejność w jakiej się łączą.
Mam też dane x i y punktu, i muszę sprawdzić czy znajduje się on w wielokącie.

Jedyne rozsądne co mi przychodzi na myśl to odszukać w tym wielokącie trójkąty lub kwadraty, bo wtedy ze sprawdzeniem nie byłoby problemu, ale za to jest strasznie dużo roboty z takim algorytmem.

Może zna ktoś lepsze rozwiązanie? Googliłem za gotowym algorytmem, ale nie znalazłem nic ciekawego...

Z góry dziękuję za odpowiedź i pozdrawiam
tlaguz

[-=Peter=-]

Układ n nierówności? Jeśli znasz wszystkie współrzędne wierzchołków wielokąta, to możesz wyznaczyć równania prostych, które są krawędzą tej figury. Jeśli masz n równań prostych, pod x i y podstawiasz współrzędne punktu, którego sprawdzasz. Następnie z kolejności wnioskujesz kierunek wszystkich nierówności (bo interesuje Cie, czy dany punkt leży wewnątrz, a nie na krawędziach) i jeśli wszystkie n nierówności są prawdziwe, to znaczy że punkt leży w wielokącie. Teraz możesz zastanowić się nad implementacją i wydajnością, jedynie z czym może być problem to ustalenie kierunku nierówności w tych równaniach.

Ten post edytował -=Peter=- 1.01.2010, 21:41:46

[qwerty1440]

jedynie z czym może być problem to ustalenie kierunku nierówności w tych równaniach.

bzdura... funkcja liniowa sie klania.

Zas do autora: To forum o php, nie matematyce. Trzeba bylo w szkole na lekcjach uwazac.

[Crozin]

http://en.wikipedia.org/wiki/Point_in_polygon

[tlaguz]

Gdyby w gimnazjum była taka lekcja to zapewne bym wiedział jak to rozwiązać.

Edit: Dzięki Crozin

Ten post edytował tlaguz 1.01.2010, 21:57:04