Punkt i polygon

Punkt i polygon-problemet går ut på å finne ut om et gitt punkt er innenfor et polygon eller ikke. Ofte antas polygonet til å ikke være konvekst; det kan også antas å ikke være enkelt, det vil si omsluttet av en enkel kurve. Problemet er et spesialtilfelle av punktlokasjon-problemet, som går ut på å finne ut hvilken region, av en mengde disjunkte regioner, et gitt punkt tilhører.

Raycasting brukt for å løse punkt-i-polygon-problemet: Tell antall ganger en stråle fra punktet krysser sider av polygonet, og sjekk om dette er et oddetall eller partall

Vanlige algoritmer for å løse dette problemet er raycasting, vinkelsummering og winding number. De to første av disse ble først presentert i 1974.

Punkt i polygon-problemet kan generaliseres til punkt i polyhedron-problemet i tre dimensjoner.

Algoritmer

Raycasting

Raycasting («strålekasting»), også kalt crossing numbers («kryssende nummer»), kan brukes for å avgjøre om punktet ligger i polygonet eller ikke. Algoritmen oppretter en stråle til det uendelige, eller et linjestykke til et punkt utenfor polygonet, fra punktet man vil undersøke. For å finne ut om punktet er i eller utenfor polygonet teller man opp antall sider av polygonet som krysses av denne strålen, eller dette linjestykket. Ideen bak algoritmen bygger på Jordans kurveteorem, som sier at en lukket kurve deler et plan i nøyaktig to deler: En utside og en innside.

Dersom linjestykket krysser en stråle i et endepunkt, det vil si et hjørne av polygonet, må dette behandles separat: Man vet ikke om linjestykket fortsetter på innsiden eller på utsiden av polygonen. For å løse dette kan man enten ha spesialtester som ser på geometriske egenskaper, eller man kan justere linjestykket slik at det ikke lenger går igjennom et hjørne.

Å teste alle linjestykker for et gitt polygon kan gjøres i lineær tid. For å gjøre dette raskere kan man bruke mer avanserte datastrukturer, slik som for eksempel kd-trær.