Problemet med om en punkt tillhör en polygon

Inom beräkningsgeometri är problemet med att avgöra om en punkt tillhör en polygon känt . En polygon och en punkt ges i ett plan . Det krävs för att lösa frågan om en punkt tillhör en polygon.

En polygon kan vara antingen konvex eller icke-konvex. Man brukar anta att polygonen är enkel, det vill säga utan självskärningar; men problemet beaktas även för icke-enkla polygoner. I det senare fallet kan olika sätt att avgöra om en punkt tillhör en polygon leda till olika resultat. Det finns algoritmer utan förbearbetning; och algoritmer med förbearbetning, under vilka vissa datastrukturer skapas som gör att de kan svara snabbare på många frågor om huruvida olika punkter tillhör samma polygon.

Strålspårningsmetod

Redovisning av antalet korsningar

En av standardmetoderna för att avgöra om en punkt tillhör en godtycklig enkel polygon är följande. Låt oss skjuta en stråle från en given punkt i en godtycklig riktning (till exempel i den horisontella axelns positiva riktning), och räkna hur många gånger strålen korsar polygonens kanter. För att göra detta räcker det med att slinga genom polygonens kanter och bestämma om strålen skär varje kant. Om antalet skärningspunkter är udda, deklareras det att punkten ligger innanför polygonen, om den är jämn, då utanför. Detta är baserat på den enkla observationen att när man rör sig längs strålen, med varje gränsöverskridande, befinner sig punkten omväxlande inom och utanför polygonen. Algoritmen är känd under namn som algoritm för korsning av tal (antal) eller udda regel .

Algoritmen har svårt i det degenererade fallet när strålen skär polygonens vertex. Ett sätt att övervinna det är att anta att sådana polygonhörn ligger oändligt mycket ovanför (eller under) strålens räta linje, och därför finns det faktiskt ingen skärningspunkt. [1] Således räknas skärningen av en stråle med en kant om en av kantens ändar ligger strikt under strålen, och den andra änden är ovanför eller ligger på strålen.

Algoritmen körs i O( N )-tid för en N -gon.

Redovisning av antalet varv

Betrakta antalet varv som polygonens orienterade gräns gör runt en given punkt P . I algebraisk topologi kallas detta nummer för punktens index med avseende på kurvan . [2] Det kan beräknas enligt följande. Som tidigare, låt oss skjuta en stråle från P i en godtycklig riktning och överväga kanterna den skär. Vi tilldelar ett antal +1 eller -1 till varje korsning, beroende på hur kanten skär strålen - medurs (vänster till höger) eller moturs (höger till vänster). Dessa två fall kan särskiljas genom tecknet för punktprodukten mellan kantriktningsvektorn och normalen till strålriktningsvektorn. [3] Summan av de erhållna värdena är indexet för punkten i förhållande till kurvan . Summan kommer att vara positiv eller negativ, beroende på gränsens orientering. Om det inte är lika med noll, kommer vi att anta att punkten ligger inuti polygonen, annars - utanför.

En sådan algoritm kallas icke-nolllindningsregeln . [3]

För enkla polygoner fungerar denna metod på samma sätt som metoden som bygger på att räkna antalet skärningspunkter. Skillnaden mellan dem blir uppenbar när man betraktar polygoner med en självskärande gräns.

Vinkelsummemetod

Det kan fastställas att punkt P är inuti en polygon med hörn V 0 , V 1 , ..., V n = V 0 genom att beräkna summan:

var  är vinkeln (i radianer och tecken) mellan strålarna PV i − 1 och PV i , dvs.

Det kan bevisas att denna summa inte är något annat än lindningstalet för punkten P med avseende på polygongränsen, upp till en konstant faktor . Därför kan vi anta att punkten ligger utanför polygonen om summan är lika med noll (eller tillräckligt nära den, om ungefärlig aritmetik används). Denna metod är dock väldigt opraktisk, eftersom den kräver beräkning av dyra operationer för varje kant (omvända trigonometriska funktioner, kvadratrötter), och har till och med kallats den "värsta algoritmen i världen" för detta problem [1] .

K. Weiler föreslog en praktisk version av denna metod, för att undvika dyra operationer och ungefärliga beräkningar. [4] Det visades att summan av vinklarna kan beräknas med endast operationen att klassificera en polygonpunkt i kvadranter med avseende på punkten P . Weilers algoritm och några förbättringar av den beskrivs i [5] .

Algoritmer med förbearbetning

Konvexa och stjärnpolygoner

Huruvida en punkt tillhör en konvex eller stjärnig N -gon kan bestämmas med hjälp av binär sökning i O(log N )-tid, O( N )-minne och O( N )-förbehandlingstid. [6]

Godtycklig polygon

Problemet med huruvida en punkt tillhör en godtycklig enkel polygon kan betraktas som ett specialfall av problemet med att lokalisera en punkt i en plan underavdelning. För en N -gon kan detta problem lösas i O(log2N ) -tid med användning av O( N )-minne och O( NlogN ) -förbehandlingstid . [7]

Anteckningar

  1. ↑ 1 2 Eric Haines. Point in Polygon Strategies Arkiverad 25 september 2011 på Wayback Machine
  2. ↑ Kan översättas till ryska som "kurvindex i förhållande till en punkt", "torsionsnummer", "lindningsnummer", "skruvnummer" och liknande.
  3. ↑ 1 2 Foley JD, et al. Datorgrafik: principer och praxis. Addison Wesley. 1990. s. 965.
  4. ↑ K. Weiler. En inkrementell vinkelpunkt i polygontest, i: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. Punkten i polygonproblemet för godtyckliga polygoner   // Comput . Geom. Theory Appl.. - 2001. - Vol. 20 . - S. 131-144 .
  6. ↑ Preparata, Sheimos. Sida 60-61.
  7. ↑ Preparata, Sheimos. Sida 74. Sats 2.6.

Litteratur

Länkar