Redigerer Punkt i polygon

[[Fil:RecursiveEvenPolygon.svg|thumb|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]]
'''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 [[konveks polygon|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.

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.<ref>{{Kilde www | forfatter=Ivan E. Sutherland, Robert F. Sproull, Robert A. Schumacker |tittel=A Characterization of Ten Hidden-Surface Algorithms | besøksdato=3. april 2018 | utgiver=ACM Comput. Surv. | dato=1974}}</ref>

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,<ref>{{Kilde www | url=http://jedi.ks.uiuc.edu/~johns/raytracer/rtn/rtnv3n4.html#art22 | tittel=Point in Polygon, One More Time..., | utgiver=Ray Tracing News | besøksdato=2. april 2018 | dato=1. oktober 1990 | arkiv-url=https://web.archive.org/web/20180524215455/http://jedi.ks.uiuc.edu/~johns/raytracer/rtn/rtnv3n4.html#art22 | arkivdato=2018-05-24 | url-status=død }}</ref> eller man kan justere linjestykket slik at det ikke lenger går igjennom et hjørne.<ref>{{Kilde www | url=https://www.ics.uci.edu/~eppstein/161/960307.html | tittel=ICS 161: Design and Analysis of Algorithms | dato=7. mars 1996 | besøksdato = 2. april 2018}}</ref>

Å teste alle linjestykker for et gitt polygon kan gjøres i [[kompleksitet (informatikk)|lineær tid]]. For å gjøre dette raskere kan man bruke mer avanserte [[datastruktur]]er, slik som for eksempel [[kd-tre|kd-trær]].<ref>{{Kilde bok | tittel=The Algorithm Design Manual | kapittel=Point Location | forfatter=Steven S. Skiena | år=2008}}</ref>

==Referanser==
<references />

{{Autoritetsdata}}

[[Kategori:Algoritmer]]
[[Kategori:Geometrisk modellering]]