Weiler – Athertonův ořezový algoritmus - Weiler–Atherton clipping algorithm

The Weiler – Atherton je mnohoúhelník-výstřižek algoritmus. Používá se v oblastech jako počítačová grafika a vývoj her, kde je zapotřebí ořezávání polygonů. Umožňuje oříznutí a polygon předmětu nebo kandidáta libovolně tvarovaný ořezový mnohoúhelník / oblast / oblast.

To je obecně použitelné pouze v 2D. Lze jej však použít v 3D prostřednictvím stanovení viditelného povrchu a se zvýšenou účinností prostřednictvím Z-objednávání.^[1]

Předpoklady

Pododdělení pomocí Weiler-Athertonova algoritmu

Před použitím na polygon vyžaduje algoritmus splnění několika předpokladů:

• Kandidátské polygony musí být orientovány ve směru hodinových ručiček.
• Kandidátské polygony by se neměly protínat samy (tj. Znovu vstoupit).
• Algoritmus může podporovat díry (jako polygony proti směru hodinových ručiček zcela uvnitř jejich nadřazeného polygonu), ale vyžaduje další algoritmy k rozhodnutí, které polygony jsou díry, a poté lze sloučení polygonů provést pomocí varianty algoritmu.

Algoritmus

Vzhledem k tomu, že polygon A je ořezovou oblastí a polygon B jako předmětný polygon, který má být oříznut, se algoritmus skládá z následujících kroků:

1. Seznam vrcholů polygonu ořezové oblasti A a vrcholů polygonu předmětu B.
2. Označte uvedené vrcholy předmětného polygonu B buď uvnitř, nebo vně ořezové oblasti A.
3. Najděte všechny průsečíky mnohoúhelníků a vložte je do obou seznamů a propojte seznamy v průsečících.
4. Vytvořte seznam „příchozích“ průsečíků - průsečíků, kde vektor od průsečíku k následnému vrcholu předmětného polygonu B začíná uvnitř ořezové oblasti.
5. Postupujte po každé křižovatce ve směru hodinových ručiček kolem propojených seznamů, dokud nenajdete počáteční pozici.

Pokud neexistují žádné křižovatky, musí platit jedna ze tří podmínek:

1. A je uvnitř B - návrat A pro oříznutí, B pro sloučení.
2. B je uvnitř A - návrat B pro oříznutí, A pro sloučení.
3. A a B se nepřekrývají - vrátit žádný pro oříznutí nebo A & B pro sloučení.

Závěr

Jeden nebo více konkávních polygonů může vytvořit více než jeden protínající se polygon. Konvexní polygony budou mít pouze jeden protínající se polygon.

Stejný algoritmus lze použít ke sloučení dvou polygonů tak, že se začnou spíše na odchozích křižovatkách než na příchozích. To však může vytvářet otvory proti směru hodinových ručiček.

Některé kombinace mnohoúhelníků může být obtížné vyřešit, zvláště když jsou povoleny díry.

Body velmi blízko k okraji druhého polygonu lze považovat za dovnitř i ven, dokud nebude možné potvrdit jejich stav po nalezení a ověření všech křižovatek; to však zvyšuje složitost.

Ke zvýšení rychlosti tohoto označování a vyhnutí se nutnosti dalšího postupu lze použít různé strategie. Pokud polygony sdílejí výhodu, bude zapotřebí opatrnosti.

Viz také

• Algoritmus oříznutí Sutherland – Hodgman
• Vattiho ořezový algoritmus
• Greiner – Hormann ořezový algoritmus

Reference

• Weiler, Kevin a Atherton, Peter. "Odstranění skrytého povrchu pomocí třídění oblastí polygonů", Computer Graphics, 11 (2): 214-222, 1977.

Tento počítačová grafika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.