Pochodové čtverce - Marching squares - Wikipedia
Pochodové čtverce je počítačová grafika algoritmus který generuje obrysy pro dvourozměrný skalární pole (obdélníkový pole jednotlivých číselných hodnot). Podobnou metodu lze použít pro konturování 2D trojúhelníkové sítě.
Obrysy mohou být dvou druhů:
- Izoliny - řádky sledující jednu datovou úroveň, nebo - hodnota.
- Isobands - vyplněné oblasti mezi izolovanými liniemi.
Mezi typické aplikace patří vrstevnice na topografických mapách nebo generování izobarů pro mapy počasí.
Pochodové čtverce zaujímají podobný přístup jako 3D pochodové kostky algoritmus:
- Zpracujte každou buňku v mřížce samostatně.
- Vypočítejte index buněk pomocí srovnání úrovní vrstev s datovými hodnotami v rozích buněk.
- Použijte předem připravený vyhledávací tabulka, zadané do indexu buňky, k popisu výstupní geometrie pro buňku.
- Aplikovat lineární interpolace podél hranic buňky pro výpočet přesné polohy obrysu.
Základní algoritmus
Tady jsou kroky algoritmu:
Aplikujte práh na 2D pole a vytvořte binární obrázek obsahující:
- 1, kde je datová hodnota výše hodnota
- 0, kde je datová hodnota níže hodnota
Každý blok 2x2 pixelů v binárním obrazu tvoří konturovací buňku, takže celý obraz je reprezentován mřížkou takových buněk (na obrázku níže zeleně). Všimněte si, že tato konturovací mřížka je o jednu buňku menší v každém směru než původní 2D pole.
Pro každou buňku v konturovací mřížce:
- Vytvořte 4 bity v rozích buňky k vytvoření binárního indexu: projděte buňku v a ve směru hodinových ručiček směr připojující bit do indexu pomocí bitové NEBO a levý Shift, z nejvýznamnější bit vlevo nahoře do nejméně významný bit vlevo dole. Výsledný 4bitový index může mít 16 možných hodnot v rozsahu 0–15.
- Pomocí indexu buněk získáte přístup k předem vytvořenému vyhledávací tabulka se 16 položkami se seznamem okrajů potřebných k reprezentaci buňky (zobrazeno v pravé dolní části obrázku níže).
- Aplikovat lineární interpolace mezi původními hodnotami dat pole najít přesnou polohu vrstevnice podél okrajů buňky.
Rozcestník sedlových bodů
Obrys je nejednoznačný sedlové body. Nejasnost je možné vyřešit pomocí průměrný datová hodnota pro střed buňky pro výběr mezi různými spoji interpolovaných bodů:
Isobands
Podobný algoritmus lze vytvořit pro vyplněná obrysová pásma v rámci horní a dolní prahové hodnoty:
Tvarovací trojúhelníkové sítě
Lze použít stejný základní algoritmus trojúhelníkové sítě, které se skládají ze spojených trojúhelníků s daty přiřazenými k vrcholům. Například rozptýlenou sadu datových bodů lze připojit k a Delaunayova triangulace umožnit konturování datového pole. Trojúhelníková buňka je vždy rovinný, protože to je 2-simplexní (tj. určené n + 1 vrcholy v n-dimenzionálním prostoru). Vždy existuje jedinečný lineární interpolant přes trojúhelník a žádná možnost nejednoznačného sedla.
Izoliny
Analýza pro isoliny přes trojúhelníky je obzvláště jednoduchý: existují 3 binární číslice, takže 8 možností:
Isobands
Analýza pro isobands přes trojúhelníky vyžaduje 3 ternární triky, takže 27 možností:
Rozměry a mezery
The datový prostor pro algoritmus Marching Squares je 2D, protože vrcholy přiřazené datové hodnotě jsou spojeny s jejich sousedy ve 2D topologické mřížka, ale prostorové souřadnice přiřazené vrcholům mohou být ve 2D, 3D nebo vyšších rozměrech.
Například trojúhelníková síť může představovat 2D datový povrch vložený do 3D prostoru, kde prostorové polohy vrcholů a interpolovaných bodů podél obrysu budou mít všechny 3 souřadnice. Všimněte si, že případ čtverců je opět nejednoznačný, protože a čtyřúhelník vložený do 3-dimenzionálního prostoru nemusí být nutně rovinný, takže existuje možnost výběru geometrického interpolačního schématu pro kreslení páskovaných povrchů ve 3D.
Úvahy o výkonu
Algoritmus je trapně paralelní, protože všechny buňky jsou zpracovávány nezávisle. Je snadné napsat a paralelní algoritmus za předpokladu:
- Sdílené skalární pole pouze pro čtení.
- Sdílený výstupní proud geometrie pouze pro připojení.
Naivní implementace Marching Squares, která zpracovává každou buňku samostatně, provede každou lineární interpolace dvakrát (isoline) nebo čtyřikrát (isoband). Podobně bude výstup obsahovat 2 kopie 2D vrcholů pro disjunktní čáry (isoline) nebo 4 kopie pro polygony (isobands). [Za předpokladu, že: mřížka je velká, takže většina buněk je interních; a vytváří se celá souvislá sada izopásem.]
Je možné snížit výpočetní režii o ukládání do mezipaměti výsledky interpolace. Například sériová verze s jedním vláknem by potřebovala ukládat do mezipaměti interpolované výsledky pouze pro jeden řádek vstupní mřížky.
Je také možné zmenšit velikost výstupu pomocí indexovaných geometrických primitiv, tj. vytvořit pole 2D vrcholů a zadejte čáry nebo mnohoúhelníky pomocí krátké celé číslo posuny do pole.
Reference
- Maple, C. (2003). Geometrický design a plánování prostoru pomocí algoritmů pochodových čtverců a pochodových krychlí. Proc. 2003 mezinárodní Konf. Geometrické modelování a grafika. str. 90–95. doi:10.1109 / GMAG.2003.1219671. ISBN 978-0-7695-1985-2.
- Banks, D. C. (2004). Msgstr "Počítání případů v substitučních algoritmech". IEEE Trans. Vizuální. Comp. Grafika. 10 (4): 371–384. CiteSeerX 10.1.1.582.7221. doi:10.1109 / TVCG.2004.6. PMID 18579966.
- Laguardia, J. J .; Cueto, E .; Doblaré, M. (2005). "Metoda Galerkinova přirozeného souseda se strukturou čtyřstromu". Int. J. Numer. Pervitin. Inženýr. 63 (6): 789–812. Bibcode:2005IJNME..63..789L. doi:10,1002 / nme.1297.
- Schaefer, Scott; Warren, Joe (2005). "Duální pochodové kostky: kontury prima a duální mřížky". Comp. Graf. Fórum. 24 (2): 195–201. doi:10.1111 / j.1467-8659.2005.00843.x.
- Mantz, Huber; Jacobs, Karin; Mecke, Klaus (2008). "Využití funkčních prvků Minkowski pro analýzu obrazu: algoritmus pochodového čtverce". J. Stat. Mech .: Theory Exp. 2008 (12): P12015. Bibcode:2008JSMTE..12..015M. doi:10.1088 / 1742-5468 / 2008/12 / P12015.
- Cipolletti, Marina P .; Delrieux, Claudio A .; Perillo, Gerardo M. E .; Piccolo, M. Cintia (2012). Msgstr "Segmentace hranic a měření v rozlišeních vzdáleného průzkumu". Comp. Geosci. 40: 87–97. Bibcode:2012CG ..... 40 ... 87C. doi:10.1016 / j.cageo.2011.07.015.
externí odkazy
- Algoritmus pochodového čtverce Matlab - Snadno pochopitelný algoritmus pochodového čtverce s otevřeným zdrojovým kódem.
- implementace v Javě
- Kód pochodových čtverců v Javě. Vzhledem k 2D datové sadě a prahovým hodnotám vrátí GeneralPath [] pro snadné vykreslení.
- Meandrující trojúhelníky vysvětlení a ukázková implementace Pythonu.
- Kód pochodových čtverců v C - Jedna knihovna záhlaví pro pochodující čtverce, která umožňuje export trojúhelníkových sítí pro snadné vykreslení.