Пространствена триангулация на Делоне
Проблемът за изграждане на мрежа от триъгълници, които не се припокриват, е един от основните в изчислителната геометрия и се използва широко в компютърната графика и географските информационни системи за повърхностно моделиране и решаване на пространствени задачи.
Проблемът за изграждане на мрежа от триъгълници, които не се припокриват, е поставен за първи път през 1934 г. в работата на съветския математик Б. Н. Делоне, който формулира съответните условия.
В математиката задачата за конструиране на триангулация от дадени точки е задачата за свързването им по двойки чрез непресичащи се сегменти, така че да се образува мрежа от триъгълници. Основните му елементи са (фиг. 5.3): възли (върхове на триъгълници), ръбове (страни) и лица (самите триъгълници). Построената триангулация може да бъде изпъкнала (ако е минимален многоъгълник, покриващ областта на моделиране), неизпъкнала (ако триангулацията не е изпъкнала) и оптимална (ако сумата от дължините на всички ръбове е минимална).
Мрежа от такива триъгълници се нарича триангулация на Делоне, ако отговаря на определени условия:
Нито една от първоначалните точки не попада в окръжността, описана около всеки триъгълник (фиг. 5.3);
Триангулацията е изпъкнала и удовлетворява условието на Делоне, формулирано по-горе;
Сумата от минималните ъгли на всички триъгълници е максималната от всички възможни триъгълници;
Сумата от радиусите на окръжностите, описани около триъгълниците, е минимална сред всички възможни триангулации.
Първият от горните критерии за построяване на триангулация на Делоне, наречен кръгов, е един от основните и се проверява за всяка двойка триъгълници с общи лица. Математическата интерпретация на критерия следва от фиг. 5.3:
(5.2)
Има много начини за конструиране на триангулация на Делоне, която е една от най-популярните в напоследъкметоди за конструиране на триангулационна мрежа. Използва се в много ГИС системи за изграждане на релефни модели.
Когато се прилага към двумерно пространство, то се формулира по следния начин: система от взаимосвързани триъгълници, които не се припокриват, има най-малък периметър, ако нито един от върховете не попада в който и да е от кръговете, описани около образуваните триъгълници (фиг. 5.4).
Ориз. 5.4. Триангулация на Делоне
Това означава, че получените триъгълници с такава триангулация са възможно най-близки до равностранните и всяка от страните на получените триъгълници от противоположния връх се вижда под максималния ъгъл от всички възможни точки на съответната полуравнина. Това е точно оптималната триангулация, по ръбовете на която обикновено се прави линейна интерполация за конструиране на изолинии.
Много алгоритми за конструиране на триангулация на Делоне използват следната теорема.
Теорема 1. Триангулацията на Делоне може да бъде получена от всяка друга триангулация, като се използва същата система от точки чрез последователно пренареждане на двойки от съседни триъгълници ABC и BCD, които не отговарят на условието на Делоне, в двойки триъгълници ABD и ACD (фиг. 5.5).
Ориз. 5.5.. Възстановяване на триъгълници, които не отговарят на условието на Делоне
Тази операция по възстановяване често се нарича обръщане. Тази теорема позволява да се конструира триангулацията на Делоне последователно, като първо се конструира някаква триангулация и след това последователно се подобрява в смисъла на условието на Делоне. Когато проверявате условието на Делоне за двойки съседни триъгълници, можете да използвате дефиницията директно, но понякога се използват други методи въз основа на изброените по-горе условия.
В тези условия се появява общата характеристика на цялата триангулация (сумата от минималните ъгли или сумата от радиусите), чрез оптимизиране на която може да се получи триангулация на Делоне.
Както бе споменато по-горе, един от критични операцииизвършена при конструиране на триангулация е да се провери условието на Делоне за дадени двойки триъгълници. Въз основа на дефиницията на триангулацията на Delaunay и съответните условия, на практика обикновено се използват няколко метода за проверка:
– проверка чрез уравнението на описаната окръжност;
– проверка с предварително изчислена описана окръжност;
– проверка на сумата от противоположни ъгли;
– модифицирана проверка на сумата от противоположни ъгли.
Много системи извършват теста с предварително изчислена описана окръжност. Основната идея на алгоритъма за проверка чрез предварително изчислени кръгове е предварително да се изчисли за всеки конструиран триъгълник центърът и радиусът на описаната около него окръжност, след което проверката на условието на Delaunay ще бъде намалена до изчисляване на разстоянието до центъра на тази окръжност и сравняване на резултата с радиуса. Центърът и радиусът r на описаната наоколо окръжност могат да бъдат намерени като , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, където стойностите a, b, c, dопределя се по формули (5.3)
(5.3)
Друг запис за уравнението на този кръг е:
(5.5.)
(5.6)
Тогава условието на Делоне за ще бъде изпълнено само когато за всяка друга точка на триангулация е:
(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5,7)
В момента има много алгоритми за конструиране на триангулация на Делоне. Много от добре познатите алгоритми използват дефиницията на триангулацията на Delaunay като вторична характеристика на триангулацията. Следователно в такива алгоритми се отбелязват следните слабости:
– алгоритмите използват постоянно изчислявани тригонометрични функции, което драстично забавя процеса;
– при изследване на връзката между точките и основния сегмент възникват много малки ъгли, а при изп тригонометрични функцииСъществува постоянна опасност от изчезване на ред и деление на 0 поради ограничената точност на представяне на данни в компютър; тази ситуация изисква постоянна допълнителна обработка.
Най-известните софтуерни продукти изграждат триангулация на Делоне, използвайки теоремата за празната топка като основен, основен принцип за конструиране на триъгълници. Алгоритъмът изглежда така:
– цялото множество от точки е разделено на триъгълници, т.е. създават се комбинации от три точки;
– за всяка комбинация се намират описаната окръжност и координатите на нейния център;
– ако няма нито една останала точка в кръга на текущата комбинация, то тази комбинация е триъгълник – част от триангулацията на Делоне.
Предимствата на този алгоритъм включват:
– липса на използване на тригонометрични функции, което не забавя процеса на конструиране;
– директно построяване на триангулацията на Делоне, без предварителни постройки;
– простота на всички изчисления и трансформации;
– в резултат на това триангулационната мрежа е представена от много триъгълници, а не от отделни линии.
Така изградената триангулация е геометричната основа за построяване на изолинии.
Алгоритмите за конструиране на триангулацията на Делоне могат да бъдат разделени на няколко групи, различаващи се по структурата на използваните входни данни, обема на изчислителните операции, началните предпоставки и т.н. Нека разгледаме някои от тях.
Алгоритмите за сливане включват разделяне на набор от изходни точки на подмножества, конструиране на триангулация за всяка от тях и след това комбинирането им в една мрежа. Същността на един от тези алгоритми се свежда до следното.
Набор от начални точки се разделя с вертикални линии на две или повече части, след което всяка от тях се разделя с хоризонтални и вертикални линии на приблизително равни части. В резултат на това цялата площ на началните точки е разделена на примитиви от три или четири точки (фиг. 2.4), по които са изградени един или два триъгълника.
Обединяването на тези триъгълници в една мрежа се извършва чрез изграждане на две базови линии (P 0 P 1 и P 2 P 3, ориз. 5.7.a), чертане на окръжности с променлив радиус, центрирани върху перпендикулярната ъглополовяща към основната линия (фиг. 5.7, b), търсене на възел, попадащ върху окръжността (точка А, ориз. 5.7. в) и построяване на нов триъгълник (P 0 P 1 A).В този случай може да е необходимо да изтриете съществуващ триъгълник (напр. P 0 AB).
Итеративните алгоритми се основават на идеята за последователно добавяне на точки към частично изградена триангулация с нейното едновременно подобряване и реконструкция в съответствие с критериите на Delaunay. IN общ изгледте включват няколко стъпки и се свеждат до построяването на триъгълник върху първите три отправни точкии проучване на няколко варианта за поставяне на следващата точка. По-специално се разглеждат варианти за попадане извън границите на областта за моделиране, върху съществуващ възел или ръб, вътре в конструиран триъгълник и т.н. Всяка от тези опции включва извършване на определена операция: разделяне на ръб на две, лица в три и т.н.; след което получените триъгълници се проверяват за съответствие с условието на Делоне и необходимите реконструкции.
Алгоритмите с два прохода първо включват изграждането на някаква триангулация, пренебрегвайки условията на Delaunay, и след това нейното възстановяване в съответствие с тези условия. Пример за приложение на алгоритъма е показан на фиг. 5.8.
За да се доближи създадения модел на релефа до реалния, в него се въвеждат допълнителни елементи, за да се гарантира, че неговите линейни и площни структурни елементи са взети предвид и показани. Такива допълнителни елементи са структурни линии, широко използвани в топографията, които определят „скелета на релефа“: вододели, талвеги, хребети, скали, первази, езера, дерета, брегови линии, граници на изкуствени структури и т.н., чиято съвкупност създава един вид рамка за триангулацията на Делоне. Тези структурни линии се въвеждат в триангулацията като ръбове на триъгълници, с което се постига моделиране на реални релефни елементи на фона на обща неравност на земната повърхност. Такива ръбове се наричат структурни (фиксирани, нереконфигурируеми), не пресичат ръбовете на други триъгълници и впоследствие не се променят.
Проблемът за конструиране на повърхностен модел, като се вземат предвид разделителните линии, се нарича ограничена триангулация на Делоне, ако условията на Делоне са изпълнени за всяка двойка съседни триъгълници, които не са разделени от разделителни линии. Най-ефективният начин, смятат изследователите, е да се изгради такава триангулация с помощта на итеративни алгоритми.
Фрагмент от триангулацията на Делоне с допълнителни елементи, включени в нея, е показан на фиг. 5.9, където отдясно са показани възли, ръбове, ръбове и структурни линии, а отляво са показани структурни линии на терена (брегови линии, ръбове на дерета и др.) И точки с известни маркировки.
Алгоритмите за конструиране на триангулацията на Делоне се изпълняват с реално или цяло числово представяне на координатите на възлите, което може значително да увеличи скоростта и точността на обработката, но поражда проблеми при търсене и изключване на съвпадащи възли.
TIN моделът се редактира лесно чрез преместване на възли, вмъкване на нови, изтриване на съществуващи, промяна на позицията на един или повече ръбове, въвеждане на нови структурни линии и т.н. Такива промени винаги засягат малка група от съседни триъгълници, не изискват повторно изграждане на цялата мрежа и се извършват онлайн, чрез насочване на курсора към съответния елемент.
Относно точността:
Поставяйки колове върху характерни релефни елементи (например вододели и талвеги), ние игнорираме по-малките елементи в празнините. При конструиране на контурни линии1 по такива ръбове на триъгълници възниква грешка, която зависи от размера на неравностите на терена и ъгъла на наклона на терена. Например, средната грешка при заснемане на релефа не трябва да надвишава 1/3 от напречното сечение на релефа при ъгли на наклон на повърхността от 2 до 10 градуса. Може да се изчисли, че при релефен участък от 0,5 m максималната стойност на пропуснатата неравност (т.е. отклонението на земната повърхност от права линия, минаваща през съседни колове) не трябва да надвишава (0,5/3)*cos10° =0,16 m.
За точността на определяне на обема на транспортираната почва е важна и площта, заета от неотчетения релефен детайл. Да кажем, че в квадрат от 20x20 m между две двойки колове има цилиндрична изпъкналост с максимална височина 0,15 m. Лесно е да се изчисли, че ако не се вземе предвид тази повърхност само с два триъгълника, това ще доведе до грешка от приблизително 40 m3. Не толкова много, но за парцел от 1 хектар, разположен на хълм или в горната (обикновено изпъкнала) част на склона, получавате 40 * 25 = 1000 m3 излишна почва. Ако вземете колове два пъти по-често (т.е. на всеки 10 м), грешката ще намалее четири пъти и ще достигне 250 м3 на хектар. Този фактор може да се вземе предвид предварително, тъй като положителните форми на плосък релеф обикновено имат изпъкнала форма, докато отрицателните форми имат вдлъбната форма. Ако зоната, която ще бъде изследвана, има приблизителни данни за релефа, тогава радиусът на кривината на повърхността и необходимата плътност на пикетите могат лесно да бъдат изчислени от стойностите на контурните линии или отделните височини.
Основни определения и свойства
Триангулацията е равнинна графика, чиито вътрешни области са триъгълници.
Имоти:
· Триангулацията на Делоне съответства едно към едно на диаграмата на Вороной за същия набор от точки.
· Като следствие: ако няма четири точки, които лежат на една и съща окръжност, триангулацията на Делоне е уникална.
· Триангулацията на Delaunay максимизира минималния ъгъл сред всички ъгли на всички конструирани триъгълници, като по този начин избягва "тънките" триъгълници.
· Триангулацията на Делоне максимизира сумата от радиусите на вписаните сфери.
· Триангулацията на Делоне минимизира дискретния функционал на Дирихле.
· Триангулацията на Delaunay минимизира максималния радиус на минималната околна сфера.
· Триангулацията на Делоне на равнината има минималната сума от радиусите на окръжностите, описани около триъгълниците сред всички възможни триангулации.
Фигура 1. Триангулация.
Изпъкнала триъгълник е триъгълник, при който минималният многоъгълник, обхващащ всички триъгълници, е изпъкнал. Триангулация, която не е изпъкнала, се нарича неизпъкнала.
Проблемът за конструиране на триангулация от даден набор от двумерни точки се нарича проблем за свързване дадени точкинепресичащи се сегменти, така че да се образува триангулация.
Твърди се, че една триангулация удовлетворява условието на Делоне, ако нито една от дадените точки на триангулация не попада в окръжността, описана около който и да е конструиран триъгълник.
Триангулацията се нарича триангулация на Делоне, ако е изпъкнала и удовлетворява условието на Делоне.
Фигура 2. Триангулация на Делоне.
Метод на празната топка на Делоне. Строителство в общия случай
Нека използваме празна топка, която ще преместим, променяйки размера й, така че да може да докосва точките на системата (А), но винаги да остава празна.
И така, нека поставим в системата от точки (А) празна топкаДелоне. Това винаги е възможно, ако изберете достатъчно малка топка. Нека започнем да увеличаваме радиуса му, оставяйки центъра на топката на място. В даден момент повърхността на топката ще срещне някаква точка i от системата (A). Това определено ще се случи, защото в нашата система няма безкрайно големи празнини. Ще продължим да увеличаваме радиуса на празната топка, така че точка i да остане на нейната повърхност. За да направите това, ще трябва да преместите центъра на топката от точка i. Рано или късно топката ще достигне с повърхността си друга точка от системата (А).
Фиг.3
Симплексите на Delaunay запълват пространството без пропуски или припокривания.
Описаната сфера на всеки симплекс не съдържа други точки от системата в себе си.
Нека това е точка j. Нека продължим да увеличаваме радиуса на нашата топка, като запазим двете точки на нейната повърхност. Когато топката се увеличава, тя ще достигне някаква трета точка от системата, точка k. В двумерния случай нашият „празен кръг“ ще бъде фиксиран в този момент, т.е. Ще стане невъзможно по-нататъшното увеличаване на радиуса му, докато кръгът остава празен. В същото време ние идентифицираме елементарна двумерна конфигурация от три точки (i, j, k), определящи определен триъгълник, чиято особеност е, че няма други точки от системата (A) вътре в неговата описана окръжност. В триизмерното пространство топката не се определя от три точки. Нека продължим да увеличаваме радиуса му, като запазим всичките три точки, открити на повърхността му. Това ще бъде възможно, докато повърхността на топката не срещне четвъртата точка l от системата. След това движението и растежът на празната топка ще стане невъзможно. Намерените четири точки (i,j,k,l) определят върховете на тетраедъра, който се характеризира с това, че вътре в описаната му сфера няма други точки от системата (A). Такъв тетраедър се нарича симплекс на Делоне.
В математиката симплекс е най-простата фигура в пространство с дадено измерение: тетраедър - в тримерно пространство; триъгълник - в две измерения. Произволни три (четири) точки от системата, които не лежат в една равнина, винаги определят определен симплекс. Той обаче ще бъде симплекс на Делоне само ако описаната му сфера е празна. С други думи, симплексите на Делоне се определят от специален избор на тройки (четворки) точки в система (A).
Построихме един симплекс на Делоне, но като поставим празната топка на различни места и повторим същата процедура, могат да се дефинират други. Твърди се, че множеството от всички симплекси на Делоне на система (А) запълва пространството без припокривания и пропуски, т.е. осъществява разделението на пространството, но този път на тетраедри. Този дял се нарича Облицовка Делоне(фиг. 3).
Приложение на триангулацията на Делоне
Триангулациите на Делоне често се използват в евклидовото пространство. Евклидовото минимално обхващащо дърво е гарантирано, че лежи върху триангулацията на Делоне, така че някои алгоритми използват триангулация. Освен това, чрез триангулацията на Делоне, проблемът на евклидовия пътуващ търговец е приблизително решен.
При 2D интерполация, триангулацията на Delaunay разделя равнината на възможно най-дебелите триъгълници, като избягва твърде остри и твърде тъпи ъгли. Използвайки тези триъгълници, можете да изградите например билинейна интерполация.
Друг често срещан проблем в геоинформатиката е изграждането на склонови изложения. Тук е необходимо да се определят доминиращите посоки на склоновете по кардинална посока и да се раздели повърхността на региони, в които доминира определена посока. Тъй като определянето на експозицията няма смисъл за хоризонтални участъци от повърхността, участъците, които са хоризонтални или имат лек наклон, се разпределят в отделен регион, напр.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.
Фиг.4.
Проблемът за изчисляване на експозициите на склона обикновено се използва за анализ на осветеността на Земята. В тази връзка често има нужда допълнително да се вземе предвид текущото положение на Слънцето, т.е. експозицията се изчислява като посоката между нормалата към триъгълника и посоката към Слънцето.
По този начин всеки триангулационен триъгълник може да бъде класифициран според принципа на принадлежност към определен регион. След това просто трябва да извикате алгоритъма за избор на регион.
Триангулацията е приближаването на повърхността на моделиран обект чрез триъгълни плочи, отдалечени от него на разстояние, което не надвишава определена определена стойност 6. Всички триъгълни плочи трябва да бъдат свързани заедно. Върховете им лежат на повърхността. С набор от триъгълни плочи се работи по-лесно, отколкото с обща повърхност. Ще наричаме триъгълни плочи триъгълници. За триъгълник бързо се изчислява разстоянието до дадена точка или точката на пресичане с дадена линия в пространството. Триангулацията на лицата се извършва за визуално възприятие на геометричния модел, така че страните на триъгълниците са избрани така, че окото да не забележи прегъванията.
Когато се показват геометрични обекти чрез триъгълници върху параметрични равнини на повърхности, трябва да се конструира пространствена триангулация на лицата на тялото чрез изчисляване на масив от точки в пространството и масив от нормали към лицата на тялото в тези точки, като се използва масив от двуизмерни точки За бързо показване на тела, техните лица се апроксимират от триъгълни плочи, изградени върху нормални точки, за да се определи поведението на светлинните лъчи, взаимодействащи с лицата на тялото. Чертежите на тонове в предишните глави и в тази глава са направени с помощта на триангулация.
В резултат на повърхностна триангулация искаме да имаме масив от двумерни точки на параметрична равнина и масив от тройки цели числа, които са броят на точките в първия споменат масив. Така всеки триъгълник ще бъде представен от три номера на неговите върхове в масива с параметри. За всяка двумерна точка от параметричния домейн може да се изчисли пространствена точка на повърхността и повърхностната нормала в нея. Пространствените точки и нормалите могат да се съхраняват в масиви, подобни на масив от 2D точки.
Нека да разгледаме някои методи на триангулация. За плоски повърхности има рентабилни методи за триангулация, при които триъгълници се конструират в граничните точки на повърхността и няма нужда да се търсят точки вътре в параметричната област.
Триангулация на Делоне.
Нека разгледаме някаква зона в самолета. Ще наречем област изпъкнала, ако при движение по нейната граница трябва да се обърнете само в една посока (само наляво или само надясно). Алгоритъмът на Delaunay може да се използва за триангулиране на изпъкнали равнинни области. Няма да можем директно да приложим този алгоритъм за триангулиране на повърхности със свободна форма, но ще използваме неговия метод за конструиране на триъгълници.
Ориз. 9.7.1. Изпъкнала област с дадени точки вътре
Нека е дадена някаква изпъкнала двумерна област, ограничена от затворена начупена линия и набор от точки вътре в тази област (фиг. 9.7.1).
Изисква се посочената област да се раздели на триъгълници, чиито върхове са зададените точки вътре в областта и върховете на прекъснатата линия, която я ограничава. Триъгълниците не трябва да се застъпват, а страните им могат да се пресичат само във върховете.
Няколко различни набора от триъгълници могат да бъдат конструирани, за да запълнят определена област. Във всички случаи броят на триъгълниците е равен на , където K е броят на върховете на ограничаващата полилиния, I е броят на дадените точки вътре в областта.
Ориз. 9.7.2. Избор на трета точка от алгоритъма на Делоне
Триангулация на регион ще бъде триангулация на Делоне, ако няма върхове на други триъгълници вътре в кръга, описан около всеки триъгълник. Триангулацията на Делоне изгражда триъгълници, възможно най-близки до равноъгълните (не позволява изграждането на необосновано удължени триъгълници).
Може да се нарече балансиран. Триангулацията на Делоне ще бъде уникална, ако няма четири върха, които лежат на една и съща окръжност.
Нека разгледаме триангулацията на Делоне. Ще наричаме върховете на полилинията, ограничаваща региона, а дадените точки вътре в региона върхове на триангулацията. Страните на триъгълниците ще наричаме ръбове. Сред ръбовете избираме сегменти от ограничаващата полилиния, които ще наричаме гранични ръбове. Нека ориентираме всички гранични ръбове, така че изпъкналата област да лежи отляво на всеки ръб. Нека е необходимо да се построи триъгълник, чиято страна е граничният ръб AB, показан на фиг. 9.7.2.
През върховете A, B и всеки връх, който не лежи на една права с тях, може да се начертае окръжност. Като трети връх на триъгълника избираме връх V, съответната окръжност не съдържа други върхове от същата страна спрямо отсечката AB, на която лежи точка V. За гранично ребро в общия случай може да има един такъв връх да се намери. Ще го наречем най-близкия. Центърът на окръжност, минаваща през точки A, B и V, лежи в пресечната точка на перпендикуляри към средите на отсечки AB, BV и VA. Положението на центъра на окръжността ще се характеризира с параметъра t на отсечката MN, перпендикулярна на ръба AB, еднаква по дължина и минаваща през средата на ръба AB.
Ориз. 9.7.3. Триангулационен процес на Делоне
За всички върхове, разположени вляво от сегмент AB, най-близкият връх има най-малкия параметър t. Окръжността, съответстваща на най-близкия връх, не съдържа други върхове вляво от отсечката AB. Нека върховете A, B и V са описани съответно с двумерни радиус-вектори. Радиус векторите на средите на сегментите AB и BV ще бъдат равни
Стойността на параметъра t на правата, съответстваща на позицията върху нея на центъра на окръжността, минаваща през точки A, B и V, е равна на
За върха, който е най-близо до отсечката AB, параметърът t има минимална стойност.
Нека ориентираме всички гранични ръбове, така че областта, която ще бъде триангулирана, да лежи отляво на всеки от тях. Започваме да конструираме триъгълници от всеки граничен ръб. Нека намерим най-близкия му връх, чиято съответна окръжност не съдържа други върхове. Нека най-близкият връх V е намерен за граничното ребро AB. След това построяваме триъгълник ABV и прехвърляме ребро AB в категорията на неактивните. Ще наричаме неактивни ръбове и върхове, които не участват в алгоритъма за триангулация. Ако сред граничните ръбове няма ребро BV, тогава конструираме ново гранично ребро на сегмента VB. Ако сред граничните ръбове има ребро BV, тогава прехвърляме него и върха B в категорията на неактивните. Ако сред граничните ръбове няма ребро VA, тогава ще построим ново гранично ребро на сегмента AV. Ако сред граничните ръбове има ръб VA, тогава го прехвърляме и връх A в категорията на неактивните. Процесът на триангулация е показан на фиг. 9.7.3.
Ориз. 9.7.4. Триангулация на Делоне
Завършваме триангулацията, когато всички върхове и ръбове станат неактивни. Резултатът от триангулацията на дадена област е показан на фиг. 9.7.4.
Триангулация по корекционен метод.
Нека разгледаме триангулацията на определена повърхност с правоъгълна област за определяне на параметрите. Разделяме областта за определяне на параметрите на повърхността на правоъгълни клетки с двумерни линии. Тези линии образуват правоъгълна мрежа. Нека приемем параметричните разстояния между съседни линии в съответствие с формула (9.4.7) за равни
Нека приемем параметричните разстояния между съседни линии в съответствие с формула (9.4.8) за равни
Чрез конструиране на диагонали във всички правоъгълни клетки получаваме триангулация на повърхността (получаваме набор от триъгълници, който отговаря на изискванията). На фиг. 9.7.5 показва триангулацията на повърхността на въртене по описания метод.
Нека разгледаме триангулацията на повърхност с произволна граница. Ще изградим триангулационния метод върху корекцията чрез гранични контури на описаната по-горе повърхностна триангулация с правоъгълна област за определяне на параметрите.
Ориз. 9.7.5. Триангулация на повърхност с правоъгълна област за определяне на параметри
Нека повърхностната граница в областта на дефиниране на параметъра е описана от няколко непресичащи се двумерни контура (2.12.7). Един от контурите е външен и съдържа останалите контури. За положителна посока за всеки контур ще вземем посоката, по която, когато се движим, областта на дефиниране на повърхността е винаги вляво от контура, когато гледаме към нормалата на повърхността. Нека построим полигони в положителната посока на граничните контури на зоната за дефиниране на повърхността. За да конструирате гранични полигони, трябва да преминете по граничните контури на повърхността с някаква променлива стъпка и да попълните масив от двумерни точки, чиито координати са параметрите на повърхността. Ще изградим многоъгълник от точки на параметрична равнина, но стъпката при преместване от една точка в друга ще се определя от пространствената геометрия, а именно от условието, че отклонението на дъгата на кривата между съседни точки е не повече от дадено стойност. Изчисляваме параметричните стъпки за конструиране на многоъгълник за повърхностната гранична контурна крива, използвайки формула (9.4.4).
Всеки полигон се състои от подреден набор от двумерни точки. Всеки участък от многоъгълник може да се разглежда като двумерен сегмент от права линия, изграден върху две съседни точки. Ние ще използваме такива области като гранични ръбове, а точките от полигоните, върху които се основават ръбовете, ще се използват като триангулационни върхове. Тъй като зоната за определяне на повърхностните параметри се намира вляво от граничните полигони, когато конструирате триъгълници за всеки граничен триангулационен ръб, трябва да търсите третия връх на триъгълника вляво от ръба.
Нека определим кои възли лежат вътре в граничните полигони и кои лежат на границата или извън зоната за дефиниране на повърхността. Използвайки тази информация, сортираме клетките на правоъгълната мрежа в две групи. Първата група включва клетки, които се намират изцяло в областта, където се определят параметрите на повърхността (клетките не трябва да докосват граничните полигони). Втората група включва останалите клетки (лежащи извън зоната за дефиниране на повърхността или пресечени от гранични полигони).
Ориз. 9.7.6. Незавършена повърхностна триангулация
Във всяка клетка от първата група, използвайки диагонал, ще изградим два триъгълника. Така получаваме незавършена триангулация. Пример за конструиране на триъгълници в клетки от първата група за повърхност на въртене, ограничена от контури, е показан на фиг. 9.7.6.
Ще изградим гранични ръбове върху непресечените страни на клетките от втората група и ще ги насочим така, че съответната клетка да е вляво от ръба. Около клетките от първата група ще построим затворена прекъсната линия (възможно е няколко затворени линии), така че при движение по нея частта от областта, която не е разделена на триъгълници, да лежи отляво, когато се гледа към повърхността нормално . Също така ще използваме правите участъци на тази прекъсната линия като гранични ръбове. Ще считаме всички ръбове за равни. За да завършим триангулацията, трябва да конструираме триъгълници между граничните ръбове. За всяко ребро ще търсим връх, който лежи вляво от него и може да се използва за построяване на триъгълник. Ще търсим връх само сред тези върхове, които лежат в една клетка с ръба. За да изберем връх, използваме метода на Delaunay, описан по-горе и илюстриран на фиг. 9.7.2. Ако се намери такъв връх, тогава трябва да проверите дали два нови ръба на триъгълника се пресичат с някой граничен ръб. Нека бъде намерен най-близкият връх V за граничния ръб AB и проверете дали отсечките BV и VA не пресичат други гранични ръбове. След това ще построим триъгълник ABV и ще прехвърлим ръба AB в неактивната категория. Ако няма ребро BV сред граничните ребра, тогава ще построим ново гранично ребро на сегмента VB, но ако има ребро BV сред граничните ребра, тогава ще прехвърлим него и върха B в категорията на неактивните. Ако сред граничните ребра няма ребро VA, тогава ще построим ново гранично ребро на сегмента AV, но ако има ребро VA сред граничните ребра, тогава ще прехвърлим него и върха A в категорията на неактивни.
Ако сегмент или VA пресича други гранични ръбове, тогава преминаваме към търсене на най-близкия връх за друг граничен ръб. Триангулацията ще бъде завършена, след като всички ръбове и върхове бъдат класифицирани като неактивни.
Ориз. 9.7.7. Триангулация по корекционен метод
На фиг. 9.7.7 показва повърхностна триангулация по метода на коригиране на триъгълници в клетки, пресечени от гранични контури. На фиг. 9.7.8, използвайки получената триангулация, се показва самата повърхност.
Ако граничните полигони и повърхността имат някаква симетрия, тогава триангулацията по корекционния метод ще има подобна симетрия.
Триангулация по абсорбционен метод.
Нека разгледаме друг метод на триангулация. По скорост отстъпва на триангулацията на Делоне и нейните модификации. За да започнете процедурата на триангулация, е необходимо да представите повърхностната граница под формата на затворени многоъгълници. По време на процеса на триангулация ще трябва да определим стъпки въз основа на параметрите на повърхността. При известна посока на движение тези стъпки се определят по формули (9.4.6). Приблизителните стъпки за параметрите на повърхността могат да бъдат намерени, както следва. Нека дефинираме област в равнината на параметрите около определена точка по такъв начин, че всеки пространствен сегмент от точка до точка в тази област да не е по-далеч от дадена стойност S от повърхността.
За да направите това, изчисляваме допустимите увеличения на параметрите по координатните линии
където са коефициентите на първата и втората квадратична форма на повърхността в точка . Като граница на необходимия регион ще вземем елипса с център в точка и полуоси. Тази елипса има уравнението
Ако искате да намерите точка в равнината до точка в посоката, дадена от ъгъла с оста и , тогава нейните параметри ще бъдат
Първо, нека разгледаме по-прост случай, когато площта на параметрите на повърхността е ограничена до един външен контур. Ние апроксимираме повърхностната граница чрез затворен многоъгълник в параметричния домейн. При изграждането на триангулация ще използваме работния многоъгълник, който в този случай ще приемем за полигона на външния контур. Ще добавим многоъгълните точки към получения масив от двумерни точки. Ще изградим триъгълници от ръба на работната зона, като я стесним, докато останат само три точки в работната зона.
Нека намерим връх в работния многоъгълник, в който той се превръща в региона. Такава точка винаги съществува и ъгълът на завъртане при нея е по-малък. Нека означим тази точка с O, а нейните параметри с. В близост до тази точка ще построим един или два триъгълника, в зависимост от ъгъла на завъртане. Ако ъгълът е по-малък, тогава върху тези три точки ще изградим един триъгълник (фиг. 9.7.9). В противен случай върху тази, две съседни и една нова точка ще построим два триъгълника (фиг. 9.7.11). Новата точка се обозначава с P. Ще търсим точка P на диагонала на успоредника B OS P. Ако върхът на успоредника лежи вътре в елипсата (фиг. 9.7.10), тогава ще го приемем за точка P В противен случай ще приемем пресечната точка на елипсата и диагонала на успоредника за точка P . В последния случай изобщо не е необходимо да се търси пресечната точка на елипсата и сегмента.
Координатите на точка P се определят чрез координатите на точки O BC
Ъгълът на отсечката OP с хоризонталата се определя от равенството
(9.7.8)
Тези данни позволяват да се определи положението на точка Р спрямо елипсата (9.7.5).
В случая, показан на фиг. 9.7.9, нека построим триъгълник (запомнете номерата на неговите върхове) и изтрийте точка O в работната зона. В случая, показан на фиг. 9.7.11, ще построим два триъгълника и в работната област ще заменим точка O с точка P и ще поставим последната в получения масив от точки. На фиг. Фигура 9.7.12 показва многоъгълника, получен след построяването на два триъгълника и елиминирането на точка O. И в двата случая точка O ще бъде премахната от работния многоъгълник и работният многоъгълник ще се стесни. Обърнете внимание, че триъгълници могат да бъдат конструирани само когато работната зона след стесняване не се пресича сама.
Ориз. 9.7.9. Построяване на триъгълник
Ориз. 9.7.10. Резултат многоъгълник
Ориз. 9.7.11. Построяване на два триъгълника
Ориз. 9.7.12. Резултат многоъгълник
Такива ситуации са показани на фиг. 9.7.13. Те могат да възникнат, когато страните на построените триъгълници пресичат страните на работната площ, които не са съседни на тях. Преди да конструирате нов триъгълник, както в случая, показан на фиг. 9.7.9, а в случая, показан на фиг. 9.7.11, трябва да се направи проверка, за да се гарантира, че полученият полигон не се пресича сам.
Освен това, когато се определя позицията на точка P, е важно тя да е на достатъчно разстояние от другите точки на работната зона и да не се доближава до сегментите, свързващи точките на зоната. В противен случай могат да възникнат трудности в бъдеще при конструирането на триъгълници. Следователно, преди да стесните работния многоъгълник, трябва да проверите получения полигон за самопресичане. Ако е невъзможно да се изгради триъгълник (триъгълници) близо до точка O, тогава вместо това трябва да намерите друга точка, в която многоъгълникът се увива в контура повече, отколкото в други, и да извършите описаните действия в нея.
След това с модифицираната работна зона ще извършим същите действия, които току-що описахме. Нека намерим точка в работния многоъгълник, в която той се обръща вътре в зоната повече, отколкото в други точки, проверете за възможността за стесняване на многоъгълника в нея чрез изграждане на един или два триъгълника и стеснете многоъгълника.
Ориз. 9.7.13. Не можете да изграждате триъгълници в този ъгъл.
Продължавайки този процес, ще разширим масива от двумерни точки и масива от триъгълници, като в същото време ще стесним работния многоъгълник, намалявайки площта, която покрива, и броя на неговите точки. На някакъв етап от тези действия ще получим работещ многоъгълник, състоящ се от три точки. Нека изградим последния триъгълник в тези точки, елиминираме работната зона и завършим триангулацията. При описания метод на триангулация зоната, ограничена от работната зона, се елиминира чрез изрязване на триъгълници от нея.
Нека разгледаме общия случай, когато площта на параметрите на повърхността е ограничена от един външен контур и няколко вътрешни контура, които лежат изцяло вътре във външния контур. Ние апроксимираме повърхностната граница чрез затворени многоъгълници в параметричния домейн. За всеки контур ще изградим собствен полигон. Както при контурите, така и при изградените върху тях полигони трябва да се спазва правилото за тяхната взаимна ориентация. Ориентацията на вътрешните многоъгълници трябва да е противоположна на ориентацията на външния многоъгълник. Нека започнем да конструираме триангулацията с полигона на външния контур. Нека поставим точките му в получения масив от двумерни точки и да направим самия многоъгълник работещ.
Ще конструираме триъгълници по същия начин, както в случай на просто свързана област. Да намерим точка O в работната зона, да проверим за възможността за стесняване на работната зона там и да стесним зоната. Ако има вътрешни контури, става по-трудно да се провери възможността за стесняване на работната зона в избрана точка. В допълнение към описаните проверки за пресичане на страните на триъгълници със страните на работната площ е необходимо да се провери пресичането на страните на триъгълници със страните на всички вътрешни многоъгълници.
Нека проверим възможността за построяване на два триъгълника в точка O (фиг. 9.7.11) и установим, че новата точка P, веднъж построена, ще попадне вътре в един от вътрешните многоъгълници или ще бъде в неприемлива близост до неговите сегменти. В този случай няма да конструираме точка P, а вместо това ще включим този вътрешен многоъгълник в работния многоъгълник чрез конструиране на двата триъгълника, показани на фиг. 9.7.14.
За да включим точките на един от вътрешните многоъгълници в работния полигон, намираме сред точките на вътрешния многоъгълник точката, която е най-близка до точка C (съседна на точка O) на работния многоъгълник.
Нека построим триъгълници в точките OCF и CEF и между точките O и C на работната зона вмъкнете точки от вътрешния многоъгълник, започвайки от точка F и завършвайки с точка E. Така ще разбием работната зона на сегмента OS, прекъснете вътрешен многоъгълник на отсечката EF и ги обединява с отсечки OF и EU.
Ориз. 9.7.14. Построяване на два триъгълника
Ориз. 9.7.15. Обединяване на външни и вътрешни полигони
Резултатът от сливането е показан на фиг. 9.7.15. Разбира се, преди обединяването на външните и вътрешните полигони трябва да се направят проверки, за да се гарантира коректността на тази операция.
След това ще продължим да стесняваме работната зона по описания начин, докато не се окажем в непосредствена близост до друга вътрешна зона и я включим в работната зона. В резултат на това всички вътрешни полигони ще бъдат включени в работния полигон, който трябва да бъде стеснен до последните три точки. В резултат на това цялата многосвързана област за определяне на параметрите на повърхността ще бъде покрита с триъгълници.
Ориз. 9.7.16. Не можете да строите триъгълници в този ъгъл.
Възможно е да има ситуации, когато е невъзможно да се построи един триъгълник върху дадените многоъгълници. На фиг. Фигура 9.7.16 показва област, ограничена от два полигона, всеки от които се състои от четири сегмента. За външния многоъгълник не можем да продължим триангулацията, защото вътрешният многоъгълник ни пречи. В този случай ще намерим две съседни точки B и C на многоъгълника, за които можем да построим триъгълник HRV. Точка P се проектира върху средата на страната BC и се намира на такова разстояние от нея, че новият триъгълник не пресича многоъгълниците.
Други методи на триангулация.
Има и други начини за триангулация. Например, след конструирането на полигоните на външните и вътрешните контури на зоната за дефиниране на повърхността, може да се избере различна стратегия за конструиране на триъгълници. Друг вариант е да комбинирате външните и вътрешните полигони в един многоъгълник, преди да започнете триангулацията. Можете да „скицирате“ точки в зоната за дефиниране на параметри, като използвате определен алгоритъм и да извършите триангулация на Делоне, като използвате тях и точките на граничните контурни полигони. Има алгоритми, които първо конструират големи триъгълници и след това ги разделят на управляеми размери.
Триангулация на тялото.
Триангулацията на тяло е набор от триъгълници, получени чрез триангулиране на повърхностите на лицата му. Триангулацията на отделни повърхности се различава от триангулацията на лицата на тялото по това, че в последния случай граничните полигони за съседни повърхности трябва да са последователни (фиг. 9.7.17).
Ориз. 9.7.17. Консистенция на полигона на границата на лицето на тялото
Секции от многоъгълници на съседни лица, минаващи по общи ръбове, ще бъдат последователни, ако точките им съвпадат в пространството.
Приложение на триангулацията.
Построените в резултат на триангулацията триъгълници се използват за получаване на тонални изображения. На фиг. 9.7.18 и 9.7.19 показват триъгълници на лицето на листово тяло, чието тонално изображение е показано на фиг. 6.5.1.
Ориз. 9.7.18. Триангулация на лице на тялото по метода на корекция
Разделянето на областта за определяне на параметрите на повърхността в триъгълници може да се използва в интеграли (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) при изчисляване на геометричните характеристики на телата . По време на численото интегриране параметричната стъпка за криви трябва да се изчисли с помощта на формула (8.11.5), а за повърхности параметричните стъпки трябва да се изчислят с помощта на формули (8.11.1) и (8.11.2).
Триангулацията за краен набор от точки S е проблемът за триангулиране на изпъкналата обвивка CH(S), обхващаща всички точки от множеството S. Правите сегменти в триангулацията не могат да се пресичат - те могат да се срещат само в общи точки, принадлежащи на множеството S. Тъй като прави сегменти затварят триъгълници, ще ги считаме за ребра. На фиг. Фигура 1 показва две различни версии на триангулация за един и същи набор от точки (ние временно ще пренебрегнем кръговете, начертани на тези фигури).
Ориз. 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. Първо, точката може да е вътре в някакъв триъгълник и след това такъв триъгълник се заменя с три нови триъгълника. Второ, ако точка съвпада с един от триангулационните ръбове, тогава всеки от двата триъгълника, съседни на този ръб, се заменя с два нови триъгълника. От това следва, че след добавяне на всички i точки, общият брой на триъгълниците ще бъде (n - i - 2) + (2i) или просто n + i - 2.
Ориз. 2
В този раздел ще представим алгоритъм за генериране на специален тип триангулация, известна като триангулация на Делоне. Тази триангулация е добре балансирана в смисъл, че образуваните триъгълници са склонни да бъдат равноъгълни. Например, триангулацията, показана на фиг. 1а може да се припише на типа триангулация на Delaunay, а на фиг. 1b триангулацията съдържа няколко силно удължени триъгълника и не може да бъде отнесена към типа Delaunay. На фиг. Фигура 3 показва пример за триангулация на Делоне за набор от голям брой точки.
Ориз. 3
За да формираме триангулация на Делоне, имаме нужда от няколко нови определения. Набор от точки се счита за кръгъл, ако има окръжност, върху която лежат всички точки в набора. Такава окръжност ще бъде описана за даден набор от точки. Описаната окръжност на триъгълник минава през трите му (неколинеарни) върха. Казва се, че една окръжност ще бъде без точки по отношение на дадено множество от точки S, ако няма точки от множеството S вътре в окръжността, но точки от множеството S могат да бъдат разположени върху окръжността, която е най-безточкови.
Триангулация на набор от точки S ще бъде триангулация на Делоне, ако описаната окръжност за всеки триъгълник не съдържа точки. В триангулационната диаграма Фиг. Фигура 1а показва две окръжности, които очевидно не съдържат други точки в себе си (можете да начертаете окръжности за други триъгълници, за да сте сигурни, че те също са свободни от точки от множеството). Това правило не се спазва в диаграмата на фиг. 16 - една точка от друг триъгълник попада в начертаната окръжност, следователно тази граангулация не принадлежи към типа Делоне.
Могат да се направят две допускания относно точките в множеството S, за да се опрости алгоритъмът за триангулация. Първо, за да съществува изобщо триангулация, трябва да приемем, че множеството S съдържа поне три точки и че те не са колинеарни. Второ, за да бъде уникална триангулацията на Делоне, е необходимо нито една четири точка от множеството S да не лежи на една и съща описана окръжност. Лесно е да се види, че без такова предположение триангулацията на Делоне няма да бъде уникална, тъй като 4 точки върху една описана окръжност ни позволяват да реализираме две различни триангулации на Делоне.
Нашият алгоритъм работи, като непрекъснато увеличава текущата триангулация един триъгълник наведнъж. Първоначално текущата триангулация се състои от един ръб на обвивката; в края на алгоритъма текущата триангулация става триангулация на Делоне. При всяка итерация алгоритъмът търси нов триъгълник, който се свързва с границатекуща триангулация.
Дефинирането на границата зависи от следната диаграмакласификация на ръбовете на триангулацията на Делоне спрямо текущата триангулация. Всеки ръб може да бъде спящ, живили мъртъв:
- спящи ребра: ребро на триангулация на Делоне е латентно, ако все още не е открито от алгоритъма;
- живи ребра: реброто е живо, ако е намерено, но е известна само една съседна област;
- мъртви ребра: Един ръб се счита за мъртъв, ако е намерен и двете съседни области са известни.
Първоначално единственият ръб, принадлежащ на изпъкналия i лоб, е жив - неограничена равнина е съседна на него, а всички останали ръбове са латентни. Докато алгоритъмът работи, краищата преминават от спящи към живи към мъртви. Границата на всеки етап се състои от набор от живи ръбове.
При всяка итерация се избира който и да е от ръбовете на границата и се подлага на обработка, която се състои в търсене на неизвестна област, към която принадлежи реброто e, ако тази област се окаже триъгълник f, определен от крайни точки на ръба e и някакъв трети връх v, тогава ръбът e става мъртъв, тъй като и двете области, съседни на него, вече са известни. Всеки от другите два ръба на триъгълника t се прехвърля в следното състояние: от спящ в жив или от жив в мъртъв. Тук ще бъде извикан връх v конюгатс ръб e. В противен случай, ако неизвестната област се окаже безкрайна равнина, тогава ръб e просто умира. В този случай ребро e няма спрегнат връх.
На фиг. Фигура 4 показва работата на алгоритъма, където действието се извършва отгоре надолу, а славата вдясно. Границата на всеки етап е подчертана с дебела линия.
Алгоритъмът е реализиран в програмата delaunayTriangulate. Програмата получава масив s от n точки и връща списък от триъгълници, представляващи триангулацията на Делоне. Реализацията използва класа на пръстенния списък и класовете от раздела Геометрична структура на данните. Класът Dictionary може да бъде всеки речник, който поддържа необходимите операции. Например, можете да замените #define Dictionary RandomizedSearchTree.
списък
Ориз. 4
Триъгълниците, които образуват триангулация, се записват в списъка с триъгълници. Границата е представена от речник на граничните живи ръбове. Всеки ръб е насочен така, че неизвестната област за него (за определяне) лежи вдясно от ръба. Функцията за сравнение edgeCmp се използва за търсене на речника. Той сравнява началните точки на два ръба, ако те са равни, тогава техните крайни точки се сравняват:
Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) върне 1; ако (a->org > b->org) върне 1; ако (a->dest< b->dest) връщане -1; if (a->dest > b->dest) върне 1; връщане 0; )
Как границата се променя от една стъпка на друга и как функцията updateFrontier променя речника на границата, за да отрази тези промени? Когато нов триъгълник t е свързан с границата, състоянията на трите ръба на триъгълника се променят. Краят на триъгълника t, съседен на границата, се променя от жив на мъртъв. Функцията updateFrontier може да игнорира този край, тъй като той вече трябва да бъде премахнат от речника, когато се извика функцията removeMin. Всеки от двата останали ръба на триъгълника t променя състоянието си от спящ на жив, ако преди това не е бил записан в речника, или от жив на мъртъв, ако ръбът вече е в речника. На фиг. 5 показва и двата случая. Съгласно фигурата, обработваме живия ръб af и след като установим, че точка b е негов конюгат, добавяме триъгълник afb към текущата триангулация. След това търсим edge fb в речника и тъй като все още го няма и се открива за първи път, състоянието му се променя от спящо на живо. За да редактирате речника, ще завъртим ръба fb, така че неизвестният регион, съседен на него, да лежи вдясно от него и ще запишем този ръб в речника. Тогава ще намерим ръба ba в речника - тъй като е в него, той вече е жив (известната област, съседна на него, е триъгълник abc). Тъй като непознатата за него област, триъгълник afb, току-що беше открита, този ръб е премахнат от речника.
Функцията updateFrontier редактира граничния речник, в който състоянието на ръба от точка a до точка b се променя:
Ориз. 5
Void updateFrontier (Речник
Функцията 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) Методи за ускоряване.Въз основа на статистически зависими точки. Началният триъгълник е триъгълникът, в който попада предишната точка. След това свързваме две точки - предишната и новата.
Преминаваме от първата точка към другата.
