Alfa tvar - Alpha shape

Konvexní trup, alfa tvar a minimální kostra dvojrozměrné datové sady.

v výpočetní geometrie, an alfa tvarnebo tvar α, je rodina po částech lineárních jednoduchých křivek v Euklidovské letadlo spojené s tvarem konečné množiny bodů. Nejprve je definoval Edelsbrunner, Kirkpatrick & Seidel (1983). Tvar alfa spojený se sadou bodů je zobecněním pojmu konvexní obal, tj. každý konvexní trup má tvar alfa, ale ne každý tvar alfa je konvexní trup.

Charakterizace

Pro každého reálné číslo α, definovat pojem a zobecněný disk o poloměru 1/α jak následuje:

  • Li α = 0, je uzavřený polorovina;
  • Li α > 0, jedná se o uzavřený disk o poloměru 1 /α;
  • Li α <0, jedná se o uzavření komplementu disku o poloměru −1 /α.

Potom je hrana alfa tvaru nakreslena mezi dva členy množiny konečných bodů, kdykoli existuje zobecněný disk o poloměru 1 /α neobsahující žádný z množiny bodů a který má tu vlastnost, že dva body leží na jeho hranici.

Li α = 0, pak alfa-tvar spojený s množinou konečných bodů je její obyčejný konvexní trup.

Alfa komplex

Alfa tvary úzce souvisí s alfa komplexy, subkomplexy z Delaunayova triangulace množiny bodů.

Každý okraj nebo trojúhelník Delaunayova triangulace může být spojen s charakteristickým poloměrem, poloměrem nejmenšího prázdného kruhu obsahujícího hranu nebo trojúhelník. Pro každého reálné číslo α, α-komplex dané sady bodů je zjednodušený komplex tvořený množinou hran a trojúhelníků, jejichž poloměry jsou maximálně 1 /α.

Spojení hran a trojúhelníků v α-komplex tvoří tvar velmi podobný tvaru α-tvar; liší se však tím, že má polygonální hrany, spíše než hrany vytvořené z oblouků kruhů. Konkrétněji, Edelsbrunner (1995) ukázal, že dva tvary jsou ekvivalent homotopy. (V této pozdější práci použil Edelsbrunner název „α-shape "označuje spojení buněk v α-komplex, a místo toho nazval související křivočarý tvar an α-tělo.)

Příklady

Tuto techniku ​​lze použít k rekonstrukci a Fermiho povrch z elektronické spektrální funkce Bloch vyhodnocené na Fermiho úroveň, jak bylo získáno z Zelená funkce ve všeobecné studii problému ab-initio. Fermiho povrch je pak definován jako sada vzájemných vesmírných bodů v prvním Brillouinova zóna, kde je signál nejvyšší. Výhodou definice je, že zahrnuje i případy různých forem poruchy.

Fermiho povrch sypkého stříbra: rekonstrukce alfa tvaru z KKR Rekonstrukce blokové spektrální funkce


Viz také

Reference

  • N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke a C. Varela. "Alfa tvary: definice a software ". V Proc. Internat. Comput. Geom. Softwarová dílna 1995, Minneapolis.
  • Edelsbrunner, Herbert (1995), "Hladké povrchy pro vícestupňové znázornění tvarů", Základy softwarové technologie a teoretické počítačové vědy (Bangalore, 1995), Poznámky k přednášce ve Výpočtu. Sci., 1026, Berlín: Springer, s. 391–412, PAN  1458090.
  • Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), „O tvaru množiny bodů v rovině“, Transakce IEEE na teorii informací, 29 (4): 551–559, doi:10.1109 / TIT.1983.1056714.

externí odkazy