Peka i polygon

Ett exempel på en enkel polygon

I beräkningsgeometri frågar problemet punkt -i-polygon ( PIP ) om en given punkt i planet ligger inuti, utanför eller på gränsen för en polygon . Det är ett specialfall av punktlokaliseringsproblem och hittar tillämpningar inom områden som behandlar geometriska data, såsom datorgrafik , datorseende , geografiska informationssystem (GIS), rörelseplanering och datorstödd design (CAD).

En tidig beskrivning av problemet inom datorgrafik visar två vanliga tillvägagångssätt ( strålkastning och vinkelsummation) som användes så tidigt som 1974.

Ett försök från datorgrafikveteraner att spåra problemets historia och några knep för att lösa det kan hittas i ett nummer av Ray Tracing News .

Strålkastningsalgoritm

Antalet skärningspunkter för en stråle som passerar från polygonens yttre till någon punkt; om det är udda visar det att punkten ligger inuti polygonen. Om det är jämnt ligger punkten utanför polygonen; Detta test fungerar också i tre dimensioner.

Ett enkelt sätt att ta reda på om punkten är inuti eller utanför en enkel polygon är att testa hur många gånger en stråle , med början från punkten och går i någon fast riktning, skär polygonens kanter. Om punkten är på utsidan av polygonen kommer strålen att skära dess kant ett jämnt antal gånger. Om punkten är på insidan av polygonen kommer den att skära kanten ett udda antal gånger. Statusen för en punkt på kanten av polygonen beror på detaljerna i strålskärningsalgoritmen.

Denna algoritm är ibland också känd som korsningstalsalgoritmen eller jämn-udda regelalgoritmen och var känd redan 1962. Algoritmen bygger på en enkel observation att om en punkt rör sig längs en stråle från oändligheten till sondpunkten och om den korsar gränsen för en polygon, möjligen flera gånger, så går den växelvis från utsidan till insidan, sedan från insidan till utsidan etc. Som ett resultat går den rörliga punkten ut efter varannan "gränsövergång". Denna observation kan matematiskt bevisas med hjälp av Jordans kurvsats .

Begränsad precision

Om det implementeras på en dator med aritmetik med ändlig precision kan resultaten bli felaktiga om punkten ligger mycket nära den gränsen på grund av avrundningsfel. För vissa applikationer, som videospel eller andra underhållningsprodukter, är detta inte ett stort problem eftersom de ofta favoriserar hastighet framför precision. Men för ett formellt korrekt datorprogram skulle man behöva införa en numerisk tolerans ε och testa i linje om P (punkten) ligger inom ε av L (linjen), i vilket fall algoritmen bör stoppa och rapportera " P ligger " mycket nära gränsen."

De flesta implementeringar av strålkastningsalgoritmen kontrollerar i följd skärningspunkter för en stråle med alla sidor av polygonen i tur och ordning. I det här fallet måste följande problem åtgärdas. Om strålen passerar exakt genom en vertex av en polygon, kommer den att skära 2 segment vid deras ändpunkter. Även om det är OK för fallet med den översta vinkeln i exemplet eller vinkeln mellan korsning 4 och 5, kräver fallet med fallet längst till höger (i exemplet) att vi räknar en skärningspunkt för att algoritmen ska fungera korrekt. Ett liknande problem uppstår med horisontella segment som råkar falla på strålen. Problemet löses enligt följande: Om skärningspunkten är en vertex på en testad polygonsida, räknas skärningen endast om sidans andra vertex ligger under strålen. Detta motsvarar i praktiken att betrakta hörn på strålen som liggande något ovanför strålen.

Återigen kan fallet med strålen som passerar genom en vertex utgöra numeriska problem i aritmetik med finit precision : för två sidor som gränsar till samma vertex kanske den enkla beräkningen av skärningen med en stråle inte ger vertexen i båda fallen. Om polygonen specificeras av dess hörn, elimineras detta problem genom att kontrollera y-koordinaterna för strålen och ändarna på den testade polygonsidan innan den faktiska beräkningen av skärningspunkten. I andra fall, när polygonsidor beräknas från andra typer av data, måste andra knep användas för algoritmens numeriska robusthet .

Lindningstalsalgoritm

En annan teknik som används för att kontrollera om en punkt är inuti en polygon är att beräkna den givna punktens lindningstal med avseende på polygonen. Om lindningstalet inte är noll, ligger punkten inuti polygonen. Den här algoritmen är ibland också känd som icke- nollregelalgoritmen .

Ett sätt att beräkna lindningstalet är att summera vinklarna mellan varje sida av polygonen. Detta involverar dock kostsamma inversa trigonometriska funktioner , vilket i allmänhet gör denna algoritm prestandaineffektiv (långsammare) jämfört med strålkastningsalgoritmen. Lyckligtvis behöver dessa inversa trigonometriska funktioner inte beräknas. Eftersom resultatet, summan av alla vinklar, endast kan lägga till upp till 0 eller $2\pi$ (eller multiplar av ${\displaystyle 2\pi } )$ , är det tillräckligt att spåra genom vilka kvadranter polygonvindar, när den vänder sig runt testpunkten, vilket gör lindningstalsalgoritmen jämförbar i hastighet med att räkna gränsövergångarna.

Visualisering av Dan Sundays slingrande talalgoritm. Ett lindningstal på 0 betyder att punkten är utanför polygonen; andra värden indikerar att punkten är inuti polygonen

En förbättrad algoritm för att beräkna lindningstalet utvecklades av Dan Sunday 2001. Den använder inte vinklar i beräkningar, inte heller någon trigonometri, och fungerar exakt på samma sätt som strålkastningsalgoritmerna som beskrivs ovan. Söndagens algoritm fungerar genom att betrakta en oändlig horisontell strålkastning från den punkt som kontrolleras. Närhelst den strålen korsar en kant av polygonen, används Juan Pinedas kantkorsningsalgoritm (1988) för att bestämma hur korsningen kommer att påverka lindningstalet. Som söndagen beskriver det, om kanten korsar strålen och går "uppåt", ökas slingrandet; om den korsar strålen "nedåt", minskas antalet. Söndagens algoritm ger det korrekta svaret för icke-enkla polygoner, medan gränsövergångsalgoritmen misslyckas i detta fall.

Genomföranden

SVG

Liknande metoder används i SVG för att definiera ett sätt att fylla med färg olika former (som bana, polylinje, polygon, text etc.). Algoritmen för fyllning påverkas av attributet 'fill-rule'. Värdet kan vara antingen icke-noll eller jämnt . Till exempel, i en icke-konvex regelbunden femkantig yta , finns det ett centralt "hål" (synlig bakgrund) med jämnodd och ingen med attribut som inte är noll .

För enkla polygoner ger algoritmerna samma resultat. Men för komplexa polygoner kan algoritmerna ge olika resultat för punkter i de regioner där polygonen skär sig, där polygonen inte har en tydligt definierad insida och utsida. En lösning med jämna-udda-regeln är att omvandla (komplexa) polygoner till enklare som är jämna-udda-ekvivalenta före korsningskontrollen. Detta är dock beräkningsmässigt dyrt. Det är billigare att använda den snabba lindningstalsalgoritmen som inte är noll, som ger rätt resultat även när polygonen överlappar sig själv.

Peka i polygonfrågor

Problemet med punkt i polygon kan övervägas i den allmänna upprepade geometriska frågeinställningen: givet en enda polygon och en sekvens av frågepunkter, hitta snabbt svaren för varje frågepunkt. Uppenbarligen kan vilken som helst av de allmänna tillvägagångssätten för plan punktplacering användas. Enklare lösningar finns för vissa speciella polygoner.

Speciella fall

Enklare algoritmer är möjliga för monotona polygoner , stjärnformade polygoner , konvexa polygoner och trianglar .

Triangelfallet kan enkelt lösas med hjälp av ett barycentriskt koordinatsystem , parametrisk ekvation eller punktprodukt . Punktproduktmetoden sträcker sig naturligt till vilken konvex polygon som helst.

Se även

Java Topology Suite (JTS)
Diskussion: http://www.ics.uci.edu/~eppstein/161/960307.html
Metoder för lindning av tal kontra korsande tal: http://geomalgorithms.com/a03-_inclusion.html