Point in Polygon

Point in Polygon -ongelmassa pyritään selvittämään, onko piste monikulmion sisällä, rajalla vai sen ulkopuolella. Ongelma saattaa olla varsin helppo ihmiselle, mutta tietokone vaatii selvittämiseksi algoritmin.

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

Ray casting -menetelmä laskee montako kertaa pisteestä vedetty säde läpäisee monikulmion reunan. Parillinen määrä tarkoittaa, että piste on monikulmion ulkopuolella – joskaan ei kaikissa tapaukissa.

Ray casting -algorimit ei ole täysin varma tapa selvittää PIP-ongelma. Menetelmä voi antaa väärän tulokset osuttuaan monikulmion kulmaan. Kuvassa tilanne havainnollistettu kolmella eri säteellä.

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

Esimerkki kolmiulotteisesta sijaintia rajaavasta suorakaiteesta.

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.