Point in Polygon

Point in Polygon (PIP, PIP-ongelma), eli suomeksi piste monikulmiossa, on matematiikan ja tietojenkäsittelyn ongelma, jonka pääongelma on, onko annettu piste monikulmion sisällä, ulkopuolella vai sen rajalla.

PIP-ongelman ratkaisemisella on useita käytännön hyötyjä esimerkiksi tietokonegrafiikkassa, CAD-ohjelmistoissa, geoinformatiikassa ja paikkatietojärjestelmissä.

PIP-ongelmaa voidaan tutkia niin kaksiulotteisille kuvioille kuin myös kolmiulotteisille kappaleille, sekä yksinkertaisille monikulmioille (simple polygons) ja monimutkaisulle monikulmioille.

Ratkaisuja 

Useita ratkaisuja PIP-ongelmalle on kehitetty. Tietyille monikulmiotyypeille on lisäksi omat nopeat ratkaisumenetelmänsä.

Ray casting -algoritmi 

Varhaisin ja kenties yksinkertaisin menetelmistä lienee niin sanottu Ray casting -algoritmi. Algoritmin mukaan piste on monikulmion ulkopuolella, jos siitä vedettävä puolisuora kulkee parillisen (0, 2, 4 ja niin edelleen) määrän verran monikulmion reunojen läpi. Tämä algoritmi tunnetaan myös joskus nimellä ”even-odd”.

Ray casting -algoritmi ei kuitenkaan ole täydellinen, sillä harvinaisissa tapauksissa säde voi osua kulmaan, muuttaen lopputuloksen vääräksi (katso kuva).

Kierroslukumenetelmä 

Kierroslukuun perustuva algoritmi (Winding number algorithm) määrittää pisteen olevan monikulmion ulkopuolella, jos sen kierrosluku on nolla.

Esilaskenta 

Laskennallisesti ongelma voidaan myös nopeasti esitarkastaa ja nopeuttaa selvittämällä onko piste niin sanotun sijaintia rajaavan suorakaiteen (eng. Bounding Box) sisällä, eli monikulmion sisäänsä sulkevan suorakulmion ulkopuolella. Esitarkastaminen on hyödyllistä esimerkiksi silloin, kun laskettavia pisteitä on huomattavan paljon, sillä sen avulla voidaan nopeasti poistaa ne pisteet jotka eivät mitenkään voi olla monikulmion sisällä. Jäljelle jäävät pisteet voidaan tämän jälkeen ottaa tarkempaan analyysiin, säästäen laskenta-aikaa.

Lähteet 

Geometria