Problém, zda bod patří k mnohoúhelníku

Ve výpočetní geometrii je problém určování, zda bod patří k mnohoúhelníku, znám . Mnohoúhelník a bod jsou dány v rovině . Je třeba vyřešit otázku, zda bod patří k mnohoúhelníku.

Mnohoúhelník může být konvexní nebo nekonvexní. Obvykle se předpokládá, že mnohoúhelník je jednoduchý, to znamená bez průniků; ale problém je také zvažován pro nejednoduché polygony. V druhém případě mohou různé způsoby určení, zda bod patří k mnohoúhelníku, vést k různým výsledkům. Existují algoritmy bez předběžného zpracování; a algoritmy s předzpracováním, během nichž se vytvářejí některé datové struktury, které jim umožňují rychleji reagovat na mnoho dotazů, zda různé body patří ke stejnému polygonu.

Metoda sledování paprsků

Účtování počtu křižovatek

Jedna ze standardních metod pro určení, zda bod patří k libovolnému jednoduchému mnohoúhelníku, je následující. Vystřelme paprsek z daného bodu v libovolném směru (například v kladném směru vodorovné osy) a spočítejme, kolikrát paprsek protne hrany mnohoúhelníku. K tomu stačí procházet hranami mnohoúhelníku a určit, zda paprsek každou hranu protíná. Pokud je počet průsečíků lichý, pak je deklarováno, že bod leží uvnitř polygonu, pokud je sudý, tak mimo. To je založeno na jednoduchém pozorování, že při pohybu po paprsku se při každém překročení hranice bod střídavě ocitá uvnitř a vně polygonu. Algoritmus je znám pod názvy, jako je algoritmus křížení čísel (počet) nebo pravidlo sudé-liché .

Algoritmus má potíže v degenerovaném případě, kdy paprsek protíná vrchol polygonu. Jedním ze způsobů, jak to překonat, je předpokládat, že takové vrcholy mnohoúhelníku leží nekonečně malé množství nad (nebo pod) přímkou ​​paprsku, a proto ve skutečnosti neexistuje žádný průsečík. [1] Průsečík paprsku s hranou se tedy počítá, pokud jeden z konců hrany leží přesně pod paprskem a druhý konec je nad nebo leží na paprsku.

Algoritmus běží v čase O( N ) pro N - gon.

Účtování počtu otáček

Uvažujme počet otáček, které provede orientovaná hranice mnohoúhelníku kolem daného bodu P . V algebraické topologii se toto číslo nazývá index bodu vzhledem ke křivce . [2] Lze jej vypočítat následovně. Stejně jako předtím vystřelme paprsek z P v libovolném směru a uvažujme hrany, které protíná. Každému průsečíku přiřadíme číslo +1 nebo -1 podle toho, jak hrana protíná paprsek - ve směru hodinových ručiček (zleva doprava) nebo proti směru hodinových ručiček (zprava doleva). Tyto dva případy lze rozlišit podle znaménka bodového součinu mezi vektorem směru hrany a normálou k vektoru směru paprsku. [3] Součet získaných hodnot je index bodu vzhledem ke křivce . Součet bude kladný nebo záporný, v závislosti na orientaci hranice. Pokud se nerovná nule, budeme předpokládat, že bod leží uvnitř polygonu, jinak - vně.

Takový algoritmus je známý jako pravidlo nenulového vinutí . [3]

U jednoduchých polygonů tato metoda funguje stejně jako metoda založená na počítání počtu průsečíků. Rozdíl mezi nimi se projeví při zvažování polygonů s protínající se hranicí.

Metoda součtu úhlů

Lze určit, že bod P je uvnitř mnohoúhelníku s vrcholy V 0 , V 1 , ..., V n = V 0 výpočtem součtu:

kde  je úhel (v radiánech a znaménko) mezi paprsky PV i − 1 a PV i , tj.:

Lze dokázat, že tento součet není nic jiného než číslo vinutí bodu P vzhledem k hranici polygonu až do konstantního faktoru . Můžeme tedy předpokládat, že bod leží mimo mnohoúhelník, pokud je součet roven nule (nebo dostatečně blízko k němu, je-li použita přibližná aritmetika). Tato metoda je však velmi nepraktická, protože vyžaduje výpočet drahých operací pro každou hranu (inverzní goniometrické funkce, odmocniny), a dokonce byla pro tento problém nazývána „nejhorším algoritmem na světě“ [1] .

K. Weiler navrhl praktickou verzi této metody, vyhýbající se nákladným operacím a přibližným výpočtům. [4] Ukázalo se, že součet úhlů lze vypočítat pouze pomocí operace klasifikace bodu polygonu do kvadrantů vzhledem k bodu P . Weilerův algoritmus a některá jeho vylepšení jsou popsány v [5] .

Algoritmy s předzpracováním

Konvexní a hvězdicové polygony

Zda bod patří ke konvexnímu nebo hvězdnému N - úhelníku lze určit pomocí binárního vyhledávání v čase O(log N ), paměti O( N ) a čase předběžného zpracování O( N ). [6]

Libovolný polygon

Problém, zda bod patří k libovolnému jednoduchému mnohoúhelníku, lze považovat za speciální případ problému lokalizace bodu v rovinném dělení. Pro N - gon lze tento problém vyřešit v čase O(log 2 N ) pomocí paměti O( N ) a času předběžného zpracování O( N log N ) . [7]

Poznámky

  1. ↑ 1 2 Eric Haines. Point in Polygon Strategies Archivováno 25. září 2011 na Wayback Machine
  2. ↑ Lze přeložit do ruštiny jako „index křivky vzhledem k bodu“, „torzní číslo“, „číslo vinutí“, „číslo šroubu“ a podobně.
  3. ↑ 1 2 Foley JD, et al. Počítačová grafika: Principy a praxe. Addison Wesleyová. 1990. S. 965.
  4. ↑ K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. Problém bodu v polygonu pro libovolné polygony   // Computing . Geom. Theory Appl.. - 2001. - Vol. 20 . - str. 131-144 .
  6. ↑ Preparata, Sheimos. Strana 60-61.
  7. ↑ Preparata, Sheimos. Strana 74. Věta 2.6.

Literatura

Odkazy