20. srpna 2012 ve 22:41 hodin

Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice a její aplikace

Řeknu vám tajemství, jak rychle zkontrolovat Delaunayovu podmínku pro dva trojúhelníky.
Ve skutečnosti je samotná optimalizace popsána trochu níže (viz „Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice“), ale o všem vám řeknu v pořádku.

V mém případě se triangulace používá při sledování obrazu k rozdělení roviny na primitivní sektory (trojúhelníky). Jak víte, je také rozdělena do několika fází: úprava, identifikace hranic, obcházení hranic, zametání kontur. Je to ve velmi obecný pohled. Opravdu bych rád přestal, myslím obtížná etapa: zametání letadla.

U vchodu

Po detekci a překročení hranic jsem na výstupu dostal spoustu vnějších smyček. Každá dotyková kontura má rozdílné barvy. Každý takový obvod také obsahuje známý počet vnitřních obvodů.
Pokud tedy z hlediska „zametání roviny“ uvažujeme odděleně vnější obrysy, máme množinu bodů, z nichž každý má jednoho souseda vpravo a vlevo. Tito. všechny body jsou uzavřeny v řetězci, neexistuje jediný „visící“ bod a každý řetězec obsahuje alespoň 3 body (obrázek 1).

Obrázek 1

Co je potřeba udělat

Musíte zakrýt postavu trojúhelníky.

Vyhledávání

Po přečtení knihy jsem nenašel jedinou (alespoň jednu) metodu konstrukce Delaunayovy triangulace, která by byla pro můj případ alespoň trochu vhodná. Jiné knihy jsem nehledala. A tohle stačilo, uspořádalo mi to myšlenky v hlavě. V důsledku toho vynalezl vlastní „kolo“.

Algoritmus

1) Pro začátek předpokládejme, že na uvažovaném obrázku je pouze jedna sekvence. Pak to všechno přijde na postupné přijímání trojúhelníků. Vezmeme libovolný bod a pokusíme se sestrojit trojúhelník se sousedními body. Pokud nebylo možné sestrojit trojúhelník (čára spojující tyto dva body se protíná s těmi již postavenými nebo čára prochází ve vyloučené zóně (obrázek 2), přesuneme se k dalšímu bodu, řekněme doprava. Když další trojúhelník je nalezen, přidáme jej do seznamu (obrázek 3) a odstraníme bod, ze kterého byl vytvořen (obrázek 4).

Obrázek 2

Obrázek 3

Obrázek 4

Ještě něco: při ukládání dalšího trojúhelníku je nutné zaznamenat vrcholy ve směru hodinových ručiček (v pravém souřadném systému). To bude užitečné v budoucnu ke snížení výpočetních zdrojů.

2) Opakujte krok 1, dokud nezametáme celou rovinu.

3) Pokud existuje více sekvencí, tzn. jeden a uvnitř něj je jeden nebo více vnitřních obrysů (obrázek 1). Zde je nutné zvážit každou sekvenci zvlášť. Vezměme další vnitřní obrys. Z jednoho vnějšího a jednoho vnitřního vytvoříme dva samostatné okruhy. Chcete-li to provést, musíte najít dva „porty“ z jednoho okruhu do druhého. Podmínka pro „porty“: neměly by se vzájemně protínat (ani jejich konce by se neměly dotýkat) a neměly by se protínat s vrstevnicemi (obrázek 5).

Obrázek 5

Obrázek 6
4) Dále byste měli postupně zadávat všechny vnitřní sekvence do již vytvořených sekvencí, oddělených od sebe (bod 3). Musíte jej sloučit s tím, který obsahuje nový. Podle definice se žádná vnitřní sekvence nedotýká a neprotíná s ostatními (jak jednou vnější, tak všemi možnými vnitřními), takže vše půjde hladce.
Po nalezení portů (obrázek 6) je snadné vytvořit nové sekvence a obejít je pomocí bodů 1 a 2 aktuálního algoritmu (obrázek 7).

Obrázek 7

5) Po 4. fázi máme seznam trojúhelníků (obrázek 8). Jako by byl úkol již dokončen, ale zbývá jen udělat obrázek krásný: zkontrolujte, zda je splněna Delaunayova podmínka (obrázek 9).

Postavení 8

Obrázek 9

6) Při pohledu do budoucna vám řeknu o šestém bodě. Spočívá v postupném procházení seznamu získaných trojúhelníků pomocí kroku č. 5. Nejprve označíme všechny trojúhelníky jako „špinavé“. V každém cyklu kontrolujeme Delaunayovu podmínku pro každý trojúhelník. Pokud podmínka není splněna, přestavíme a označíme sousedy a aktuální trojúhelník jako „špinavé“. Pokud je podmínka splněna, pak označíme za čisté. V mé implementaci algoritmu má každý trojúhelník vazbu na své sousedy. V tomto případě funguje bod 6 nejrychleji.

Více o páté etapě

Nyní, pokud vím, jsou dva možné způsoby určete, zda trojúhelníky splňují Delaunayovu podmínku či nikoli: 1) Zkontrolujte součet opačných úhlů. Musí být menší než 180. 2) Vypočítejte střed opsané kružnice a vypočítejte vzdálenost ke 4. bodu. Každý ví, že Delaunayova podmínka je splněna, pokud je bod mimo opsané kružnice.

Výpočetní výkon #1: 10 násobení/dělení a 13 sčítání/odčítání.
Výpočetní výkon #2: 29 operací násobení/dělení a 24 operací sčítání/odčítání.

Z hlediska výpočetního výkonu, který je vypočítán např. v knize, je výhodnější varianta č. 1. Implementoval bych to, pokud ne... (Obrázek 10). Jak se ukázalo po výrobě tato metoda na „dopravní pás“, výsledkem byla nejistota. Toto je možnost, když úhel A samotný je větší než 180 stupňů. V knize je považována za jednu z individuálních soukromých metod. A tím zmizí veškerá jeho elegance, transparentnost a výkon. A také se později ukázalo, že metodu č. 2 lze velmi výrazně optimalizovat.

Obrázek 10

Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice

Následuje čistá matematika.

Takže máme:
Kontrolu podmínky pro bod M(X, Y) rovnicí kružnice procházející body A(x1, y1), B(x2, y2), C(x3, y3) lze zapsat jako:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ znaménko a ≥ 0

Podrobnosti najdete ve skvělé knize. (Ne, nejsem autorem)
Takže znaménko a je směrové znaménko, od samého začátku jsem trojúhelníky stavěl ve směru hodinových ručiček, takže ho lze vynechat (rovná se jedné).

A(x1 - X, yl - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Obrázek 11

Jednoduché, že?

Podle knihy opět

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 – x1*y2)<= 0

Máme: 15 operací násobení/dělení a 14 operací sčítání/odčítání.

Děkuji za pozornost. Čekám na kritiku.

Bibliografie

1. Skvortsov A.V. Delaunayova triangulace a její aplikace. – Tomsk: Nakladatelství Tom. Univerzita, 2002. – 128 s. ISBN 5-7511-1501-5

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í koeficient:

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.

20. srpna 2012 ve 22:41 hodin

Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice a její aplikace

• Zpracování obrazu ,
• Programování

Řeknu vám tajemství, jak rychle zkontrolovat Delaunayovu podmínku pro dva trojúhelníky.
Ve skutečnosti je samotná optimalizace popsána trochu níže (viz „Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice“), ale o všem vám řeknu v pořádku.

V mém případě se triangulace používá při sledování obrazu k rozdělení roviny na primitivní sektory (trojúhelníky). Jak víte, je také rozdělena do několika fází: úprava, identifikace hranic, obcházení hranic, zametání kontur. To je v nejobecnějších termínech. Rád bych se zastavil, myslím, v nejtěžší fázi: zametání letadla.

U vchodu

Po detekci a překročení hranic jsem na výstupu dostal spoustu vnějších smyček. Každý dojemný obrys má jinou barvu. Každý takový obvod také obsahuje známý počet vnitřních obvodů.
Pokud tedy z hlediska „zametání roviny“ uvažujeme odděleně vnější obrysy, máme množinu bodů, z nichž každý má jednoho souseda vpravo a vlevo. Tito. všechny body jsou uzavřeny v řetězci, neexistuje jediný „visící“ bod a každý řetězec obsahuje alespoň 3 body (obrázek 1).

Obrázek 1

Co je potřeba udělat

Musíte zakrýt postavu trojúhelníky.

Vyhledávání

Po přečtení knihy jsem nenašel jedinou (alespoň jednu) metodu konstrukce Delaunayovy triangulace, která by byla pro můj případ alespoň trochu vhodná. Jiné knihy jsem nehledala. A tohle stačilo, uspořádalo mi to myšlenky v hlavě. V důsledku toho vynalezl vlastní „kolo“.

Algoritmus

1) Pro začátek předpokládejme, že na uvažovaném obrázku je pouze jedna sekvence. Pak to všechno přijde na postupné přijímání trojúhelníků. Vezmeme libovolný bod a pokusíme se sestrojit trojúhelník se sousedními body. Pokud nebylo možné sestrojit trojúhelník (čára spojující tyto dva body se protíná s těmi již postavenými nebo čára prochází ve vyloučené zóně (obrázek 2), přesuneme se k dalšímu bodu, řekněme doprava. Když další trojúhelník je nalezen, přidáme jej do seznamu (obrázek 3) a odstraníme bod, ze kterého byl vytvořen (obrázek 4).

Obrázek 2

Obrázek 3

Obrázek 4

Ještě něco: při ukládání dalšího trojúhelníku je nutné zaznamenat vrcholy ve směru hodinových ručiček (v pravém souřadném systému). To bude užitečné v budoucnu ke snížení výpočetních zdrojů.

2) Opakujte krok 1, dokud nezametáme celou rovinu.

3) Pokud existuje více sekvencí, tzn. jeden a uvnitř něj je jeden nebo více vnitřních obrysů (obrázek 1). Zde je nutné zvážit každou sekvenci zvlášť. Vezměme další vnitřní obrys. Z jednoho vnějšího a jednoho vnitřního vytvoříme dva samostatné okruhy. Chcete-li to provést, musíte najít dva „porty“ z jednoho okruhu do druhého. Podmínka pro „porty“: neměly by se vzájemně protínat (ani jejich konce by se neměly dotýkat) a neměly by se protínat s vrstevnicemi (obrázek 5).

Obrázek 5

Obrázek 6
4) Dále byste měli postupně zadávat všechny vnitřní sekvence do již vytvořených sekvencí, oddělených od sebe (bod 3). Musíte jej sloučit s tím, který obsahuje nový. Podle definice se žádná vnitřní sekvence nedotýká a neprotíná s ostatními (jak jednou vnější, tak všemi možnými vnitřními), takže vše půjde hladce.
Po nalezení portů (obrázek 6) je snadné vytvořit nové sekvence a obejít je pomocí bodů 1 a 2 aktuálního algoritmu (obrázek 7).

Obrázek 7

5) Po 4. fázi máme seznam trojúhelníků (obrázek 8). Jako by byl úkol již dokončen, ale zbývá jen udělat obrázek krásný: zkontrolujte, zda je splněna Delaunayova podmínka (obrázek 9).

Postavení 8

Obrázek 9

6) Při pohledu do budoucna vám řeknu o šestém bodě. Spočívá v postupném procházení seznamu získaných trojúhelníků pomocí kroku č. 5. Nejprve označíme všechny trojúhelníky jako „špinavé“. V každém cyklu kontrolujeme Delaunayovu podmínku pro každý trojúhelník. Pokud podmínka není splněna, přestavíme a označíme sousedy a aktuální trojúhelník jako „špinavé“. Pokud je podmínka splněna, pak označíme za čisté. V mé implementaci algoritmu má každý trojúhelník vazbu na své sousedy. V tomto případě funguje bod 6 nejrychleji.

Více o páté etapě

Nyní, pokud vím, existují dva možné způsoby, jak určit, zda trojúhelníky splňují Delaunayovu podmínku nebo ne: 1) Zkontrolujte součet opačných úhlů. Musí být menší než 180. 2) Vypočítejte střed opsané kružnice a vypočítejte vzdálenost ke 4. bodu. Každý ví, že Delaunayova podmínka je splněna, pokud je bod mimo opsané kružnice.

Výpočetní výkon #1: 10 násobení/dělení a 13 sčítání/odčítání.
Výpočetní výkon #2: 29 operací násobení/dělení a 24 operací sčítání/odčítání.

Z hlediska výpočetního výkonu, který je vypočítán např. v knize, je výhodnější varianta č. 1. Implementoval bych to, pokud ne... (Obrázek 10). Jak se ukázalo, po nasazení této metody na „dopravník“ nastala nejistota. Toto je možnost, když úhel A samotný je větší než 180 stupňů. V knize je považována za jednu z individuálních soukromých metod. A tím zmizí veškerá jeho elegance, transparentnost a výkon. A také se později ukázalo, že metodu č. 2 lze velmi výrazně optimalizovat.

Obrázek 10

Optimalizace algoritmu pro kontrolu Delaunayovy podmínky pomocí rovnice opsané kružnice

Následuje čistá matematika.

Takže máme:
Kontrolu podmínky pro bod M(X, Y) rovnicí kružnice procházející body A(x1, y1), B(x2, y2), C(x3, y3) lze zapsat jako:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ znaménko a ≥ 0

Podrobnosti najdete ve skvělé knize. (Ne, nejsem autorem)
Takže znaménko a je směrové znaménko, od samého začátku jsem trojúhelníky stavěl ve směru hodinových ručiček, takže ho lze vynechat (rovná se jedné).

A(x1 - X, yl - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Obrázek 11

Jednoduché, že?

Podle knihy opět

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 – x1*y2)<= 0

Máme: 15 operací násobení/dělení a 14 operací sčítání/odčítání.

Děkuji za pozornost. Čekám na kritiku.

Bibliografie

1. Skvortsov A.V. Delaunayova triangulace a její aplikace. – Tomsk: Nakladatelství Tom. Univerzita, 2002. – 128 s. ISBN 5-7511-1501-5

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ů je problém spojování daných bodů disjunktními segmenty tak, aby vznikla 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á.

Položme tedy prázdnou Delaunayovu kouli do systému bodů (A). 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. K tomu budete muset posunout 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, které určují 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 v obecném případě jeden takový vrchol může 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. Nechť je nalezen nejbližší vrchol V pro hraniční hranu AB Potom 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 definování parametrů Rozdělme oblast pro definování parametrů povrchu na pravoúhlé buňky s dvourozměrnými čarami. 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 obdélníkovou 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ů. Každý úsek mnohoúhelníku lze považovat za dvourozměrný přímkový segment 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. Dostáváme 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í určitou 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 postavíme trojúhelníky a zužujeme 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 tom 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 brát průsečík elipsy a úhlopříčky rovnoběžníku jako 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 vymažeme bod O v pracovní oblasti 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ý polygon neprotíná. 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ího mnohoúhelníku vložíme body vnitřního mnohoúhelníku počínaje bodem F a konče bodem E. Pracovní mnohoúhelník tedy přerušíme na segmentu OS, rozbijte vnitřní polygon na segmentu EF a spojte je se segmenty OF a EU.

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

Rýže. 9.7.15. Sloučení 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ýsledkem je, že celá vícenásobně spojená doména pro určování parametrů povrchu bude 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. 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).