Jak sprawdzić, czy punkt leży wewnątrz wielokąta?

Dane są wierzchołki P_i = (x_i, y_i), i = 1, 2,..., n wielokąta, i punkt Q = (a, b). Jak sprawdzić, czy punkt Q leży wewnątrz wielokąta? Zwróćmy uwagę, że sformułowanie zagadnienia nie jest jednoznaczne: nie stwierdzono, czy łamana P₁P₂...P_nP₁ jest brzegiem badanego wielokąta. Jesli jest, i jest łamaną zwyczajną (bez samoprzecięć), to trzeba najpierw zbadać wypukłość tego wielokąta i postępować odpowiednio do rezultatu. Jeśli zaś łamana P₁P₂...P_nP₁ nie musi być brzegiem badanego wielokąta, to sam spis (zbiór) wierzchołków określa wielokąt tylko przy dodatkowym założeniu, że chodzi o wielokąt wypukły.

Pierwszy przypadek - wielokąt ograniczony łamana zamkniętą zwyczajną P₁P₂...P_nP₁. Najpierw sprawdzamy wypukłość wielokąta; dla każdej prostej P_iP_i+1 i prostej P_nP₁ sprawdzamy metodą, opisaną wyżej, czy pozostałe wierzchołki leżą po jednej stronie tej prostej. Jeśli tak, to badany wielokąt jest częścią wspólną półpłaszczyzn, więc jest wypukły. W takim wypadku, aby sprawdzic, czy punkt Q leży wewnątrz niego, wystarczy sprawdzić - dla każdej z prostych P_iP_i+1 i prostej P_nP₁ - czy punkt Q leży po tej samej stronie prostej, co wierzchołek P_i+2 (wierzchołek P₁ dla i = n - 1, wierzchołek P₂ dla i = n). Jesli tak, to należy do każdej z półpłaszczyzn, których częścią wspólną jest badany wielokąt, czyli leży wewnątrz wielokąta. Jeśli nie, to leży na zewnątrz lub na brzegu wielokąta.

Jeśli wielokąt okazał się niewypukły, to trzeba podzielić go na sumę wielokątów wypukłych. W tym celu szukamy nieprzedłużalnego łańcucha kolejnych wierzchołków P_iP_i+1...P_j takiego, że wszystkie pozostałe wierzchołki leżą po jednej stronie każdej prostej łączącej dwa kolejne wierzchołki w tym łańcuchu. Nieprzedłużalność oznacza, że ani prosta P_i-1P_i, ani prosta P_jP_j+1 nie mają już tej własności, tzn. wierzchołki wielokąta leżą po obu stronach każdej z tych prostych. Taki łańcuch wyznacza wystający "róg" wielokąta. Wielokąt przedstawiamy jako sumę wielokąta wypukłego P_iP_i+1...P_jP_i i wielokąta P₁P₂...P_i-1P_j+1...P_nP₁ (z odciętym "rogiem"), który ma mniej wierzchołków. Punkt Q leży wewnątrz wielokąta P₁P₂...P_nP₁ wtedy i tylko wtedy, gdy leży wewnątrz wielokąta (wypukłego!) P_iP_i+1...P_jP_i lub leży na boku P_jP_i lub leży wewnątrz wielokąta P₁P₂...P_i-1P_j+1...P_nP₁.

Drugi przypadek - wielokąt jest powłoką wypukłą Conv(P₁, P₂,..., P_n) zbioru danych punktów A = {P₁, P₂,..., P_n}. W tym przypadku trzeba znaleźć łamaną, która jest brzegiem badanego wielokąta. Tworzymy dwa obiekty: podzbiór W zbioru {P₁, P₂,..., P_n} - zbiór punktów wewnętrznych, i ciąg wierzchołków x. Zaczynamy od dowolnego punktu P_i i dla każdej prostej P_iP_j, j $\neq$ i sprawdzamy, czy wszystkie pozostałe wierzchołki leżą po tej samej stronie prostej. Jeśli nie ma takiego punktu P_j, to punkt P_i przenosimy ze zbioru A do zbioru punktów wewnętrznych W. Jeśli istnieje taki punkt P_j, to punkt P_i przenosimy ze zbioru A na koniec ciągu wierzchołków x, i powtarzamy procedurę z punktem P_j zamiast P_i, aż okaże się, że ciągu wierzchołków nie da się przedłużyć. Wtedy sprawdzany punkt dopisujemy na końcu ciągu wierzchołków, a pozostałe w zbiorze A punkty przenosimy do zbioru W punktów wewnętrznych. Ciąg wierzchołków wyznacza łamaną zwyczajną, która ogranicza badany wielokąt, i zagadnienie sprowadziło się do pierwszego przypadku, przy czym już wiadomo, że badany wielokąt jest wypukły.