Az a probléma, hogy egy pont egy sokszöghez tartozik-e

A számítási geometriában ismert az a probléma, hogy egy pont egy sokszöghez tartozik-e . Egy sokszög és egy pont adott egy síkban . Meg kell oldani azt a kérdést, hogy egy pont egy sokszöghez tartozik-e.

A sokszög lehet konvex vagy nem konvex. Általában azt feltételezik, hogy a sokszög egyszerű, azaz nincs önmetszéspontja; de a problémát nem egyszerű sokszögeknél is figyelembe veszik. Az utóbbi esetben a sokszöghez tartozó pont meghatározásának különböző módjai eltérő eredményekhez vezethetnek. Vannak előfeldolgozás nélküli algoritmusok; valamint az előfeldolgozással rendelkező algoritmusok, amelyek során létrejönnek bizonyos adatstruktúrák, amelyek lehetővé teszik, hogy gyorsabban tudjanak válaszolni számos olyan lekérdezésre, hogy különböző pontok ugyanahhoz a sokszöghez tartoznak-e.

Sugárkövetési módszer

A kereszteződések számának elszámolása

Az egyik szabványos módszer annak meghatározására, hogy egy pont tetszőleges egyszerű sokszöghez tartozik-e, a következő. Lőjünk ki egy sugarat egy adott pontból tetszőleges irányban (például a vízszintes tengely pozitív irányába), és számoljuk meg, hogy a sugár hányszor keresztezi a sokszög éleit. Ehhez elegendő áthurkolni a sokszög éleit, és meghatározni, hogy a sugár metszi-e az egyes éleket. Ha a metszéspontok száma páratlan, akkor azt deklaráljuk, hogy a pont a sokszögön belül, ha páros, akkor kívül van. Ez azon az egyszerű megfigyelésen alapul, hogy a sugár mentén haladva minden határátlépéskor a pont felváltva a sokszögön belül és kívül találja magát. Az algoritmus olyan neveken ismert, mint például keresztezési szám (számlálás) algoritmus vagy páros-páratlan szabály .

Az algoritmusnak nehézségei vannak abban a degenerált esetben, amikor a sugár metszi a sokszög csúcsát. Ennek egyik módja az, hogy feltételezzük, hogy az ilyen sokszög csúcsok végtelenül kicsivel a sugár egyenese felett (vagy alatta) helyezkednek el, és ezért valójában nincs metszéspont. [1] Így a sugárnak egy éllel való metszéspontját akkor számoljuk, ha az él egyik vége szigorúan a sugár alatt van, a másik vége pedig a sugár felett, vagy azon fekszik.

Az algoritmus O( N ) idő alatt fut N - gon esetén.

A fordulatszám elszámolása

Tekintsük, hogy a sokszög orientált határa hány fordulatot tesz meg egy adott P pont körül . Az algebrai topológiában ezt a számot a pont görbéhez viszonyított indexének nevezik . [2] A következőképpen számítható ki. Mint korábban, lőjünk ki egy sugarat P -ből tetszőleges irányba, és vegyük figyelembe az általa metszett éleket. Minden metszésponthoz +1 vagy -1 számot rendelünk, attól függően, hogy az él hogyan metszi a sugarat - az óramutató járásával megegyezően (balról jobbra) vagy azzal ellentétes irányba (jobbról balra). Ezt a két esetet az élirányvektor és a sugárirányvektor normálja közötti pontszorzat előjelével lehet megkülönböztetni. [3] A kapott értékek összege a pont görbéhez viszonyított indexe . Az összeg pozitív vagy negatív lehet, a határ irányától függően. Ha nem egyenlő nullával, akkor feltételezzük, hogy a pont a sokszög belsejében, különben kívül van.

Egy ilyen algoritmus a nullától eltérő tekercselési szabály néven ismert . [3]

Egyszerű sokszögeknél ez a módszer ugyanúgy működik, mint a metszéspontok számának számlálásán alapuló módszer. A köztük lévő különbség akkor válik nyilvánvalóvá, ha önmetsző határvonalú sokszögeket veszünk figyelembe.

Szögösszeg módszer

Az összeg kiszámításával megállapítható, hogy a P pont egy V 0 , V 1 , ..., V n = V 0 csúcsú sokszögön belül van :

ahol a PV i − 1 és PV i  sugarak közötti szög (radiánban és előjelben) , azaz:

Bebizonyítható, hogy ez az összeg nem más, mint a P pont tekercsszáma a sokszög határához képest, egy állandó tényezőig . Feltételezhetjük tehát, hogy a pont a sokszögön kívül van, ha az összeg egyenlő nullával (vagy elég közel ahhoz, ha közelítő aritmetikát használunk). Ez a módszer azonban nagyon nem praktikus, mivel minden élre költséges műveletek (inverz trigonometrikus függvények, négyzetgyökök) kiszámítása szükséges, sőt a „világ legrosszabb algoritmusának” is nevezték erre a problémára [1] .

K. Weiler ennek a módszernek egy gyakorlati változatát javasolta, elkerülve a költséges műveleteket és a közelítő számításokat. [4] Megmutatták, hogy a szögek összege csak a sokszögpont negyedekbe sorolásával számítható ki a P ponthoz képest . A Weiler-algoritmus és néhány fejlesztése az [5]-ben található .

Algoritmusok előfeldolgozással

Konvex és csillag sokszögek

Az, hogy egy pont konvex vagy csillag N - gonhoz tartozik-e, bináris kereséssel O(log N ) időben, O( N ) memóriában és O( N ) előfeldolgozási időben határozható meg. [6]

Tetszőleges sokszög

Azt a problémát, hogy egy pont tetszőleges egyszerű sokszöghez tartozik-e , egy síkbeli felosztásban pont lokalizálási probléma speciális esetének tekinthető. Egy N -gon esetén ez a probléma O(log 2 N ) időben O( N ) memória és O( N log N ) előfeldolgozási idő használatával megoldható. [7]

Jegyzetek

  1. ↑ 1 2 Eric Haines. Point in Polygon Strategies archiválva : 2011. szeptember 25. a Wayback Machine -nél
  2. ↑ Lefordítható oroszra: „ponthoz viszonyított görbe index”, „torziós szám”, „tekercselési szám”, „csavarszám” és hasonlók.
  3. ↑ 1 2 Foley JD, et al. Számítógépes grafika: alapelvek és gyakorlat. Addison Wesley. 1990. 965. o.
  4. ↑ K. Weiler. Inkrementális szögpont sokszög tesztben, in: P. Heckbert (szerk.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. A pont a sokszögben tetszőleges sokszögek esetén   // Comput . Geom. Elmélet Appl.. - 2001. - 2. évf. 20 . - 131-144 . o .
  6. ↑ Preparata, Sheimos. oldal 60-61.
  7. ↑ Preparata, Sheimos. oldal 74. 2.6. Tétel.

Irodalom

Linkek