W której półpłaszczyźnie wyznaczonej przez łamaną znajduje się punkt

Witam. Na płaszczyźnie mam kilka ponumerowanych punktów. Dwa pierwsze i dwa ostanie punkty wyznaczają półproste lecące w nieskończoność, pozostałe punkty są po prostu kolejno połączone. I teraz muszę odpowiedzieć po której stronie tej łamanej znajduje się przykładowy punkt. Strony (prawa/lewa) określamy patrząc od dowolnego punktu w kierunku punktu o numerze większym o 1.

Wybaczcie jakość obrazka:

Nie zaznaczyłem niestety przykładowych punktów ale pewnie każdy wie o co chodzi.

Jakieś pomysły jak to zrobić ?

Żartujesz sobie? o_O
http://was.zaa.mimuw.edu.pl/?q=node/16#
http://www.math.us.edu.pl/pgladki/faq/node102.html
i milion innych linków. Czemu nawet nie próbowałeś poszukać?

No dobra, w takim razie ja poproszę o obrazek gdzie pokazujesz jak te punkty klasyfikujesz ręcznie. Bo z twojego opisu wcale nie wynika jak to jednoznacznie zrobić. Przeciez punkt na dole, pomiędzy twoimi 2 i 3 będzie po prawej stronie od (2,3) ale po lewej od (3,4) (i może też być po lewej od 1,2). W jaki sposób decydujesz który odcinek bierzesz pod uwagę? Odległośc punktu od tego docinka?

Załóżmy, że sprawdzany punkt A ma współrzędne (Xa,Ya). Szukamy na łamanej dwóch kolejnych punktów B(Xb, Yb) oraz C(Xc, Yc), takich że Xb <= Xa <= Xc. Teraz sprawdzamy, po której stronie prostej przechodzącej przez B, C jest punkt A. Pozostają przypadki, gdy dla jakichś sąsiadujących punktów łamanej Xb jest równe Xc, gdy punkt leży "na lewo" lub "na prawo" od łamanej, punkt na prostej i pewnie jeszcze jakieś skrajne.

Jeżeli łamana ma samoprzecięcia, to dla pewnych punktów płaszczyzny nie jest dobrze określona strona łamanej.
Dla łamanej bez samoprzecięć można działac tak: wybieramy punkt "wzorcowy" W, dla którego łatwo ustalić stronę - np. w połowie drogi do nieskończoności. Dla dowolnego punktu P liczymy ilość punktów przecięcia łamanej z odcinkiem PW, jeśli ta ilośc jest parzysta, to P i W leżą po tej samej stronie, jeśli nieparzysta to leżą po róznych stronach.