Prostorová Delaunayova triangulace

Problém konstrukce sítě nepřekrývajících se trojúhelníků je jedním ze základních ve výpočetní geometrii a je široce používán v počítačové grafice a geografických informačních systémech pro modelování povrchů a řešení prostorových problémů.

Problém konstrukce sítě nepřekrývajících se trojúhelníků byl poprvé nastolen v roce 1934 v práci sovětského matematika B. N. Delona, ​​který formuloval odpovídající podmínky.

V matematice je úkolem sestrojit triangulaci z daných bodů úkolem spojit je ve dvojicích neprotínajícími se úsečkami tak, aby vznikla síť trojúhelníků. Jeho hlavními prvky jsou (obr. 5.3): uzly (vrcholy trojúhelníků), hrany (strany) a plochy (samotné trojúhelníky). Sestrojená triangulace může být konvexní (pokud se jedná o minimální polygon pokrývající plochu modelování), nekonvexní (pokud triangulace není konvexní) a optimální (pokud je součet délek všech hran minimální).

Síť takových trojúhelníků se nazývá Delaunayova triangulace, pokud splňuje určité podmínky:

Žádný z původních bodů nespadá dovnitř kružnice opsané žádnému trojúhelníku (obr. 5.3);

Triangulace je konvexní a splňuje Delaunayovu podmínku formulovanou výše;

Součet minimálních úhlů všech trojúhelníků je maximální ze všech možných triangulací;

Součet poloměrů kruhů popsaných kolem trojúhelníků je mezi všemi možnými triangulacemi minimální.

První z výše uvedených kritérií pro konstrukci Delaunayovy triangulace, nazývané kruhové, je jedním z hlavních a kontroluje se na jakoukoli dvojici trojúhelníků se společnými plochami. Matematická interpretace kritéria vyplývá z Obr. 5.3:

(5.2)

Existuje mnoho způsobů, jak sestrojit Delaunayovu triangulaci, která je jedním z nejpopulárnějších Nedávno metody pro konstrukci triangulační sítě. Používá se v mnoha systémech GIS pro vytváření modelů reliéfu.

Při aplikaci na dvourozměrný prostor je formulován následovně: soustava vzájemně propojených nepřekrývajících se trojúhelníků má nejmenší obvod, pokud žádný z vrcholů nespadá do žádné z kružnic popsaných kolem vytvořených trojúhelníků (obr. 5.4).

Rýže. 5.4. Delaunayova triangulace

To znamená, že výsledné trojúhelníky s takovou triangulací jsou co nejblíže rovnostranným a každá ze stran výsledných trojúhelníků z protilehlého vrcholu je viditelná v maximálním úhlu ze všech možných bodů odpovídající poloroviny. To je přesně optimální triangulace, podél jejíchž okrajů se obvykle provádí lineární interpolace pro konstrukci izolinií.

Mnoho algoritmů pro konstrukci Delaunayovy triangulace používá následující větu.

Teorém 1. Delaunayovu triangulaci lze získat z jakékoli jiné triangulace pomocí stejného systému bodů postupným přeskupením dvojic sousedních trojúhelníků ABC a BCD, které nesplňují Delaunayovu podmínku, do dvojic trojúhelníků ABD a ACD (obr. 5.5).

Rýže. 5.5.. Rekonstrukce trojúhelníků, které nesplňují Delaunayovu podmínku

Tato operace přestavby se často nazývá převrácení. Tato věta umožňuje konstruovat Delaunayovu triangulaci postupně, nejprve zkonstruovat nějakou triangulaci a poté ji postupně vylepšovat ve smyslu Delaunayovy podmínky. Při kontrole Delaunayovy podmínky pro dvojice sousedních trojúhelníků můžete použít definici přímo, ale někdy se používají jiné metody založené na podmínkách uvedených výše.

Za těchto podmínek se objeví celková charakteristika celé triangulace (součet minimálních úhlů nebo součet poloměrů), jejichž optimalizací lze získat Delaunayovu triangulaci.

Jak je uvedeno výše, jeden z kritické operace při konstrukci triangulace je kontrola Delaunayovy podmínky pro dané dvojice trojúhelníků. Na základě definice Delaunayovy triangulace a odpovídajících podmínek se v praxi obvykle používá několik ověřovacích metod:

– kontrola pomocí rovnice opsané kružnice;

– kontrola pomocí předem vypočítané kružnice opsané;

– kontrola součtu protilehlých úhlů;

– upravená kontrola součtu protilehlých úhlů.

Mnoho systémů provádí test s předem vypočítanou kružnicí opsanou. Hlavní myšlenkou ověřovacího algoritmu prostřednictvím předem vypočítaných kruhů je předem vypočítat pro každý sestrojený trojúhelník střed a poloměr kruhu popsaného kolem něj, po kterém bude kontrola Delaunayovy podmínky omezena na výpočet vzdálenosti ke středu. této kružnice a porovnání výsledku s poloměrem. Střed a poloměr r kruhu popsaného kolem lze nalézt jako , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, kde hodnoty abeceda určeno podle vzorců (5.3)

(5.3)

Další záznam pro rovnici tohoto kruhu je:

(5.5.)

(5.6)

Pak bude Delaunayova podmínka pro splněna pouze tehdy, když pro jakýkoli jiný triangulační bod bude:

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r2. (5.7)

V současné době existuje mnoho algoritmů pro konstrukci Delaunayovy triangulace. Mnoho známých algoritmů používá definici Delaunayovy triangulace jako sekundární triangulační prvek. Proto jsou v těchto algoritmech zaznamenány následující slabiny:

– algoritmy využívají neustále počítané goniometrické funkce, což výrazně zpomaluje proces;

– při studiu vztahu mezi body a základním segmentem vznikají velmi malé úhly a při použití goniometrické funkce Neustále hrozí zánik řádu a dělení 0 z důvodu omezené přesnosti reprezentace dat v počítači, tato situace vyžaduje neustálé dodatečné zpracování.

Nejznámější softwarové produkty vytvářejí Delaunayovu triangulaci pomocí věty o prázdné kouli jako hlavního, primárního principu pro konstrukci trojúhelníků. Algoritmus vypadá takto:

– celá množina bodů je rozdělena na trojúhelníky, tzn. vznikají kombinace tří bodů;

– pro každou kombinaci je nalezena kružnice opsaná a souřadnice jejího středu;

– pokud uvnitř kruhu aktuální kombinace nezůstává jediný bod, pak je tato kombinace trojúhelníkem – součástí Delaunayovy triangulace.

Mezi výhody tohoto algoritmu patří:

– nevyužívání goniometrických funkcí, které nezpomaluje proces výstavby;

– přímá konstrukce Delaunayovy triangulace bez jakýchkoli předběžných konstrukcí;

– jednoduchost všech výpočtů a transformací;

– v důsledku toho je triangulační mřížka reprezentována mnoha trojúhelníky, nikoli jednotlivými čarami.

Takto konstruovaná triangulace je geometrickým základem pro konstrukci izolinií.

Algoritmy pro konstrukci Delaunayovy triangulace lze rozdělit do řady skupin, lišících se strukturou použitých vstupních dat, objemem výpočetních operací, počátečními premisami atd. Uveďme některé z nich.

Slučovací algoritmy zahrnují rozdělení sady zdrojových bodů do podmnožin, vytvoření triangulace na každém z nich a jejich následné spojení do jediné sítě. Podstata jednoho z těchto algoritmů spočívá v následujícím.

Sada počátečních bodů je rozdělena svislými čarami na dvě nebo více částí, poté je každá z nich rozdělena vodorovnými a svislými čarami na přibližně stejné části. Výsledkem je, že celá plocha výchozích bodů je rozdělena na primitiva o třech nebo čtyřech bodech (obr. 2.4), podél kterých jsou sestrojeny jeden nebo dva trojúhelníky.

Sloučení těchto trojúhelníků do jediné sítě se provádí konstrukcí dvou základních linií (P 0 P 1 a P 2 P 3, rýže. 5.7.a), kreslení kružnic s proměnným poloměrem se středem na kolmici k základní čáře (obr. 5.7, b), hledání uzlu dopadajícího na kružnici (bod A, rýže. 5.7. c) a konstrukce nového trojúhelníku (P 0 P 1 A). V tomto případě může být nutné odstranit existující trojúhelník (např. P 0 AB).

Iterační algoritmy jsou založeny na myšlence postupného přidávání bodů do částečně konstruované triangulace s jejím současným vylepšením a rekonstrukcí podle Delaunayových kritérií. V obecný pohled zahrnují několik kroků a scvrkají se na konstrukci trojúhelníku na prvních třech výchozí body a prozkoumání několika možností umístění dalšího bodu. Zejména jsou zvažovány možnosti, aby spadala mimo hranice oblasti modelování, na existující uzel nebo hranu, uvnitř sestrojeného trojúhelníku atd. Každá z těchto možností zahrnuje provedení určité operace: rozdělení hrany na dvě, plochy na tři atd.; načež se výsledné trojúhelníky zkontrolují, zda splňují Delaunayovu podmínku a potřebné rekonstrukce.

Dvouprůchodové algoritmy nejprve zahrnují konstrukci nějaké triangulace, ignorující Delaunayovy podmínky, a poté její rekonstrukci v souladu s těmito podmínkami. Příklad aplikace algoritmu je na obr. 5.8.

Aby se vytvořený model reliéfu přiblížil skutečnému, jsou do něj vloženy další prvky, které zajistí zohlednění a zobrazení jeho lineárních a plošných konstrukčních prvků. Takovými doplňkovými prvky jsou strukturní linie široce používané v topografii, které definují „reliéfní kostru“: povodí, thalwegs, hřebeny, útesy, římsy, jezera, rokle, pobřeží, hranice umělých struktur atd., jejichž souhrn vytváří určitý druh rám pro Delaunayovu triangulaci. Tyto strukturní linie jsou do triangulace zavedeny jako hrany trojúhelníků, čímž je docíleno modelování skutečných reliéfních prvků na pozadí obecných nerovností zemského povrchu. Takové hrany se nazývají strukturální (pevné, nepřekonfigurovatelné), neprotínají hrany jiných trojúhelníků a následně se nemění.

Problém konstrukce povrchového modelu, který bere v úvahu lomené čáry, se nazývá vázaná Delaunayova triangulace, pokud jsou splněny Delaunayovy podmínky pro jakýkoli pár sousedních trojúhelníků, které nejsou odděleny čárami přerušení. Vědci se domnívají, že nejúčinnějším způsobem je vytvořit takovou triangulaci pomocí iteračních algoritmů.

Fragment Delaunayovy triangulace s dalšími v ní zahrnutými prvky je znázorněn na Obr. 5.9, kde jsou vpravo zobrazeny uzly, hrany, hrany a strukturní linie a vlevo jsou zobrazeny strukturní linie terénu (pobřežní linie, okraje roklí atd.) a body se známými značkami.

Algoritmy pro konstrukci Delaunayovy triangulace jsou implementovány s reálnou nebo celočíselnou reprezentací souřadnic uzlů, což může výrazně zvýšit rychlost a přesnost zpracování, ale přináší problémy s vyhledáváním a vyloučením odpovídajících uzlů.

Model TIN lze snadno upravovat přesouváním uzlů, vkládáním nových, mazáním stávajících, změnou polohy jedné nebo několika hran, zavedením nových strukturních čar atd. Takové změny vždy postihnou malou skupinu sousedních trojúhelníků, nevyžadují přestavbu celé sítě a jsou prováděny on-line, namířením kurzoru na odpovídající prvek.

O přesnosti:

Umístěním tyčí na charakteristické prvky reliéfu (například povodí a thalwegs) ignorujeme menší prvky v mezerách. Při konstrukci vrstevnic1 podél takových hran trojúhelníků dochází k chybě, která závisí na velikosti nerovností terénu a úhlu sklonu terénu. Například průměrná chyba při zaměření reliéfu by neměla překročit 1/3 průřezu reliéfu při úhlech sklonu povrchu od 2 do 10 stupňů. Lze spočítat, že při reliéfním úseku 0,5 m by maximální hodnota vynechané nerovnosti (tj. odchylka povrchu země od přímky procházející sousedními tyčemi) neměla překročit (0,5/3)*cos10° = 0,16 m.

Pro přesnost stanovení objemu přepravované zeminy je důležitá i plocha, kterou zabírá nezapočítaný detail reliéfu. Řekněme, že ve čtverci 20x20 m mezi dvěma páry tyčí je válcová konvexita s maximální výškou 0,15 m. Je snadné spočítat, že její nezohlednění při znázornění této plochy pouze dvěma trojúhelníky povede k chyba cca 40 m3. Ne tolik, ale za pozemek o rozloze 1 hektar, který se nachází na kopci nebo v horní (obvykle konvexní) části svahu, získáte 40 * 25 = 1000 m3 přebytečné půdy. Pokud budete hlídkovat dvakrát častěji (tedy každých 10 m), chyba se zmenší čtyřnásobně a bude činit 250 m3 na hektar. Tento faktor lze předem vzít v úvahu, protože pozitivní formy plochého reliéfu mají obvykle konvexní tvar, zatímco negativní formy mají tvar konkávní. Pokud má zkoumaná oblast přibližné údaje o reliéfu, lze z hodnot vrstevnic nebo jednotlivých převýšení snadno vypočítat poloměr zakřivení povrchu a požadovanou hustotu piketů.

Základní definice a vlastnosti

Triangulace je rovinný graf, jehož vnitřní oblasti jsou všechny trojúhelníky.

Vlastnosti:

· Delaunayova triangulace odpovídá jedna ku jedné Voronoiově diagramu pro stejnou sadu bodů.

· V důsledku toho: pokud žádné čtyři body neleží na stejné kružnici, je Delaunayova triangulace jedinečná.

· Delaunayova triangulace maximalizuje minimální úhel mezi všemi úhly všech vytvořených trojúhelníků, čímž se vyhne „tenkým“ trojúhelníkům.

· Delaunayova triangulace maximalizuje součet poloměrů vepsaných koulí.

· Delaunayova triangulace minimalizuje diskrétní Dirichletovu funkci.

· Delaunayova triangulace minimalizuje maximální poloměr minimální okolní koule.

· Delaunayova triangulace v rovině má minimální součet poloměrů kružnic popsaných kolem trojúhelníků ze všech možných triangulace.

Obrázek 1. Triangulace.

Konvexní triangulace je triangulace, pro kterou je minimální mnohoúhelník obklopující všechny trojúhelníky konvexní. Triangulace, která není konvexní, se nazývá nekonvexní.

Problém sestrojení triangulace z dané množiny dvourozměrných bodů se nazývá problém spojení dané body neprotínající se segmenty tak, aby se vytvořila triangulace.

Říká se, že triangulace splňuje Delaunayovu podmínku, pokud žádný z daných triangulačních bodů nespadá do kružnice opsané kolem jakéhokoli sestrojeného trojúhelníku.

Triangulace se nazývá Delaunayova triangulace, pokud je konvexní a splňuje Delaunayovu podmínku.

Obrázek 2. Delaunayova triangulace.

Delaunayova metoda prázdného míče. Konstrukce v obecném případě

Použijme prázdnou kouli, kterou budeme pohybovat, měnit její velikost tak, aby se mohla dotýkat bodů soustavy (A), ale vždy zůstala prázdná.

Umístíme tedy do systému bodů (A) prázdný míč Delaunay. To je vždy možné, pokud zvolíte dostatečně malý míč. Začněme zvětšovat jeho poloměr, přičemž střed koule necháme na místě. V určitém bodě se povrch koule setká s některým bodem i systému (A). To se určitě stane, protože v našem systému nejsou žádné nekonečně velké prázdné prostory. Poloměr prázdné koule budeme dále zvětšovat tak, aby bod i zůstal na jejím povrchu. Chcete-li to provést, budete muset přesunout střed koule z bodu i. Dříve nebo později míč dosáhne svým povrchem jiného bodu v systému (A).

Obr.3

Delaunay simplexy vyplňují prostor bez mezer nebo přesahů.

Popsaná koule žádného simplexu v sobě neobsahuje další body systému.

Nechť je to bod j. Pokračujme ve zvětšování poloměru naší koule, přičemž oba body ponecháme na jejím povrchu. Jak se míč zvětšuje, dosáhne nějakého třetího bodu systému, bodu k. Ve dvourozměrném případě bude náš „prázdný kruh“ v tuto chvíli zafixován, tzn. Bude nemožné dále zvětšovat jeho poloměr a přitom udržovat kruh prázdný. Zároveň identifikujeme elementární dvourozměrnou konfiguraci tří bodů (i, j, k), definujících určitý trojúhelník, jehož zvláštností je, že uvnitř jeho kružnice opsané nejsou žádné další body soustavy (A). V trojrozměrném prostoru není koule definována třemi body. Pokračujme ve zvětšování jeho poloměru, přičemž zachováme všechny tři body nalezené na jeho povrchu. To bude možné, dokud povrch koule nedosáhne čtvrtého bodu l soustavy. Poté bude pohyb a růst prázdné koule nemožný. Nalezené čtyři body (i,j,k,l) ​​definují vrcholy čtyřstěnu, který se vyznačuje tím, že uvnitř jeho opsané koule nejsou žádné další body soustavy (A). Takový čtyřstěn se nazývá Delaunay simplex.

V matematice je simplex nejjednodušší obrazec v prostoru dané dimenze: čtyřstěn - v trojrozměrném prostoru; trojúhelník - ve dvou rozměrech. Libovolné tři (čtyři) body soustavy, které neleží ve stejné rovině, vždy definují určitý simplex. Bude to však Delaunay simplex pouze v případě, že jeho popsaná koule bude prázdná. Jinými slovy, Delaunayovy simplice jsou určeny speciálním výběrem trojic (čtyřnásobků) bodů v systému (A).

Zkonstruovali jsme jeden Delaunayův simplex, ale umístěním prázdné koule na různá místa a opakováním stejného postupu můžeme definovat další. Uvádí se, že množina všech Delaunayových simplicí systému (A) vyplňuje prostor bez přesahů a mezer, tzn. implementuje rozdělení prostoru, ale tentokrát na čtyřstěny. Tento oddíl se nazývá Obklady Delaunay(obr. 3).

Aplikace Delaunayovy triangulace

Delaunayovy triangulace se často používají v euklidovském prostoru. Euklidovský minimální kostra bude zaručeně ležet na Delaunayově triangulaci, takže některé algoritmy používají triangulaci. Prostřednictvím Delaunayovy triangulace je také přibližně vyřešen euklidovský problém obchodního cestujícího.

Při 2D interpolaci rozděluje Delaunayova triangulace rovinu na nejtlustší možné trojúhelníky, čímž se vyhne příliš ostrým a příliš tupým úhlům. Pomocí těchto trojúhelníků můžete sestavit například bilineární interpolaci.

Dalším často se vyskytujícím problémem v geoinformatice je výstavba svahových expozic. Zde je nutné určit dominantní směry svahů podle světových stran a rozdělit povrch na oblasti, ve kterých určitý směr dominuje. Protože určení expozice nemá smysl pro horizontální oblasti povrchu, oblasti, které jsou horizontální nebo mají mírný sklon, jsou přiřazeny do samostatné oblasti, např.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Obr.4.

Problém výpočtu sklonových expozic se obvykle používá k analýze osvětlení Země. V tomto ohledu je často potřeba dodatečně zohlednit aktuální polohu Slunce, tzn. expozice se vypočítá jako směr mezi normálou k trojúhelníku a směrem ke Slunci.

Každý triangulační trojúhelník lze tedy klasifikovat podle principu příslušnosti k určité oblasti. Poté stačí zavolat algoritmus výběru regionu.

Triangulace je aproximace povrchu modelovaného objektu trojúhelníkovými deskami, které jsou od něj vzdáleny ve vzdálenosti nepřesahující určitou zadanou hodnotu 6. Všechny trojúhelníkové desky musí být spojeny dohromady. Jejich vrcholy leží na povrchu. Se sadou trojúhelníkových desek se pracuje snadněji než s běžným povrchem. Trojúhelníkové desky budeme nazývat trojúhelníky. U trojúhelníku se rychle vypočítá vzdálenost k danému bodu nebo průsečíku s danou přímkou ​​v prostoru. Triangulace tváří se provádí pro vizuální vnímání geometrického modelu, takže strany trojúhelníků jsou vybrány tak, aby oko nemohlo zaznamenat zalomení.

Při zobrazování geometrických objektů pomocí trojúhelníků na parametrických rovinách ploch je třeba zkonstruovat prostorovou triangulaci ploch tělesa výpočtem pole bodů v prostoru a pole normál k plochám tělesa v těchto bodech pomocí pole dvourozměrné body Pro rychlé zobrazení těles jsou jejich plochy aproximovány trojúhelníkovými deskami postavenými na normálních bodech, aby bylo možné určit chování světelných paprsků interagujících s plochami těles. Kresby tónů v předchozích kapitolách a v této kapitole jsou vytvořeny pomocí triangulace.

V důsledku povrchové triangulace chceme mít pole dvourozměrných bodů v parametrické rovině a pole trojic celých čísel, což jsou počty bodů v prvním uvedeném poli. Každý trojúhelník bude tedy reprezentován třemi čísly jeho vrcholů v poli parametrů. Pro každý dvourozměrný bod parametrické oblasti lze vypočítat prostorový bod na povrchu a normálu povrchu v něm. Prostorové body a normály mohou být uloženy v polích podobných 2D poli bodů.

Podívejme se na některé metody triangulace. Pro rovné povrchy existují cenově výhodné triangulační metody, ve kterých jsou trojúhelníky konstruovány na hraničních bodech povrchu a není potřeba hledat body uvnitř parametrické oblasti.

Delaunayova triangulace.

Podívejme se na nějakou oblast v letadle. Oblast budeme nazývat konvexní, pokud se při pohybu po její hranici musíte otočit pouze jedním směrem (pouze doleva nebo pouze doprava). Algoritmus Delaunay lze použít k triangulaci konvexních rovinných oblastí. Tento algoritmus nebudeme moci přímo aplikovat na triangulaci volně tvarovaných ploch, ale použijeme jeho metodu pro konstrukci trojúhelníků.

Rýže. 9.7.1. Konvexní oblast s danými body uvnitř

Nechť je dána nějaká konvexní dvourozměrná oblast ohraničená uzavřenou přerušovanou čarou a množina bodů uvnitř této oblasti (obr. 9.7.1).

Zadanou oblast je nutné rozdělit na trojúhelníky, jejichž vrcholy jsou dané body uvnitř oblasti a vrcholy přerušované čáry, která ji ohraničuje. Trojúhelníky se nesmí překrývat a jejich strany se mohou protínat pouze ve vrcholech.

K vyplnění určené oblasti lze sestavit několik různých sad trojúhelníků. Ve všech případech je počet trojúhelníků roven , kde K je počet vrcholů ohraničující křivky, I je počet daných bodů uvnitř oblasti.

Rýže. 9.7.2. Výběr třetího bodu Delaunayova algoritmu

Triangulace oblasti bude Delaunayova triangulace, pokud uvnitř kruhu popsaného kolem každého trojúhelníku nejsou žádné vrcholy jiných trojúhelníků. Delaunayova triangulace staví trojúhelníky co nejblíže rovnoúhelníku (neumožňuje konstrukci nepřiměřeně protáhlých trojúhelníků).

Dá se to nazvat vyváženým. Delaunayova triangulace bude jedinečná, pokud žádné čtyři vrcholy neleží na stejné kružnici.

Podívejme se na Delaunayovu triangulaci. Vrcholy lomené čáry ohraničující region a dané body uvnitř regionu budeme nazývat vrcholy triangulace. Strany trojúhelníků budeme nazývat hranami. Mezi hranami vybereme segmenty ohraničující křivky, které budeme říkat hraniční hrany. Orientujme všechny hraniční hrany tak, aby konvexní oblast ležela nalevo od každé hrany. Nechť je třeba sestrojit trojúhelník, jehož stranou je hraniční hrana AB, znázorněná na Obr. 9.7.2.

Přes vrcholy A, B a jakýkoli vrchol, který s nimi neleží na stejné čáře, lze nakreslit kružnici. Jako třetí vrchol trojúhelníku zvolíme vrchol V, odpovídající kružnice neobsahuje další vrcholy na stejné straně vzhledem k úsečce AB, na které leží bod V. Pro hraniční hranu může v obecném případě jeden takový vrchol být nalezen. Budeme mu říkat nejbližší. Střed kružnice procházející body A, B a V leží v průsečíku kolmiček ke středům úseček AB, BV a VA. Poloha středu kružnice bude charakterizována parametrem t úsečky MN, kolmé na hranu AB, stejné délky a procházející středem hrany AB.

Rýže. 9.7.3. Delaunayův triangulační proces

Pro všechny vrcholy ležící nalevo od segmentu AB má nejbližší vrchol nejmenší parametr t. Kruh odpovídající nejbližšímu vrcholu neobsahuje další vrcholy vlevo od segmentu AB. Nechť jsou vrcholy A, B a V popsány pomocí dvourozměrných poloměrových vektorů. Poloměrové vektory středů segmentů AB a BV budou stejné

Hodnota parametru t přímky, odpovídající poloze na ní středu kružnice procházející body A, B a V, je rovna

Pro vrchol nejblíže vlevo od segmentu AB má parametr t minimální hodnotu.

Orientujme všechny hraniční hrany tak, aby plocha určená k triangulaci ležela nalevo od každé z nich. Začneme konstruovat trojúhelníky z libovolné hraniční hrany. Najdeme pro něj nejbližší vrchol, jehož odpovídající kružnice jiné vrcholy neobsahuje. Pro hraniční hranu AB nechť najdeme nejbližší vrchol V. Poté sestrojíme trojúhelník ABV a převedeme hranu AB do kategorie neaktivní. Budeme nazývat neaktivní hrany a vrcholy, které se neúčastní triangulačního algoritmu. Pokud mezi hraničními hranami není žádná hrana BV, pak sestrojíme novou hraniční hranu na segmentu VB. Je-li mezi hraničními hranami hrana BV, pak ji a vrchol B přeneseme do kategorie neaktivní. Pokud mezi hraničními hranami není žádná hrana VA, pak sestrojíme novou hraniční hranu na segmentu AV. Je-li mezi hraničními hranami hrana VA, pak ji a vrchol A přeneseme do kategorie neaktivní. Proces triangulace je znázorněn na Obr. 9.7.3.

Rýže. 9.7.4. Delaunayova triangulace

Triangulaci dokončíme, když se všechny vrcholy a hrany stanou neaktivními. Výsledek triangulace dané oblasti je na Obr. 9.7.4.

Triangulace korekční metodou.

Uvažujme triangulaci určitého povrchu s pravoúhlou oblastí pro určení parametrů Oblast pro definování parametrů povrchu rozdělíme na obdélníkové buňky s dvourozměrnými čarami.Tyto čáry tvoří pravoúhlou síť. Mějme parametrické vzdálenosti mezi sousedními čarami podle vzorce (9.4.7) za stejné

Mějme parametrické vzdálenosti mezi sousedními čarami podle vzorce (9.4.8) za stejné

Sestrojením úhlopříček ve všech pravoúhlých buňkách získáme triangulaci povrchu (získáme sadu trojúhelníků splňující požadavky). Na Obr. 9.7.5 ukazuje triangulaci rotační plochy pomocí popsané metody.

Uvažujme triangulaci plochy s libovolnou hranicí. Triangulační metodu postavíme na korekci hraničními obrysy výše popsané triangulace povrchu s pravoúhlou plochou pro stanovení parametrů.

Rýže. 9.7.5. Triangulace plochy s pravoúhlou doménou pro definování parametrů

Nechť je hranice povrchu v oblasti definice parametru popsána několika neprotínajícími se dvourozměrnými obrysy (2.12.7). Jeden z obrysů je vnější a obsahuje zbývající obrysy. Pro kladný směr pro každou konturu vezmeme směr, ve kterém je při pohybu podél, oblast definice povrchu vždy vlevo od kontury, při pohledu k normále povrchu. Sestrojme polygony v kladném směru hraničních vrstevnic plochy definice povrchu. Chcete-li sestrojit hraniční polygony, musíte jít po hraničních obrysech povrchu s nějakým proměnným krokem a vyplnit pole dvourozměrných bodů, jejichž souřadnice jsou parametry povrchu. Polygon postavíme z bodů na parametrické rovině, ale krok při pohybu z jednoho bodu do druhého bude určen z prostorové geometrie, konkrétně z podmínky, že průhyb oblouku křivky mezi sousedními body není větší než daný hodnota. Parametrické kroky pro konstrukci polygonu pro obrysovou křivku hranice povrchu vypočítáme pomocí vzorce (9.4.4).

Každý mnohoúhelník se skládá z uspořádané sady dvourozměrných bodů, přičemž každý úsek mnohoúhelníku lze považovat za dvourozměrný úsečka postavená na dvou sousedních bodech. Takové oblasti použijeme jako hraniční hrany a body polygonů, na kterých jsou hrany založeny, budou použity jako triangulační vrcholy. Protože oblast pro určení parametrů povrchu leží nalevo od hraničních polygonů, při konstrukci trojúhelníků pro každou hraniční triangulační hranu byste měli hledat třetí vrchol trojúhelníku vlevo od hrany.

Pojďme určit, které uzly leží uvnitř hraničních polygonů a které leží na hranici nebo mimo oblast definice povrchu. Pomocí těchto informací roztřídíme buňky obdélníkové mřížky do dvou skupin. První skupina zahrnuje buňky, které leží zcela v oblasti, kde se určují parametry povrchu (buňky by se neměly dotýkat hraničních polygonů). Druhá skupina zahrnuje zbývající buňky (ležící mimo oblast definice povrchu nebo protnuté hraničními polygony).

Rýže. 9.7.6. Nedokončená triangulace povrchu

Uvnitř každé buňky první skupiny sestrojíme pomocí úhlopříčky dva trojúhelníky. Dostaneme tak nedokončenou triangulaci. Příklad konstrukce trojúhelníků v buňkách první skupiny pro rotační plochu omezenou obrysy je na Obr. 9.7.6.

Na neprotínajících se stranách buněk druhé skupiny sestrojíme hraniční hrany a nasměrujeme je tak, aby odpovídající buňka byla nalevo od hrany. Kolem buněk první skupiny zkonstruujeme uzavřenou lomenou čáru (případně několik uzavřených čar) tak, že při pohybu po ní leží část plochy, která není rozdělena na trojúhelníky, vlevo, při pohledu k normále plochy . Přímé úseky této přerušované čáry také použijeme jako hraniční hrany. Všechny hrany budeme považovat za rovné. K dokončení triangulace potřebujeme sestrojit trojúhelníky mezi hraničními hranami. Pro každou hranu budeme hledat vrchol, který leží nalevo od ní a lze z něj sestrojit trojúhelník. Budeme hledat vrchol pouze mezi těmi vrcholy, které leží ve stejné buňce s okrajem. Pro výběr vrcholu použijeme Delaunayovu metodu popsanou výše a znázorněnou na Obr. 9.7.2. Pokud je takový vrchol nalezen, měli byste zkontrolovat, zda se dvě nové hrany trojúhelníku protínají s nějakou hraniční hranou. Nechte najít nejbližší vrchol V pro hraniční hranu AB a zkontrolujte, že segmenty BV a VA neprotínají další hraniční hrany. Poté sestrojíme trojúhelník ABV a převedeme hranu AB do neaktivní kategorie. Pokud mezi hraničními hranami není hrana BV, pak sestrojíme novou hraniční hranu na segmentu VB, ale pokud je mezi hraničními hranami hrana BV, tak ji i s vrcholem B převedeme do kategorie neaktivní. Pokud mezi hraničními hranami není hrana VA, pak sestrojíme novou hraniční hranu na segmentu AV, ale pokud je mezi hraničními hranami hrana VA, tak ji i s vrcholem A převedeme do kategorie neaktivní.

Pokud segment nebo VA protíná další hraniční hrany, pak přejdeme k hledání nejbližšího vrcholu pro další hraniční hranu. Triangulace bude dokončena poté, co budou všechny hrany a vrcholy klasifikovány jako neaktivní.

Rýže. 9.7.7. Triangulace korekční metodou

Na Obr. 9.7.7 ukazuje triangulaci povrchu metodou korekce trojúhelníků v buňkách protnutých hraničními obrysy. Na Obr. 9.7.8 se pomocí výsledné triangulace zobrazí samotný povrch.

Pokud hraniční polygony a povrch mají nějakou symetrii, pak bude mít triangulace pomocí korekční metody podobnou symetrii.

Triangulace absorpční metodou.

Zvažme další triangulační metodu. Z hlediska rychlosti je horší než Delaunayova triangulace a její modifikace. Pro zahájení triangulační procedury je nutné znázornit povrchovou hranici ve formě uzavřených polygonů. Během procesu triangulace budeme muset určit kroky na základě parametrů povrchu. Při známém směru pohybu jsou tyto kroky určeny vzorci (9.4.6). Přibližné kroky pro parametry povrchu lze nalézt následovně. Definujme oblast na rovině parametrů kolem určitého bodu tak, že jakýkoli prostorový segment z bodu do bodu v této oblasti nebude dále než daná hodnota S od povrchu.

K tomu vypočítáme přípustné přírůstky parametrů podél souřadnic

kde jsou koeficienty první a druhé kvadratické formy povrchu v bodě . Jako hranici požadované oblasti vezmeme elipsu se středem v bodě a poloosy . Tato elipsa má rovnici

Pokud chcete najít bod v rovině vedle bodu ve směru daném úhlem s osou a, pak jeho parametry budou

Nejprve uvažujme jednodušší případ, kdy je oblast parametrů povrchu omezena na jeden vnější obrys. Hranici povrchu aproximujeme uzavřeným polygonem na parametrické oblasti. Při konstrukci triangulace použijeme pracovní polygon, který v tomto případě budeme brát jako polygon vnějšího obrysu. Do výsledného pole dvourozměrných bodů přidáme body polygonu. Z okraje pracovní oblasti budeme stavět trojúhelníky a zužovat ji, dokud v pracovní oblasti nezůstanou pouze tři body.

Najdeme v pracovním mnohoúhelníku vrchol, ve kterém přechází do oblasti. Takový bod vždy existuje a úhel natočení v něm je menší. Označme tento bod O a jeho parametry jako Blízko tohoto bodu sestrojíme jeden nebo dva trojúhelníky v závislosti na úhlu natočení. Pokud je úhel menší, pak na těchto třech bodech postavíme jeden trojúhelník (obr. 9.7.9). Jinak na tomto sestrojíme dva trojúhelníky, dva sousední a jeden nový bod (obr. 9.7.11). Nový bod je označen P. Budeme hledat bod P na úhlopříčce rovnoběžníku B OS P. Leží-li vrchol rovnoběžníku uvnitř elipsy (obr. 9.7.10), pak jej budeme brát jako bod P Jinak budeme považovat průsečík elipsy a úhlopříčky rovnoběžníku za bod P . V druhém případě není vůbec nutné hledat průsečík elipsy a úsečky.

Souřadnice bodu P jsou určeny přes souřadnice bodů O BC

Úhel segmentu OP s horizontálou je určen rovností

(9.7.8)

Tyto údaje umožňují určit polohu bodu P vzhledem k elipse (9.7.5).

V případě znázorněném na Obr. 9.7.9 sestrojme trojúhelník (zapamatujme si čísla jeho vrcholů) a v pracovní oblasti vymažte bod O. V případě znázorněném na Obr. 9.7.11 sestrojíme dva trojúhelníky a v pracovní oblasti nahradíme bod O bodem P a ten umístíme do výsledného pole bodů. Na Obr. Obrázek 9.7.12 ukazuje mnohoúhelník získaný po sestrojení dvou trojúhelníků a odstranění bodu O. V obou případech bude bod O odstraněn z pracovního mnohoúhelníku a pracovní mnohoúhelník se zúží. Všimněte si, že trojúhelníky lze konstruovat pouze tehdy, když se pracovní plocha po zúžení sama neprotíná.

Rýže. 9.7.9. Konstrukce trojúhelníku

Rýže. 9.7.10. Výsledek polygon

Rýže. 9.7.11. Konstrukce dvou trojúhelníků

Rýže. 9.7.12. Výsledek polygon

Takové situace jsou znázorněny na Obr. 9.7.13. Mohou nastat, když strany sestrojených trojúhelníků protínají strany pracovní plochy, které s nimi nesousedí. Před sestrojením nového trojúhelníku jako v případě znázorněném na Obr. 9.7.9 a v případě znázorněném na Obr. 9.7.11, je třeba provést kontrolu, aby se zajistilo, že výsledný polygon neprotíná sám sebe.

Navíc při určování polohy bodu P je důležité, aby byl v dostatečné vzdálenosti od ostatních bodů pracovní oblasti a nepřibližoval se k segmentům spojujícím body oblasti. Jinak mohou v budoucnu při konstrukci trojúhelníků nastat potíže. Před zúžením pracovního polygonu byste proto měli zkontrolovat, zda se výsledný mnohoúhelník neprotne. Pokud není možné sestrojit trojúhelník (trojúhelníky) v blízkosti bodu O, pak byste místo toho měli najít jiný bod, ve kterém se mnohoúhelník zalomí uvnitř obrysu více než v jiných, a provést v něm popsané akce.

Dále s upravenou pracovní oblastí provedeme stejné akce, které jsme právě popsali. Najdeme v pracovním mnohoúhelníku bod, ve kterém se uvnitř plochy otočí více než v jiných bodech, ověříme možnost zúžení mnohoúhelníku v něm sestrojením jednoho nebo dvou trojúhelníků a mnohoúhelník zúžíme.

Rýže. 9.7.13. V tomto rohu nemůžete stavět trojúhelníky.

Pokračujeme-li v tomto procesu, rozšíříme pole dvourozměrných bodů a pole trojúhelníků a zároveň zúžíme pracovní polygon, zmenšíme plochu, kterou pokrývá, a počet jeho bodů. V určité fázi těchto akcí obdržíme pracovní polygon sestávající ze tří bodů. Postavme v těchto bodech poslední trojúhelník, zrušme pracovní oblast a dokončeme triangulaci. V popsaném triangulačním způsobu je oblast ohraničená pracovní oblastí jakoby eliminována odříznutím trojúhelníků z ní.

Uvažujme obecný případ, kdy je oblast parametrů povrchu omezena jedním vnějším obrysem a několika vnitřními obrysy, které leží zcela uvnitř vnějšího obrysu. Hranici povrchu aproximujeme uzavřenými polygony na parametrické doméně. Pro každý obrys postavíme vlastní polygon. Stejně jako u vrstevnic i u polygonů na nich postavených musí být splněno pravidlo jejich vzájemné orientace. Orientace vnitřních mnohoúhelníků musí být opačná než orientace vnějšího mnohoúhelníku. Začněme konstruovat triangulaci s vnějším obrysovým polygonem. Dejme jeho body do výsledného pole dvourozměrných bodů a udělejme ze samotného mnohoúhelníku funkční.

Trojúhelníky sestrojíme stejně jako v případě jednoduše spojené oblasti. Najdeme bod O v pracovní oblasti, ověříme možnost zúžení pracovní oblasti tam a zúžíme oblast. Pokud existují vnitřní obrysy, je obtížnější zkontrolovat možnost zúžení pracovní oblasti ve vybraném bodě. Kromě popsaných kontrol průsečíku stran trojúhelníků se stranami pracovní plochy je nutné zkontrolovat průnik stran trojúhelníků se stranami všech vnitřních polygonů.

Prověříme možnost sestrojit dva trojúhelníky v bodě O (obr. 9.7.11) a zjistíme, že nový bod P, jakmile je sestrojen, bude spadat do jednoho z vnitřních polygonů nebo bude v nepřijatelné blízkosti jeho segmentů. V tomto případě nebudeme konstruovat bod P, ale místo toho zahrneme tento vnitřní mnohoúhelník do pracovního mnohoúhelníku sestrojením dvou trojúhelníků znázorněných na Obr. 9.7.14.

Abychom do pracovního mnohoúhelníku zahrnuli body jednoho z vnitřních mnohoúhelníků, najdeme mezi body vnitřního mnohoúhelníku bod nejblíže bodu C (sousedícímu s bodem O) pracovního mnohoúhelníku.

Sestrojme trojúhelníky v bodech OCF a CEF a mezi body O a C pracovní oblasti vložíme body vnitřního mnohoúhelníku, počínaje bodem F a konče bodem E. Tím přerušíme pracovní oblast na segmentu OS, přerušíme vnitřní polygon na segmentu EF a sjednotit je se segmenty OF a EU.

Rýže. 9.7.14. Konstrukce dvou trojúhelníků

Rýže. 9.7.15. Slučování vnějších a vnitřních polygonů

Výsledek fúze je na obr. 9.7.15. Před sloučením vnějšího a vnitřního polygonu je samozřejmě nutné provést kontroly správnosti této operace.

Dále budeme pokračovat ve zužování pracovní oblasti popsaným způsobem, dokud se neocitneme v těsné blízkosti další vnitřní oblasti a zahrneme ji do pracovní oblasti. Díky tomu budou všechny vnitřní polygony zahrnuty do pracovního polygonu, který by měl být zúžen na poslední tři body. V důsledku toho bude celá vícenásobně spojená oblast pro stanovení parametrů povrchu pokryta trojúhelníky.

Rýže. 9.7.16. V tomto rohu nemůžete stavět trojúhelníky.

Mohou nastat situace, kdy na daných polygonech není možné sestrojit jeden trojúhelník. Na Obr. Obrázek 9.7.16 ukazuje oblast omezenou dvěma polygony, z nichž každý se skládá ze čtyř segmentů. U vnějšího mnohoúhelníku nemůžeme pokračovat v triangulaci, protože vnitřní mnohoúhelník stojí v cestě. V tomto případě najdeme dva sousední body B a C polygonu, pro které můžeme sestrojit trojúhelník HRV. Bod P se promítá do středu strany BC a nachází se od ní v takové vzdálenosti, aby nový trojúhelník neprotínal mnohoúhelníky.

Jiné metody triangulace.

Existují i ​​jiné způsoby triangulace. Například po sestrojení polygonů vnějších a vnitřních obrysů oblasti definice povrchu lze zvolit jinou strategii konstrukce trojúhelníků. Další možností je spojit vnější a vnitřní polygony do jednoho polygonu před zahájením triangulace. Pomocí určitého algoritmu můžete „načrtnout“ body uvnitř oblasti definice parametru a provést Delaunayovu triangulaci pomocí nich a bodů polygonů hraničních vrstevnic. Existují algoritmy, které nejprve konstruují velké trojúhelníky a poté je rozdělují na zvládnutelné velikosti.

Triangulace těla.

Triangulace tělesa je množina trojúhelníků získaná triangulací povrchů jeho ploch. Triangulace jednotlivých ploch se liší od triangulace ploch tělesa v tom, že v druhém případě musí být hraniční polygony pro sousední plochy konzistentní (obr. 9.7.17).

Rýže. 9.7.17. Konzistence polygonu hranice obličeje těla

Řezy polygonů sousedních ploch procházejících podél společných hran budou konzistentní, pokud se jejich body v prostoru shodují.

Aplikace triangulace.

Trojúhelníky vytvořené jako výsledek triangulace se používají k získání tónových obrazů. Na Obr. 9.7.18 a 9.7.19 znázorňují triangulace líce plechového tělesa, jehož tónový obraz je na Obr. 6.5.1.

Rýže. 9.7.18. Triangulace obličeje pomocí korekční metody

Rozdělení oboru určování povrchových parametrů na trojúhelníky lze použít v integrálech (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) při výpočtu geometrických charakteristik těles . Během numerické integrace by se parametrický krok pro křivky měl vypočítat pomocí vzorce (8.11.5) a pro povrchy by se měly parametrické kroky vypočítat pomocí vzorců (8.11.1) a (8.11.2).

Triangulace pro konečnou množinu bodů S je problém triangulace konvexního trupu CH(S) obklopujícího všechny body množiny S. Přímé úsečky v triangulaci se nemohou protínat - mohou se setkávat pouze ve společných bodech patřících do množiny S. Od přímé úsečky uzavírají trojúhelníky, budeme je považovat za žebra. Na Obr. Obrázek 1 ukazuje dvě různé verze triangulace pro stejnou sadu bodů (kružnice nakreslené na těchto obrázcích budeme dočasně ignorovat).

Rýže. 1

Pro danou množinu bodů S můžeme vidět, že všechny body z množiny S lze rozdělit na hraniční body – ty body, které leží na hranici konvexního trupu CH(S), a vnitřní body – ty ležící uvnitř konvexního trup CH(S). Hrany získané triangulací S můžete také klasifikovat jako skořápková žebra A vnitřní žebra. Hrany trupu zahrnují hrany umístěné podél hranice konvexního trupu CH(S) a vnitřní hrany zahrnují všechny ostatní hrany, které tvoří síť trojúhelníků uvnitř konvexního trupu. Všimněte si, že každá hrana skořepiny spojuje dva sousední hraniční body, zatímco vnitřní hrany mohou spojovat dva body libovolného typu. Konkrétně, pokud vnitřní hrana spojuje dva hraniční body, pak je to tětiva konvexního trupu CH(S). Všimněte si také, že každá hrana triangulace je hranicí dvou oblastí: každá vnitřní hrana je mezi dvěma trojúhelníky a každá hrana pláště je mezi trojúhelníkem a nekonečnou rovinou.

Jakákoli sada bodů, kromě některých triviálních případů, umožňuje více než jednu metodu triangulace. Je tu ale pozoruhodná vlastnost: jakákoli metoda triangulace pro danou množinu určuje stejný počet trojúhelníků, což vyplývá z věty:

Věta o triangulaci množiny bodů. Předpokládejme, že množina bodů S obsahuje n>3 bodů a ne všechny jsou kolineární. Navíc i body z nich jsou vnitřní (tj. leží uvnitř konvexního trupu CH(S). Potom jakákoli metoda triangulace množiny S bude mít za následek přesně n + i - 2 trojúhelníky.

Abychom dokázali větu, nejprve uvažujeme triangulaci n-i hraničních bodů. Protože jsou to všechny vrcholy konvexního mnohoúhelníku, výsledkem takové triangulace budou (n - i) - 2 trojúhelníky. (To není těžké ověřit a navíc lze prokázat, že jakákoli triangulace libovolný M-stranný mnohoúhelník - konvexní nebo nekonvexní - obsahuje m - 2 trojúhelníky). Nyní zkontrolujme, co se stane s triangulací při přidávání zbývajících i vnitřních bodů, vždy jednoho. Tvrdíme, že přidání každého takového bodu zvýší počet trojúhelníků o dva. Při přidávání vnitřního bodu mohou nastat dvě situace, znázorněné na Obr. 2. Za prvé, bod může být uvnitř nějakého trojúhelníku a pak je takový trojúhelník nahrazen třemi novými trojúhelníky. Za druhé, pokud se bod shoduje s jednou z triangulačních hran, pak je každý ze dvou trojúhelníků sousedících s touto hranou nahrazen dvěma novými trojúhelníky. Z toho vyplývá, že po sečtení všech bodů i bude celkový počet trojúhelníků (n - i - 2) + (2i), nebo jednoduše n + i - 2.

Rýže. 2

V této části představíme algoritmus pro generování speciálního typu triangulace známého jako Delaunayova triangulace. Tato triangulace je dobře vyvážená v tom smyslu, že vytvořené trojúhelníky mají tendenci být rovnoúhelníkové. Například triangulace znázorněná na Obr. 1a lze připsat typu Delaunayovy triangulace a na Obr. 1b triangulace obsahuje několik vysoce protáhlých trojúhelníků a nelze je připsat typu Delaunay. Na Obr. Obrázek 3 ukazuje příklad Delaunayovy triangulace pro množinu velkého počtu bodů.

Rýže. 3

K vytvoření Delaunayovy triangulace potřebujeme několik nových definic. Množina bodů je považována za kruhovou, pokud existuje kružnice, na které leží všechny body v množině. Taková kružnice bude opsána pro danou množinu bodů. Kružnice opsané trojúhelníku prochází všemi třemi jeho (nekolineárními) vrcholy. Říká se, že kružnice bude bez bodu vzhledem k dané množině bodů S, pokud uvnitř kružnice nebudou žádné body z množiny S. Avšak body z množiny S mohou být umístěny na kružnici, která je nejvíce bez bodu.

Triangulace množiny bodů S bude Delaunayova triangulace, jestliže kružnice opsaná pro každý trojúhelník je bez bodů. V triangulačním diagramu Obr. Obrázek 1a ukazuje dva kruhy, které jasně neobsahují další body uvnitř (můžete nakreslit kruhy pro jiné trojúhelníky, abyste se ujistili, že jsou také volné od bodů sady). Toto pravidlo není ve schématu na Obr. 16 - jeden bod jiného trojúhelníku spadá do nakreslené kružnice, proto tato griangulace nepatří do Delaunayova typu.

Ohledně bodů v množině S lze učinit dva předpoklady pro zjednodušení triangulačního algoritmu. Za prvé, aby triangulace vůbec existovala, musíme předpokládat, že množina S obsahuje alespoň tři body a že nejsou kolineární. Za druhé, aby byla Delaunayova triangulace jedinečná, je nutné, aby žádné čtyři body z množiny S neležely na stejné kružnici opsané. Je snadné vidět, že bez takového předpokladu nebude Delaunayova triangulace jedinečná, protože 4 body na jedné opsané kružnici nám umožňují realizovat dvě různé Delaunayovy triangulace.

Náš algoritmus funguje tak, že neustále zvětšuje aktuální triangulaci o jeden trojúhelník po druhém. Zpočátku se současná triangulace skládá z jedné hrany pláště, na konci algoritmu se z aktuální triangulace stane Delaunayova triangulace. Při každé iteraci algoritmus hledá nový trojúhelník, ke kterému se připojuje okraj aktuální triangulace.

Definice hranice závisí na následující schéma klasifikace hran Delaunayovy triangulace vzhledem k současné triangulaci. Každá hrana může být Spící, naživu nebo mrtví:

• spací žebra: okraj Delaunayovy triangulace je nečinný, pokud ještě nebyl detekován algoritmem;
• živá žebra: žebro je živé, pokud je nalezeno, ale je známa pouze jedna sousední oblast;
• mrtvá žebra: Hrana je považována za mrtvou, pokud je nalezena a jsou známy obě sousední oblasti.

Zpočátku je živá jediná hrana patřící do konvexního i laloku - k ní přiléhá neohraničená rovina a všechny ostatní hrany jsou nečinné. Jak algoritmus funguje, okraje přecházejí ze spánku přes živé až po mrtvé. Hranice v každé fázi se skládá ze sady živých hran.

Při každé iteraci se vybere kterákoli z hran hranice a ta se podrobí zpracování, které spočívá v hledání neznámé oblasti, ke které hrana e patří. Pokud se ukáže, že tato oblast je trojúhelník f, definovaný pomocí koncové body hrany e a některého třetího vrcholu v, pak se hrana e stane mrtvou, protože obě oblasti k ní přiléhající jsou nyní známé. Každá z dalších dvou hran trojúhelníku t je převedena do následujícího stavu: ze spánku do živého nebo ze živého do mrtvého. Zde se bude nazývat vrchol v sdružené s hranou e. V opačném případě, pokud se neznámá oblast ukáže jako nekonečná rovina, hrana e jednoduše zemře. V tomto případě hrana e nemá sdružený vrchol.

Na Obr. Obrázek 4 ukazuje činnost algoritmu, kde akce probíhá shora dolů a sláva doprava. Ohraničení v každé fázi je zvýrazněno silnou čarou.

Algoritmus je implementován v programu delaunayTriangulate. Program dostane pole s n bodů a vrátí seznam trojúhelníků představujících Delaunayovu triangulaci. Implementace využívá třídu kruhového seznamu a třídy ze sekce Geometric Data Structure. Třída Dictionary může být libovolný slovník, který podporuje požadované operace. Můžete například přepsat #define Dictionary RandomizedSearchTree .

Seznam * (Bod s, int n) ( Bod p; Seznam *trojúhelníky = nový seznam ; Slovník hranice(hranaCmp); Hrana *e = hrana trupu(s, n); hranice.vložte(e); while (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(hranice, p, e->org); updateFrontier(hranice, e ->dest, p); trojúhelníky->insert(trojúhelník(e->org, e->dest, p)); ) smazat e; ) vrátit trojúhelníky; )

Rýže. 4

Trojúhelníky, které tvoří triangulaci, se zapisují do seznamu trojúhelníků. Hranici představuje slovník hraničních živých hran. Každá hrana je nasměrována tak, že její neznámá oblast (která má být určena) leží napravo od hrany. K vyhledání slovníku se používá funkce porovnání edgeCmp. Porovnává počáteční body dvou hran; pokud jsou stejné, pak se porovnávají jejich koncové body:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) návrat 1; if (a->org > b->org) return 1; pokud (a->dest< b->cíl) návrat -1; if (a->dest > b->dest) return 1; návrat 0; )

Jak se hranice mění z jednoho kroku na další a jak funkce updateFrontier upravuje okrajový slovník ohraničení, aby odrážel tyto změny? Když se k hranici připojí nový trojúhelník t, změní se stavy tří hran trojúhelníku. Hrana trojúhelníku t sousedící s hranicí se změní z živé na mrtvou. Funkce updateFrontier může tuto hranu ignorovat, protože by již měla být odstraněna ze slovníku při volání funkce removeMin. Každá ze dvou zbývajících hran trojúhelníku t změní svůj stav ze spánku na živý, pokud nebyly dříve zaznamenány ve slovníku, nebo ze živého na mrtvý, pokud je okraj již ve slovníku. Na Obr. 5 ukazuje oba případy. Podle obrázku zpracujeme živou hranu af a po zjištění, že bod b je její konjugát, přidáme k aktuální triangulaci trojúhelník afb. Poté hledáme okrajový fb ve slovníku a jelikož tam ještě není a je objeven poprvé, změní se jeho stav ze spánku na živý. Pro úpravu slovníku otočíme hranu fb tak, aby k ní přilehlá neznámá oblast ležela napravo od ní a tuto hranu zapíšeme do slovníku. Poté ve slovníku najdeme hranu ba - jelikož je v něm, je již živá (známá oblast k ní přiléhající je trojúhelník abc). Protože neznámá oblast, trojúhelník afb, byla právě objevena, je tato hrana odstraněna ze slovníku.

Funkce updateFrontier upravuje hraniční slovník, ve kterém se mění stav hrany z bodu a do bodu b:

Rýže. 5

Void updateFrontier (Dictionary &hranice, bod &a, bod &b) ( Hrana *e = nová hrana (a, b); if (hranice.find (e)) hranice.remove(e); jinak ( e->flip(); hranice.vložte( e);))

Funkce hullEdge najde hranu trupu mezi n body v poli s. Tato funkce ve skutečnosti používá inicializační krok a první iteraci metody balení dárků:

Edge *hullEdge (Bod s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

Funkce trojúhelník jednoduše vygeneruje a vrátí polygon pro tři body, které jí byly předány jako parametry:

Mnohoúhelník *trojúhelník (Bod &a, Bod &b, Bod &c) ( Mnohoúhelník *t = nový mnohoúhelník; t->vložit (a); t->vložit (b); t->vložit (c); vrátit t; )

GRID modely jsou modely pravidelných buněk.

Nechť je zaveden souřadnicový systém
A A
. Uživatelské sady
a kroky vzorkování
.

,

- fyzické souřadnice bodu.

Počítáme
A
,
- bitová mřížka.

- kvantované hodnoty. Nemovitý:

- parametr algoritmu – počet bodů, - hmotnost. Čím blíže je bod, tím větší je váha.

- stupeň vzdálenosti (1 nebo 2).

Normalizační faktor:

Jak blíže k 1, tím více bodů s vyšší váhou se bere v úvahu.

Toto je metoda IDW - dlouhá, pro každé t je nutné najít sousedy. Množinu sousedů lze efektivně najít - nejbližší. Každý bod vytváří „kolíček“ určité výšky. Hodně záleží na nepravidelnosti nastavení bodu, na to berou
nebo
těch. rozděleny do sektorů a stavět body v okolí.

Výhoda– jednoduchost

Chyba:

------Vstupenka 14. Plechový model. Delaunayovy triangulační algoritmy ------

1) Triangulace (cín).

Triangulace– konstrukce funkce ve formě množiny po částech lineárních funkcí

Triangulace– interpolace v rámci konvexní oblasti.

Triangulace– rovinný graf, jehož všechny vnitřní hrany jsou trojúhelníky; způsob znázornění prostoru ve formě trojúhelníků vedle sebe bez překrývání. Triangulace je postavena na množině bodů několika způsoby.

K vytvoření optimální triangulace je potřeba algoritmus.

Rovina procházející 3 body.

1) Najděte trojúhelník, který
;

2)
- sestrojte rovnici roviny.

Chcete-li zkontrolovat, zda jsou body uvnitř trojúhelníku nebo ne, musíte hodnotu dosadit do rovnice přímek - hran trojúhelníku. Pokud všechny 3 rovnice > 0, pak uvnitř.

Struktura prezentace:

Každá triangulace obsahuje stejný počet trojúhelníků.

, Kde - počet vnitřních bodů,
- počet bodů.

Chamtivá triangulace.

Všechny body spojíme hranami, vybereme minimum a přidáme je do triangulace. Dále vezmeme další minimum, které se nekříží s předchozími atd. Výsledkem je chamtivá triangulace.

Delaunayova triangulace.

Vnitřek kružnice opsané žádnému trojúhelníku nezahrnuje body jiných trojúhelníků. Je postavena jediným způsobem.

Flip je přenos hran. Umožňuje vám přejít od konvenční triangulace k Delaunayově triangulaci. Chcete-li zkontrolovat, zda bod patří do kruhu: dosaďte pokud< R, то внутри.

Delaunayův stav.

Rovnice kružnice procházející třemi body:

Pokud je menší než nula, pak externí, jinak - interní.

– Delaunayův stav.

Algoritmus pro konstrukci Delaunayovy triangulace:

1) Přidávání teček v šetření– jednoduchý iterační algoritmus:

Je tam sada
přidejte k trojúhelníku, konstrukce se provádí
dělení trojúhelníku
přestavba. V nulté fázi přidáme 3-4 fiktivní body, které samozřejmě pokrývají naši obálku, všechny body uvnitř. Poté bod hodíme, podíváme se na jaký trojúhelník narazí, rozdělíme na 3, u každého trojúhelníku zkontrolujeme Delaunayovu podmínku a provedeme překlopení hran. Průměrný počet změn jízdních pruhů jsou tři.

Teoretická složitost

2) Akcelerační metody. Na základě statisticky závislých bodů. Zárodečný trojúhelník je trojúhelník, do kterého spadl předchozí bod. Poté spojíme dva body – předchozí a nový.

Postupujeme od prvního bodu k dalšímu.