Problemet med, om et punkt hører til en polygon

I beregningsgeometri er problemet med at bestemme, om et punkt hører til en polygon , kendt . En polygon og et punkt er givet i en plan . Det er nødvendigt at løse spørgsmålet om, hvorvidt et punkt hører til en polygon.

En polygon kan enten være konveks eller ikke-konveks. Det antages normalt, at polygonen er enkel, det vil sige uden selvskæringer; men problemet overvejes også for ikke-simple polygoner. I sidstnævnte tilfælde kan forskellige måder at bestemme, om et punkt tilhører en polygon, føre til forskellige resultater. Der er algoritmer uden forbehandling; og algoritmer med forbehandling, hvor der skabes nogle datastrukturer, der giver dem mulighed for at svare hurtigere på mange forespørgsler om, hvorvidt forskellige punkter hører til den samme polygon.

Strålesporingsmetode

Regnskab for antallet af kryds

En af standardmetoderne til at bestemme, om et punkt tilhører en vilkårlig simpel polygon, er som følger. Lad os skyde en stråle fra et givet punkt i en vilkårlig retning (for eksempel i positiv retning af den vandrette akse), og tælle hvor mange gange strålen krydser polygonens kanter. For at gøre dette er det nok at sløjfe gennem polygonens kanter og bestemme, om strålen skærer hver kant. Hvis antallet af skæringspunkter er ulige, erklæres det, at punktet ligger inde i polygonen, hvis det er lige, så udenfor. Dette er baseret på den simple observation, at når man bevæger sig langs strålen, med hver grænseoverskridelse, befinder punktet sig på skift i og uden for polygonen. Algoritmen kendes under navne som krydsningstal (optælling) algoritme eller lige-ulige regel .

Algoritmen har vanskeligheder i det degenererede tilfælde, når strålen skærer polygonens toppunkt. En måde at overvinde det på er at antage, at sådanne polygon-spidser ligger uendeligt meget over (eller under) den rette linje af strålen, og derfor er der faktisk ingen skæring. [1] Således tælles skæringen af ​​en stråle med en kant, hvis en af ​​kantens ender ligger strengt under strålen, og den anden ende er over eller ligger på strålen.

Algoritmen kører i O( N ) tid for en N - gon.

Regnskab for antallet af omdrejninger

Overvej antallet af omdrejninger, som polygonens orienterede grænse laver omkring et givet punkt P . I algebraisk topologi kaldes dette tal indekset for punktet i forhold til kurven . [2] Det kan beregnes som følger. Lad os som før skyde en stråle fra P i en vilkårlig retning og overveje kanterne, den skærer. Vi tildeler et antal +1 eller -1 til hvert kryds, afhængigt af hvordan kanten skærer strålen - med uret (venstre mod højre) eller mod uret (højre mod venstre). Disse to tilfælde kan skelnes ved prikproduktets fortegn mellem kantretningsvektoren og normalen til stråleretningsvektoren. [3] Summen af ​​de opnåede værdier er indekset for punktet i forhold til kurven . Summen vil være positiv eller negativ, afhængigt af grænsens orientering. Hvis det ikke er lig med nul, så vil vi antage, at punktet ligger inde i polygonen, ellers - udenfor.

En sådan algoritme er kendt som den ikke-nul-viklingsregel . [3]

For simple polygoner fungerer denne metode på samme måde som metoden baseret på at tælle antallet af skæringspunkter. Forskellen mellem dem bliver tydelig, når man betragter polygoner med en selvskærende grænse.

Vinkelsum metode

Det kan bestemmes, at punktet P er inde i en polygon med toppunkter V 0 , V 1 , ..., V n = V 0 ved at beregne summen:

hvor  er vinklen (i radianer og fortegn) mellem strålerne PV i − 1 og PV i , dvs.

Det kan bevises, at denne sum ikke er andet end viklingstallet for punktet P i forhold til polygongrænsen, op til en konstant faktor . Derfor kan vi antage, at punktet ligger uden for polygonen, hvis summen er lig med nul (eller tæt nok på den, hvis der bruges tilnærmet aritmetik). Denne metode er dog meget upraktisk, da den kræver beregning af dyre operationer for hver kant (inverse trigonometriske funktioner, kvadratrødder), og er endda blevet kaldt den "værste algoritme i verden" til dette problem [1] .

K. Weiler foreslog en praktisk version af denne metode, hvor man undgik dyre operationer og omtrentlige beregninger. [4] Det blev vist, at summen af ​​vinklerne kan beregnes ved kun at bruge operationen med at klassificere et polygonpunkt i kvadranter i forhold til punktet P . Weilers algoritme og nogle forbedringer til den er beskrevet i [5] .

Algoritmer med forbehandling

Konvekse og stjernepolygoner

Hvorvidt et punkt tilhører en konveks eller stjerne N - gon kan bestemmes ved hjælp af binær søgning i O(log N ) tid, O( N ) hukommelse og O( N ) forbehandlingstid. [6]

Vilkårlig polygon

Problemet med, om et punkt tilhører en vilkårlig simpel polygon, kan betragtes som et specialtilfælde af problemet med at lokalisere et punkt i en plan underinddeling. For en N - gon kan dette problem løses i O(log 2N ) tid ved brug af O( N ) hukommelse og O( N log N ) forbehandlingstid. [7]

Noter

  1. ↑ 1 2 Eric Haines. Punkt i polygonstrategier Arkiveret 25. september 2011 på Wayback Machine
  2. ↑ Kan oversættes til russisk som "kurveindeks i forhold til et punkt", "torsionstal", "viklingsnummer", "skruenummer" og lignende.
  3. ↑ 1 2 Foley JD, et al. Computergrafik: principper og praksis. Addison Wesley. 1990. S. 965.
  4. ↑ K. Weiler. Et inkrementelt vinkelpunkt i polygontest, i: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. Punktet i polygonproblemet for vilkårlige polygoner   // Comput . Geom. Theory Appl.. - 2001. - Vol. 20 . - S. 131-144 .
  6. ↑ Preparata, Sheimos. Side 60-61.
  7. ↑ Preparata, Sheimos. Side 74. Sætning 2.6.

Litteratur

Links