Триангулацията за краен набор от точки S е проблемът за триангулиране на изпъкналата обвивка CH(S), обхващаща всички точки от множеството S. Отсечките не могат да се пресичат по време на триангулацията - те могат да се срещат само в общи точки, принадлежащи на множеството S. Тъй като правата линейните сегменти затварят триъгълници, ще ги считаме за ръбове. На фиг. 1 показва два различни варианта на триангулация за един и същ набор от точки (временно ще пренебрегнем кръговете, начертани на тези фигури).

Ориз. един

Дадено е множество от точки S, можем да видим, че всички точки от множеството S могат да бъдат подразделени на гранични точки - тези точки, които лежат на границата на изпъкналата обвивка CH(S), и вътрешни точки - тези, които лежат вътре в изпъкналата корпус CH(S). Също така е възможно да се класифицират ръбовете, получени в резултат на триангулацията на S като ръбове на черупкатаи вътрешни ребра. Краищата на обвивката включват ръбовете, разположени по протежение на границата на изпъкналата обвивка CH(S), а вътрешните ръбове включват всички други ръбове, които образуват мрежа от триъгълници вътре в изпъкналата обвивка. Имайте предвид, че всеки ръб на обвивката свързва две съседни гранични точки, докато вътрешните ръбове могат да свързват две точки от всякакъв тип. По-специално, ако вътрешен ръб свързва две гранични точки, тогава той е хорда на изпъкналата обвивка CH(S). Обърнете внимание също, че всеки триангулационен ръб е границата на две области: всеки вътрешен ръб е между два триъгълника, а всеки ръб на обвивката е между триъгълник и безкрайна равнина.

Всеки набор от точки, освен в някои тривиални случаи, позволява повече от един начин за триангулиране. Но в същото време има едно забележително свойство: всеки начин на триангулация за дадено множество определя същия брой триъгълници, което следва от теоремата:

Теорема за триангулация на множество точки.Да приемем, че множеството от точки S съдържа n>3 точки и не всички от тях са колинеарни. Освен това i точки от тях са вътрешни (т.е. лежащи вътре в изпъкналата обвивка CH(S). Тогава при произволен метод на триангулация на множеството S ще се получат точно n + i - 2 триъгълника.

За да докажем теоремата, първо разглеждаме триангулацията на n-i гранични точки. Тъй като всички те са върхове на изпъкнал многоъгълник, такава триангулация ще доведе до (n - i) - 2 триъгълника. (Това не е трудно да се провери и освен това може да се покаже, че всяка триангулация произволен m-странен многоъгълник - изпъкнал или неизпъкнал - съдържа m - 2 триъгълника). Сега нека проверим какво ще се случи с триангулацията при добавяне на останалите i вътрешни точки, по една всеки път. Твърдим, че добавянето на всяка такава точка води до увеличаване на броя на триъгълниците с две. При добавяне на вътрешна точка могат да възникнат две ситуации, както е показано на фиг. 2. Първо, точката може да е вътре в някакъв триъгълник и след това такъв триъгълник се заменя с три нови триъгълника. Второ, ако точката съвпада с един от ръбовете на триангулацията, тогава всеки от двата триъгълника, съседни на този ръб, се заменя с два нови триъгълника. От това следва, че след добавяне на всички r точки, общият брой на триъгълниците ще бъде (n - i - 2) + (2i) или просто n + i - 2.

Ориз. 2

В този раздел представяме алгоритъм за генериране на специален вид триангулация, известна като триангулация на Делоне. Тази триангулация е добре балансирана в смисъл, че образуваните триъгълници са склонни да бъдат равноъгълни. Например, триангулацията, показана на фиг. 1а може да се припише на типа триангулация на Делоне, а на фиг. Триангулацията на Фиг. 1b съдържа няколко силно издължени триъгълника и не може да бъде отнесена към типа Delaunay. На фиг. 3 показва пример за триангулация на Делоне за набор от голям брой точки.

Ориз. 3

За да формираме триангулацията на Делоне, имаме нужда от няколко нови определения. Набор от точки се счита за кръгъл, ако има някаква окръжност, върху която лежат всички точки от набора. Такава окръжност ще бъде описана за даден набор от точки. Описаната окръжност за триъгълник минава през трите му (неколинеарни) върха. Казва се, че една окръжност е свободна от точки по отношение на дадено множество от точки S, ако вътре в окръжността няма точки от множеството S. Но точките от множеството S могат да бъдат разположени върху най-свободната от точки окръжност.

Триангулация на набор от точки S ще бъде триангулация на Делоне, ако описаната окръжност за всеки триъгълник е свободна от точки. В триангулационната диаграма на фиг. 1а показва два кръга, които очевидно не съдържат други точки вътре (можете да нарисувате кръгове за други триъгълници, за да сте сигурни, че те също са свободни от точки в набора). Това правило не се спазва в диаграмата на фиг. 16 - една точка от друг триъгълник е попаднала в начертаната окръжност, следователно тази граангулация не принадлежи към типа Делоне.

Могат да се направят две допускания относно точките в множеството S, за да се опрости алгоритъмът за триангулация. Първо, за да съществува изобщо триангулация, трябва да приемем, че множеството S съдържа поне три точки и те не са колинеарни. Второ, за да бъде триангулацията на Делоне уникална, е необходимо нито една четири точка от множеството S да не лежи на една и съща описана окръжност. Лесно е да се види, че без такова предположение триангулацията на Делоне няма да бъде уникална, защото 4 точки върху една описана окръжност ни позволяват да реализираме две различни триангулации на Делоне.

Нашият алгоритъм работи чрез постоянно изграждане на текущата триангулация един триъгълник наведнъж. Първоначално текущата триангулация се състои от един ръб на обвивката, след завършване на алгоритъма текущата триангулация става триангулация на Делоне. При всяка итерация алгоритъмът търси нов триъгълник, който се свързва с границатекуща триангулация.

Дефиницията на границата зависи от следната схема за класификация на ръба на триангулацията на Делоне спрямо текущата триангулация. Всеки ръб може да бъде спящ, живили мъртъв:

• спящи ребра: ребро на триангулация на Делоне е латентно, ако все още не е открито от алгоритъма;
• живи ребра: ръбът е жив, ако бъде намерен, но е известен само един регион, съседен на него;
• мъртви ребра: ръбът се счита за мъртъв, ако е намерен и двата съседни региона са известни.

Първоначално единственото ребро, което принадлежи на изпъкналата i точка, е живо - неограничена равнина граничи с него, а всички останали ребра са латентни. Докато алгоритъмът работи, спящите ръбове стават живи, след това мъртви. Границата на всеки етап се състои от набор от живи ръбове.

При всяка итерация всеки един от ръбовете на границата се избира и се подлага на обработка, която се състои в намиране на неизвестна област, към която принадлежи ръбът е. Ако тази област се окаже триъгълник f, определен от крайните точки на ръбът e и някакъв трети връх v, тогава ръбът e става мъртъв, тъй като и двете съседни области вече са известни. Всеки от другите два ръба на триъгълника t се прехвърля в следното състояние: от спящ в жив или от жив в мъртъв. Тук ще бъде извикан връх v конюгатс ръба e. В противен случай, ако неизвестната област се окаже безкрайна равнина, тогава ръбът e просто умира. В този случай ръбът e няма спрегнат връх.

На фиг. 4 показва работата на алгоритъма, където действието се извършва отгоре надолу и отгоре надясно. Границата на всеки етап е маркирана с дебела линия.

Алгоритъмът е реализиран в програмата delaunayTriangulate. Програмата получава масив s от n точки и връща списък от триъгълници, представляващи триангулацията на Делоне. Внедряването използва класа на пръстенния списък и класовете от раздела Геометрични структури на данни. Всеки речник, който поддържа необходимите операции, може да се използва като клас Речник. Например, можете да замените #define Dictionary RandomizedSearchTree.

списък * (Точка s, int n) (Точка p; Списък *триъгълници = нов списък ; Речник граница (edgeCmp); Edge *e = hullEdge(s, n); гранична вложка(e); докато (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(frontier, e ->dest, p); triangles->insert(triangle(e->org, e->dest, p)); ) delete e; ) return triangles; )

Ориз. четири

Триъгълниците, които образуват триангулацията, се записват в списъка с триъгълници. Границата е представена от речник на граничните живи ръбове. Всеки ръб е насочен така, че неговата неизвестна област (която предстои да бъде определена) лежи вдясно от ръба. Функцията за сравнение edgeCmp се използва за търсене на речник. Той сравнява началните точки на два ръба, ако те са равни, тогава техните крайни точки се сравняват:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) върне 1; if (a->org > b->org) върне 1; ако (a->dest< b->dest) връщане -1; if (a->dest > b->dest) върне 1; връщане 0; )

И така, как границата се променя от една стъпка на друга и как функцията updateFrontier променя речника на границата, за да отрази тези промени? Когато нов триъгълник t е прикрепен към границата, състоянията на трите ръба на триъгълника се променят. Ръбът на триъгълника t, съседен на границата, става мъртъв от жив. Функцията updateFrontier може да игнорира този край, тъй като той вече трябва да е премахнат от речника, когато се извика функцията removeMin. Всеки от двата останали ръба на триъгълника променя състоянието си от спящ на жив, ако преди това не е бил записан в речника, или от жив на мъртъв, ако ръбът вече е в речника. На фиг. 5 показва и двата случая. В съответствие с фигурата обработваме живия ръб af и след като установим, че точката b е спрегната на него, добавяме триъгълника afb към текущата триангулация. След това търсим edge fb в речника и тъй като все още го няма и се открива за първи път, състоянието му се променя от спящо на живо. За да редактирате речника, ще завъртим ръба fb, така че неизвестният регион, съседен на него, да лежи вдясно от него и ще запишем този ръб в речника. Тогава ще намерим ръба ba в речника - тъй като е в него, той вече е жив (известната област, съседна на него, е триъгълникът abc). Тъй като непознатата за него област, триъгълникът afb, току-що беше открита, този ръб е премахнат от речника.

Функцията updateFrontier редактира граничния речник, в който състоянието на ръба се променя от точка a до точка b:

Ориз. 5

Void updateFrontier(Речник &frontier, Point &a, Point &b) ( Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( д);))

Функцията hullEdge намира край на корпуса сред n точки на масива s. Тази функция всъщност използва стъпката за инициализация и първата итерация на метода за опаковане на подаръци:

Edge *hullEdge (Точка 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]); }

Функцията триъгълник просто формира и връща многоъгълник за трите точки, предадени като параметри към нея:

Многоъгълник *триъгълник (Точка &a, Точка &b, Точка &c) ( Многоъгълник *t = нов многоъгълник; t->вмъкване (a); t->вмъкване (b); t->вмъкване (c); връщане t; )

GRID моделите са модели на правилни клетки.

Нека координатната система
и и
. Потребителски набори
и стъпки за вземане на проби
.

,

- физически координати на точката.

Изчисли
и
,
- битова решетка.

- квантувани стойности. Реално:

- параметър на алгоритъма - брой точки, - теглото. Колкото по-близо е точката, толкова по-голямо е теглото.

- степен на разстояние (1 или 2).

Коефициент на нормализиране:

как по-близо до 1, толкова повече претеглени точки се вземат предвид.

Това е методът IDW - дълъг, за всяко t е необходимо да се намерят съседи. Набор от съседи може да бъде ефективно намерен - най-близкият. Всяка от точките произвежда "колче" с определена височина. Много зависи от нередовността на определяне на точката, за това те вземат
или
тези. разделете на сектори и изградете в близост до точката.

Предимство– простота

недостатък:

------Билет 14. Тенекиен модел. Алгоритми за триангулация на Делоне ------

1) Триангулация (калай).

Триангулация– конструиране на функция под формата на набор от късолинейни функции

Триангулация– интерполация вътре в изпъкналата област.

Триангулацияе равнинен граф, чиито вътрешни ръбове са триъгълници; начин за представяне на пространството под формата на триъгълници, съседни един на друг без припокриване. Триангулацията се изгражда върху набор от точки по няколко начина.

Имаме нужда от алгоритъм за изграждане на оптимална триангулация.

Равнина, преминаваща през 3 точки.

1) Намерете триъгълник, който
;

2)
- изграждаме уравнението на равнината.

За да проверите дали точките са вътре в триъгълника или не, трябва да замените стойността в уравнението на линиите - краищата на триъгълника. Ако всичките 3 уравнения > 0, тогава вътре.

Вижте структурата:

Всяка триангулация съдържа еднакъв брой триъгълници.

, където е броят на вътрешните точки,
- брой точки.

Алчна триангулация.

Свързваме всички точки с ръбове, избираме минимума, добавяме към триангулацията. След това вземаме следващия минимум, който не се пресича с предишните и т.н. Резултатът е алчна триангулация.

Триангулация на Делоне.

Точките на други триъгълници не попадат в окръжност, описана около всеки триъгълник. Построен по един начин.

Обръщането е обръщане на ръбове. Тя ви позволява да превключите от конвенционална триангулация към триангулация на Делоне. За да проверите дали дадена точка принадлежи на окръжност: заместете if< R, то внутри.

Условие на Делоне.

Уравнение на окръжност, минаваща през три точки:

Ако е по-малко от нула, тогава външно, в противен случай - вътрешно.

е условието на Делоне.

Алгоритъмът за конструиране на триангулацията на Delaunay:

1) В процес на разследване добавяне на точкие прост итеративен алгоритъм:

Има комплект
добавете към триъгълника, конструкцията се извършва
преграда на триъгълник
възстановяване. На нулевия етап добавяме 3-4 фиктивни точки, които очевидно покриват нашия плик, всички точки са вътре. След като хвърлим точка, вижте кой триъгълник е ударил, разделяме го на 3, за всеки триъгълник проверяваме условието на Delaunay и обръщаме ръбовете. Средният брой реконструкции е три.

Теоретична сложност

2) Методи за ускоряване.Въз основа на статистически зависими точки. Стартовият триъгълник е триъгълникът, в който е паднала предишната точка. След това свързваме две точки - предишната и новата.

Преминаваме от първата точка към другата.

Основни определения и свойства

Триангулацията е равнинна графика, чиито вътрешни области са триъгълници.

Имоти:

· Триангулацията на Делоне съответства едно към едно на диаграмата на Вороной за същия набор от точки.

· Като следствие: ако няма четири точки, които лежат на една и съща окръжност, триангулацията на Делоне е уникална.

· Триангулацията на Delaunay максимизира минималния ъгъл сред всички ъгли на всички конструирани триъгълници, като по този начин избягва "тънките" триъгълници.

· Триангулацията на Делоне максимизира сумата от радиусите на вписаните топки.

· Триангулацията на Делоне минимизира дискретния функционал на Дирихле.

· Триангулацията на Delaunay минимизира максималния радиус на минималната обхващаща сфера.

· Триангулацията на Делоне в равнина има минималната сума от радиуси на окръжности, описани около триъгълници сред всички възможни триангулации.

Фигура 1. Триангулация.

Изпъкнала триангулация е такава триангулация, при която минималният многоъгълник, обхващащ всички триъгълници, е изпъкнал. Триангулация, която не е изпъкнала, се нарича неизпъкнала.

Задачата за конструиране на триангулация от даден набор от двумерни точки е проблемът за свързване на дадени точки с непресичащи се сегменти, така че да се образува триангулация.

Твърди се, че една триангулация удовлетворява условието на Делоне, ако нито една от дадените точки на триангулация не попада в окръжността, описана около който и да е конструиран триъгълник.

Триангулацията се нарича триангулация на Делоне, ако е изпъкнала и удовлетворява условието на Делоне.

Фигура 2. Триангулация на Делоне.

Метод на празната топка на Делоне. Конструкция в общия случай

Нека използваме празна топка, която ще преместим, променяйки размера й, така че да може да докосне точките на системата (А), но винаги да остава празна.

И така, нека поставим празна топка на Делоне в системата от точки (А). Това винаги е възможно, ако топката е избрана достатъчно малка. Нека започнем да увеличаваме радиуса му, оставяйки центъра на топката на място. В даден момент повърхността на топката ще срещне някаква точка i от системата (A). Това определено ще се случи, защото в нашата система няма безкрайно големи празнини. Ще продължим да увеличаваме радиуса на празната топка, така че точка i да остане на нейната повърхност. За да направите това, ще трябва да преместите центъра на топката от точка i. Рано или късно топката ще достигне с повърхността си друга точка от системата (А).

Фиг.3

Delaunay simples запълват пространството без празнини и припокривания.

Описаната сфера на всеки симплекс не съдържа други точки от системата вътре.

Нека това е точка j. Нека продължим да увеличаваме радиуса на нашата топка, като запазим двете точки на нейната повърхност. Увеличавайки се, топката ще достигне някаква трета точка от системата, точка k. В двумерния случай нашият "празен кръг" ще бъде фиксиран в този момент, т.е. става невъзможно по-нататъшното увеличаване на радиуса му, докато кръгът остава празен. В същото време разкриваме елементарна двумерна конфигурация от три точки (i, j, k), която определя определен триъгълник, чиято особеност е, че няма други точки от системата (A) вътре в описаната му кръг. В три измерения една топка не се определя от три точки. Нека продължим да увеличаваме радиуса му, като запазим и трите намерени точки на повърхността му. Това ще бъде възможно, докато повърхността на топката не срещне четвъртата точка l от системата. След това движението и растежът на празна топка ще стане невъзможно. Намерените четири точки (i, j, k, l) определят върховете на тетраедъра, който се характеризира с това, че няма други точки от системата (A) вътре в описаната му сфера. Такъв тетраедър се нарича симплекс на Делоне.

Симплекс в математиката се нарича най-простата фигура в пространство с дадено измерение: тетраедър - в тримерно пространство; триъгълник - в две измерения. Произволна тройка (четворка) системни точки, които не лежат в една и съща равнина, винаги определя определен симплекс. Въпреки това, той е само симплекс на Делоне, ако описаната му сфера е празна. С други думи, симплексите на Делоне се определят от специален избор на тройки (четворки) точки в система (A).

Построихме един симплекс на Делоне, но чрез поставяне на празната топка на различни места и повтаряне на същата процедура могат да бъдат дефинирани други. Твърди се, че множеството от всички симплекси на Делоне на система (A) запълва пространството без припокривания и пропуски, т.е. прилага разделяне на пространството, но този път на тетраедри. Това разделяне се нарича Делоне дял(фиг. 3).

Приложение на триангулацията на Делоне

Често триангулациите на Делоне се прилагат в евклидовото пространство. Гарантирано е, че минималното евклидово обхващащо дърво е на триангулация на Delaunay, така че някои алгоритми използват триангулация. Освен това, чрез триангулацията на Делоне, евклидовият проблем на пътуващия търговец е приблизително решен.

При 2D интерполация, триангулацията на Делоне разделя равнината на възможно най-дебелите триъгълници, като избягва твърде остри или твърде тъпи ъгли. Тези триъгълници могат да се използват за изграждане, например, на билинейна интерполация.

Друг проблем, който често възниква в геоинформатиката, е изграждането на експозиции на склонове. Тук е необходимо да се определят доминиращите посоки на склоновете по кардинални точки и да се раздели повърхността на области, в които доминира определена посока. Тъй като определението за експозиция няма смисъл за хоризонтални участъци от повърхността, областите, които са хоризонтални или имат лек наклон, например, се разпределят в отделен регион.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Фиг.4.

Задачата за изчисляване на експозициите на склона обикновено се използва за анализ на осветеността на Земята. В тази връзка често има нужда допълнително да се вземе предвид текущото положение на Слънцето, т.е. експозицията се изчислява като посоката между нормалата към триъгълника и посоката на слънцето.

По този начин всеки триангулационен триъгълник може да бъде класифициран според принципа на принадлежност към определен регион. След това просто трябва да извикате алгоритъма за избор на регион.

Пространствена триангулация на Делоне

Проблемът за изграждане на мрежа от триъгълници без припокриване е един от основните в изчислителната геометрия и се използва широко в компютърната графика и геоинформационните системи за повърхностно моделиране и решаване на пространствени задачи.

За първи път проблемът за изграждане на мрежа от неприпокриващи се триъгълници е поставен през 1934 г. в работата на съветския математик Б. Н. Делоне, който формулира и съответните условия.

В математиката задачата за изграждане на триангулация по дадени точки се нарича задачата за тяхното свързване по двойки чрез непресичащи се сегменти, така че да се образува мрежа от триъгълници. Основните му елементи са (Фигура 5.3): възли (върхове на триъгълник), ръбове (страни) и лица (същински триъгълници). Построената триангулация може да бъде изпъкнала (ако това е минималният многоъгълник, покриващ зоната на симулация), неизпъкнала (ако триангулацията не е изпъкнала) и оптимална (ако сумата от дължините на всички ръбове е минимална).

Мрежа от такива триъгълници се нарича триангулация на Делоне, ако отговаря на определени условия:

Нито една от началните точки не попада в кръга, описан около който и да е триъгълник (фиг. 5.3);

Триангулацията е изпъкнала и удовлетворява условието на Делоне, формулирано по-горе;

Сумата от минималните ъгли на всички триъгълници е максималната от всички възможни триъгълници;

Сумата от радиусите на окръжностите, описани около триъгълниците, е най-малката сред всички възможни триъгълници.

Първият от горните критерии за построяване на триангулация на Делоне, наречен кръгов, е един от основните и се проверява за всяка двойка триъгълници с общи лица. Математическата интерпретация на критерия следва от фиг. 5.3:

(5.2)

Има много начини за конструиране на триангулация на Delaunay, която е един от най-популярните методи за конструиране на триангулационна мрежа в последно време. Използва се в много ГИС системи за изграждане на модели на терена.

Когато се прилага към двумерно пространство, то се формулира по следния начин: система от взаимосвързани триъгълници, които не се припокриват, има най-малък периметър, ако нито един от върховете не попада в който и да е от кръговете, описани около образуваните триъгълници (фиг. 5.4).

Ориз. 5.4. Триангулация на Делоне

Това означава, че образуваните триъгълници в такава триангулация са възможно най-близки до равностранни и всяка от страните на образуваните триъгълници от срещуположния връх се вижда под максимален ъгъл от всички възможни точки на съответната полуравнина. Това е точно оптималната триангулация, по ръбовете на която обикновено се прави линейна интерполация за изграждане на изолинии.

Много алгоритми за конструиране на триангулация на Делоне използват следната теорема.

Теорема 1. Триангулацията на Делоне може да бъде получена от всяка друга триангулация на същата система от точки чрез последователно престрояване на двойки от съседни триъгълници ABC и BCD, които не отговарят на условието на Делоне, в двойки триъгълници ABD и ACD (фиг. 5.5).

Ориз. 5.5 Повторно построяване на триъгълници, които не отговарят на условието на Делоне

Тази операция по възстановяване често се нарича обръщане. Тази теорема позволява да се конструира триангулация на Делоне последователно, като първо се конструира някаква триангулация и след това последователно се подобрява в смисъла на условието на Делоне. Когато проверявате условието на Делоне за двойки съседни триъгълници, можете да използвате дефиницията директно, но понякога се използват други методи въз основа на изброените по-горе условия.

При тези условия се появява общата характеристика на цялата триангулация (сумата от минималните ъгли или сумата от радиусите), чрез оптимизиране на която може да се получи триангулацията на Делоне.

Както бе споменато по-горе, една от най-важните операции, извършвани при конструирането на триангулация, е проверката на условието на Делоне за дадени двойки триъгълници. Въз основа на дефиницията на триангулацията на Delaunay и съответните условия, на практика обикновено се използват няколко метода за проверка:

- проверка чрез уравнението на описаната окръжност;

– проверка с предварително изчислена описана окръжност;

– проверка на сумата от противоположни ъгли;

е модифицирана проверка на сумата от противоположни ъгли.

Много системи тестват с предварително изчислена описана окръжност. Основната идея на алгоритъма за проверка чрез предварително изчислени окръжности е предварително да се изчисли за всеки построен триъгълник центърът и радиусът на описаната около него окръжност, след което проверката на условието на Делоне ще се сведе до изчисляване на разстоянието до центъра на този кръг и сравнявайки резултата с радиуса. Центърът и радиусът r на окръжност, описана наоколо, могат да бъдат намерени като , , , r 2 = (b 2 + c 2 - 4ad)/4a 2 , където стойностите a, b, c, dопределени с формули (5.3)

(5.3)

Друг начин да напишете уравнението за този кръг е:

(5.5.)

(5.6)

Тогава условието на Delaunay за ще бъде изпълнено само когато за всяка друга точка на триангулация ще бъде:

(x 0 - x C) 2 + (y 0 - y C) 2 ≥ r 2 . (5,7)

В момента има много алгоритми за конструиране на триангулацията на Делоне. Много от добре познатите алгоритми използват дефиницията на триангулацията на Делоне като вторична характеристика на триангулацията. Следователно такива алгоритми имат следните слабости:

- алгоритмите използват постоянно изчислявани тригонометрични функции, което драстично забавя процеса;

- при изучаване на връзката между точките и базовия сегмент възникват много малки ъгли, а при използване на тригонометрични функции съществува постоянна опасност от изчезване на реда и разделяне на 0 поради ограничената точност на представяне на данни в компютър, тази ситуация изисква постоянна допълнителна обработка.

Най-известните софтуерни продукти изграждат триангулацията на Делоне, използвайки теоремата за празната топка като основен, първичен принцип за конструиране на триъгълници. Алгоритъмът изглежда така:

– цялото множество от точки се разделя на триъгълници, т.е. създават се комбинации от три точки;

– за всяка комбинация се намират описаната окръжност и координатите на нейния център;

- ако няма нито една точка от останалите вътре в кръга на текущата комбинация, то тази комбинация е триъгълник - част от триангулацията на Делоне.

Предимствата на този алгоритъм включват:

– без използване на тригонометрични функции, което не забавя процеса на конструиране;

– директно построяване на триангулацията на Делоне, без предварителни постройки;

– простота на всички изчисления и трансформации;

- в резултат на това триангулационната мрежа е представена от много триъгълници, а не от отделни линии.

Така изградената триангулация е геометричната основа за построяване на изолинии.

Алгоритмите за конструиране на триангулацията на Delaunay могат да бъдат разделени на няколко групи, които се различават по структурата на използваните входни данни, количеството изчислителни операции, първоначалните предположения и т.н. Нека разгледаме някои от тях.

Алгоритмите за сливане включват разделяне на набор от начални точки на подгрупи, изграждане на триангулация върху всяка от тях и след това комбинирането им в една мрежа. Същността на един от тези алгоритми е следната.

Наборът от начални точки се разделя с вертикални линии на две или повече части, след което всяка от тях се разделя с хоризонтални и вертикални линии на приблизително равни части. В резултат на това цялата площ на началните точки е разделена на примитиви от три или четири точки (фиг. 2.4), върху които са изградени един или два триъгълника.

Обединяването на тези триъгълници в една мрежа се извършва чрез изграждане на две базови линии (P 0 P 1 и P 2 P 3, ориз. 5.7.a), чертане на кръгове с променлив радиус, центрирани върху медианата, перпендикулярна на основната линия (фиг. 5.7, b), търсене на възел, попадащ върху кръга (точка А, ориз. 5.7. в) и построяването на нов триъгълник (P 0 P 1 A).В този случай може да се наложи да изтриете вече съществуващ триъгълник (напр. P0AB).

Итеративните алгоритми се основават на идеята за последователно добавяне на точки към частично изградена триангулация с едновременното й подобряване и възстановяване в съответствие с критериите на Delaunay. Като цяло те включват няколко стъпки и се свеждат до построяване на триъгълник върху първите три начални точки и проучване на няколко варианта за поставяне на следващата точка. По-специално се разглеждат опции за извеждането му отвъд границата на областта за моделиране, върху съществуващ възел или ръб, вътре в конструиран триъгълник и т.н. Всяка от тези опции включва извършване на определена операция: разделяне на ръб на две, лице на три и т.н.; след което получените триъгълници се проверяват за съответствие с условието на Делоне и необходимите пренареждания.

Алгоритмите с два прохода осигуряват първо конструиране на някаква триангулация, игнорирайки условията на Delaunay, и след това повторно изграждане в съответствие с тези условия. Пример за приложение на алгоритъма е показан на фиг. 5.8.

За приближаване на създадения релефен модел до реалния в него се въвеждат допълнителни елементи, които осигуряват отчитането и изобразяването на неговите линейни и площни структурни елементи. Такива допълнителни елементи са структурните линии, широко използвани в топографията, които определят "релефния скелет": вододели, талвеги, хребети, скали, первази, езера, дерета, брегови линии, граници на изкуствени структури и др., чиято съвкупност създава, като това беше рамката на триангулацията на Делоне. Тези прекъснати линии се въвеждат в триангулацията като ръбове на триъгълници, с което се постига моделирането на реални релефни елементи на фона на обща грапавост на земната повърхност. Такива ръбове се наричат ​​структурни (фиксирани, невъзстановяеми), не пресичат ръбовете на други триъгълници и не се променят впоследствие.

Задачата за конструиране на повърхностен модел, като се вземат предвид линиите на прекъсване, се нарича триангулация на Делоне с ограничения, ако условията на Делоне са изпълнени за всяка двойка съседни триъгълници, които не са разделени от линии на прекъсване. Изследователите смятат, че такава триангулация е най-ефективно конструирана с помощта на итеративни алгоритми.

Фрагмент от триангулацията на Делоне с допълнителни елементи, включени в нея, е показан на фиг. 5.9, където отдясно са показани възли, ръбове, лица и прекъснати линии, а отляво са показани прекъснати линии на терена (брегови линии, ръбове на дерета и т.н.) и точки с известни маркировки.

Алгоритмите за конструиране на триангулация на Делоне се изпълняват с реално или цяло числово представяне на координатите на възлите, което може значително да увеличи скоростта и точността на обработката, но поражда проблеми при намирането и елиминирането на съвпадащи възли.

TIN моделът се редактира лесно чрез преместване на възли, вмъкване на нови, изтриване на съществуващи, промяна на позицията на един или повече ръбове, въвеждане на нови разделителни линии и т.н. Такива промени винаги засягат малка група от съседни триъгълници, не изискват повторно изграждане на целия мрежа и се извършват в режим on-line, чрез насочване на курсора към съответния елемент.

Относно точността:

Когато поставяме колове върху характерни релефни елементи (например вододели и талвеги), пренебрегваме по-малките елементи между тях. При конструирането на контурни линии1 по такива ръбове на триъгълници възниква грешка, която зависи от големината на неравностите на релефа и ъгъла на наклона на терена. Например, средната грешка при изследване на релефа не трябва да надвишава 1/3 от релефното сечение при ъгли на наклон на повърхността от 2 до 10 градуса. Може да се изчисли, че при напречно сечение на релефа от 0,5 m граничната стойност на пропуснатите неравности (т.е. отклонението на земната повърхност от права линия, минаваща през съседни колове) не трябва да надвишава (0,5/3)*cos10 °=0,16 m.

За точността на определяне на обема на преместената почва е важна и площта, заета от релефния детайл, който не се взема предвид. Да предположим, че в квадрат с размери 20x20 м между две двойки колове има цилиндрична издутина с максимална височина 0,15 м. Лесно е да се изчисли, че пренебрегването й при представяне на тази повърхност само с два триъгълника ще доведе до грешка от приблизително 40 m3. Не толкова много, но за парцел от 1 ха, разположен на хълм или горната (обикновено изпъкнала) част на склона, вече ще получите 40 * 25 = 1000 m3 излишна почва. Ако пикетите се вземат два пъти по-често (т.е. на всеки 10 m), грешката ще намалее четири пъти и ще достигне 250 m3 на хектар. Този фактор може да се вземе предвид предварително, тъй като положителните форми на плоския релеф обикновено имат изпъкнала форма, а отрицателните форми са вдлъбнати. Ако зоната, която ще бъде изследвана, има приблизителни данни за релефа, тогава радиусът на кривината на повърхността и необходимата плътност на пикетите могат лесно да бъдат изчислени от стойностите на контурните линии или отделни височини.

За количествено определяне на качеството на изградената триангулация, ние дефинираме два вида критерии, топологични и геометрични.

Топологичният критерий се основава на най-близките съседи на точка от множество. В идеалния случай една точка има 6 съседи за 2D регион и 12 съседи за 3D регион. Получаваме топологична оценка, използвайки формула (1), където е общият брой точки в региона, е степента или броят на съседните точки, свързани с вътрешна точка.

Геометричният критерий се основава на разликата между вписаните и описаните окръжности около изчисления триъгълен елемент. Получаваме геометрична оценка, използвайки формула (2), където е броят на триъгълниците, е радиусът на вписаната окръжност, е радиусът на описаната окръжност.

Алгоритми за построяване на триангулация

Има голям брой алгоритми за конструиране на триангулация. Те се различават един от друг по трудоемкостта, сложността на внедряване на компютър и подходите за изграждане. Можете да научите повече за алгоритмите в книгата на A.V. Скворцова. Нека разгледаме някои алгоритми.

Един от първите предложени алчен алгоритъмизграждане на триангулация. Триангулацията на Делоне се нарича алчна, ако е изградена с помощта на алчен алгоритъм. Сложността на алчния алгоритъм с някои от неговите подобрения е . Поради такава голяма сложност на практика, той почти никога не се използва. Разгледайте алгоритъма стъпка по стъпка:

Етап 1.Списък на всички възможни линейни сегменти, свързващи двойки изходни точки, се генерира и сортира по дължината на сегментите.

Стъпка 2Започвайки от най-късия, сегментите се вмъкват последователно в триангулацията. Ако сегментът не се пресича с други вмъкнати преди това сегменти, той се вмъква, в противен случай се отхвърля.

Имайте предвид, че ако всички възможни сегменти имат различни дължини, тогава резултатът от този алгоритъм е недвусмислен, в противен случай зависи от реда на вмъкване на сегменти с еднаква дължина.

Итеративен алгоритъмсе основават на много проста идея за последователно добавяне на точки към частично изградена триангулация на Delaunay. Сложността на този алгоритъм се състои в трудоемкостта на намирането на триъгълник, към който се добавя точка на следващата стъпка, трудоемкостта на конструирането на нови триъгълници, както и трудоемкостта на съответното възстановяване на триангулационната структура в резултат на незадоволителна проверки на двойки съседни триъгълници на получената триангулация за условието на Делоне. Разгледайте алгоритъма стъпка по стъпка:

Етап 1.На първите три начални точки изграждаме един триъгълник.

Стъпка 2В цикъла за всички останали точки изпълнете стъпки 3-5.

Стъпка 3Следващата -та точка се добавя към вече изградената триангулационна структура, както следва. Първо, точката е локализирана, т.е. има триъгълник (построен по-рано), в който попада следващата точка. Или, ако точката не попада в триангулацията, има триъгълник на границата на триангулацията, който е най-близо до следващата точка.

Стъпка 4Ако точка удари предварително вмъкнат триангулационен възел, тогава такава точка обикновено се отхвърля, в противен случай точката се вмъква в триангулацията като нов възел. Освен това, ако точката удари някакъв ръб, тогава тя се разделя на два нови и двата триъгълника, съседни на ръба, също се разделят на два по-малки. Ако точката е строго вътре в който и да е триъгълник, тя се разделя на три нови. Ако точката е извън триангулацията, тогава се изграждат един или повече триъгълници.

Стъпка 5Извършват се локални проверки на новополучените триъгълници за съответствие с условието на Делоне и се извършват необходимите пренареждания.

При конструирането на нови триъгълници са възможни две ситуации, когато добавената точка попада или вътре в триангулацията, или извън нея. В първия случай се конструират нови триъгълници и се фиксира броят на действията, извършени от алгоритъма. Във втория е необходимо да се изградят допълнителни триъгълници, външни за текущата триангулация, като техният брой може да бъде равен в най-лошия случай? 3. За всички стъпки на алгоритъма обаче няма да се добавят повече от триъгълници, където е общият брой начални точки. Следователно и в двата случая общото време, изразходвано за изграждане на триъгълници, е.

Верижен алгоритъмедин от първите ефективни алгоритми за конструиране на триангулация се основава на процедура за регуляризиране на планарна графа и монотонна полигонална триангулация. Сложността на този алгоритъм е, където е броят на началните сегменти. Разгледайте алгоритъма стъпка по стъпка:

Етап 1.От набора от начални структурни сегменти формираме свързана равнинна графика (Фигура 4, а).

Стъпка 2Графиката е регуляризирана, т.е. добавят се нови ребра, които не пресичат други, така че всеки връх на графиката става съседен на поне един връх над него и един под него. Регулирането се извършва в две преминавания, като се използва вертикално плоско почистване. При първото преминаване отдолу нагоре последователно намираме всички върхове, от които няма ръбове, водещи нагоре. Например, на (Фигура 4, b) това е връх B. Начертавайки хоризонтална линия, намираме най-близките ръбове на графиките AD и EF, пресечени от нея отляво и отдясно. След това намираме най-ниския връх в четириъгълника DEHG и начертаваме в него ръб от B. По същия начин второто преминаване се извършва отгоре надолу (Фигура 4, c). В резултат на тази стъпка всяка област от равнинната графика се превръща в монотонен многоъгълник.

Стъпка 3Всяка област на графиката трябва да бъде разделена на триъгълници. За да направите това, можете да използвате алгоритъма за неконвексно сливане на две триангулации (Фигура 4, d).

Фигура 4. Схема на работа на алгоритъма на триангулационната верига: а) - начални сегменти; b - преминаване отдолу нагоре на регуляризацията на графиката; в) - преминаване отгоре надолу; г) - триангулация на монотонни многоъгълници

За да се приложи верижният алгоритъм, най-добре е да се използват структури от данни, в които ръбовете са представени изрично, като "Двойни ръбове" или "Възли, ръбове и триъгълници".

Недостатъкът на верижния алгоритъм е, че нищо не може да се каже предварително за формата на получената триангулация. Това не е оптимална триангулация, нито алчна, нито ограничена триангулация на Делоне. Верижният алгоритъм може да произведе много дълги удължени триъгълници.

За да се подобри качеството на получената триангулация, всички двойки съседни триъгълници, които не са разделени от структурен ръб, могат да бъдат проверени за изпълнение на условието на Delaunay и, ако е необходимо, да бъдат построени отново. В резултат ще се получи триангулация на Делоне с ограничения.