czy punkt zawiera się w wielokącie. Problem z wierzchołkami

[amorphis]

Witam wszystkich

Piszę pewien program, sprawdzający czy dany punkt jest w wielokącie i napotkałem problem. Wiem, że przynależność punktu do wielokąta można łatwo sprawdzić badając ile razy prosta, poprowadzona od punktu badanego gdzieś daleko, przecina boki wielokąta. Problem pojawia się w sytuacji, gdy prosta przecina tylko wierzchołek. Są 2 sytuacje, które postaram się zilustrować w paincie



Uploaded with

Pierwszy punkt znajduje się wewnątrz wielokąta i przecina jego boki tylko raz (w miejscu wierzchołka)
Drugi punkt również przecina raz w miejscu wierzchołka, ale znajduje się na zewnątrz..

I tu jest cały problem. Nie wiem w jaki sposób odróżnić te dwa przypadki, aby poprawnie stwierdzić, który punkt znajduje się wewnątrz wielokąta. Proszę o pomoc.

[Hassgesang]

Puścić prostą drugą stronę? Górny punkt znów przetnie, dolny nie. Ale gorzej się dzieje, jeżeli ropatrujesz wielokąty wypukłe i wklęsłe

[ordyh]

Poczytaj o iloczynie wektorowym, jego znak potrafi stwierdzić w którą stronę (w lewo czy w prawo ) trzeba skręcić, żeby dojść z wierzchołka X do Z przez Y. W tym dolnym przypadku, bierzemy wierzchołki po lewej i prawej owego czworokąta, oba z nich leżą po lewej stronie półprostej którą wypuściliśmy, więc nie zmieniamy jakby stanu czy jesteśmy w środku czy na zewnątrz. Z kolei w tym górnym przypadku górny wierzchołek jest po lewej stronie półprostej, a ten dolny wierzchołek po prawej stronie, więc zmieniamy stan.