ТЕПЛОВ А.А., бакалавър, Московски държавен технически университет на името на Н.Е. Бауман, Катедра за компютърен софтуер и информационни технологии, Москва, [защитен с имейл]

МАЙКОВ К.А., доктор на техническите науки, професор, Московски държавен технически университет на името на Н.Е. Бауман, Катедра за компютърен софтуер и информационни технологии, Москва, [защитен с имейл]

Модифициран алгоритъм
Триангулация на Делоне

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

Въведение

Един от етапите, които определят ресурсоемкостта на изграждане на динамични 3D обекти с дадена степен на детайлност, е триангулацията. На практика се налага да се определи прототипа на метода на триангулация, който да удовлетворява изискването за висока производителност и ниска ресурсна интензивност с последваща модификация за специфичен клас проблеми.

Постановка на задачите за решаване

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

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

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

Итеративни алгоритми за конструиране на триангулацията на Делоне

В итеративните алгоритми се реализира последователно добавяне на точки към частично построена триангулация на Делоне. Сложността на итеративните алгоритми на Делоне се определя като O(N2) , а за случай на равномерно разпределение на точките - O(N) . Недостатъците на итеративните алгоритми на Делоне са голям брой итеративни цикли, зависимостта на алгоритъма за сортиране от структурата на изходните данни и необходимостта от проверка за условието на Делоне във всеки цикъл. Предимствата на итеративните алгоритми на Делоне са лекотата на изпълнение и високата скорост на избор на ефективен алгоритъм за сортиране въз основа на специфичен набор от входни данни.

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

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

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

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

Алгоритми стъпка по стъпка за изграждане на триангулацията на Делоне

Алгоритмите за конструиране стъпка по стъпка изпълняват само триъгълници, които удовлетворяват условието на Делоне в крайната триангулация и следователно не изискват повторно изграждане. При висока концентрация на точки използването на клетъчен алгоритъм стъпка по стъпка е неподходящо. Сложността на този алгоритъм е средно O(N), а в най-лошия случай O(N 2).

Избор на прототип за модификация на триангулацията на Делоне

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

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

Алгоритмите от този тип обаче трябва да бъдат модифицирани, за да се повиши производителността, приложима при проблеми в реално време. Алгоритъмът на двупроходния вентилатор е излишен при определяне на центъра на масата на точките. При определяне на координатата на центъра на масата на точката чрез OX или OY, при голям брой точки е неподходящо да се изчислява средноаритметичната стойност, а при големи стойности на координатите на точките може да възникне преливане на данни, което ще доведе до грешка или програмна грешка. Поради това е препоръчително всички стойности на триангулационните точки да се разделят на интервали по оста X с Δх 1, Δх 2, Δх 3 ... Δх n и по оста Y с Δy 1, Δy 2, Δy 3 . .. Δy n. Необходимо е също така да се определи броят на точките, принадлежащи към съответните интервали по осите X и Y. Получените формули за получаване на центъра на координатите на точковите маси са както следва:

• x c - x-координата на точката на центъра на масата;
• Δх i – i-ти интервал по оста X;
• X max - максималната стойност по оста X сред всички триангулационни точки;
• X min - минималната стойност по оста X сред всички триангулационни точки;

• y c - y-координата на точката на центъра на масата;
• n i е броят на точките в i-тия интервал;
• Δy i – i-ти интервал по оста Y;
• Y max - максималната стойност по оста Y сред всички триангулационни точки;
• Y min - минималната стойност по оста Y сред всички триангулационни точки.

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

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

Анализ на модифицирания алгоритъм за триангулация на вентилатор Делоне

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

• T 1 ,T 2 са стойностите на времето за изчисляване на оптималния брой интервали по осите X и Y, съответно;
• T 3 ,T 4 са стойностите на времето за изчисление X min и X max, съответно;
• T 5 ,T 6 – стойности на времето за изчисление съответно Y min и Y max;
• T 7 ,T 8 са стойностите на времето за изчисляване на стойностите на интервала по осите X и Y, съответно;
• T 9 е стойността на времето за изчисляване на стойностите на полярния ъгъл на всяка точка от масива спрямо точка A(X c ,Y c);
• T 10 е стойността на времето за сортиране чрез сливане на всички точки според полярния ъгъл спрямо точката A(X c ,Y c);
• T 11 е стойността на времето за изграждане на ръба от всяка точка на масива до точката A(X c ,Y c);
• T 12 - стойността на времето за завършване на триангулацията до изпъкналата;
• T 13 е стойността на времето за възстановяване на триангулацията, което удовлетворява условието на Делоне;
• n е масив от стойности на координатните точки.

Нека разгледаме всяка зависимост от времето отделно.

При определяне на оптималния брой интервали по осите X и Y използваме правилото на Стърджс, според което броят на интервалите n се дефинира като:

• N е общият брой наблюдения на количеството;
• [x] е цялата част от числото x.

Очевидно времевите зависимости на T 1 и T 2 имат постоянни представяния c 1 и c 2 .

На етапите на определяне на стойностите на X min , X max , Y min , Y max , псевдокодът ще изглежда така:

Xmin ← M

за i ← 1 до дължина (M) – 1

Ако Xmin › M[i]

Xmin ← M[i]

Xmax ← M

за i ← 1 до дължина (M) – 1

IfXmax< M[i]

Xmax ← M[i]

Имин ← М

за i ← 1 до дължина (M) – 1

Ако Ymin › M[i]

Ymin ← M[i]

Ymax ← М

за i ← 1 до дължина (M) – 1

Ако Ymax< M[i]

Ymax ← M[i]

От горния псевдокод се вижда ясно, че времето за намиране на максималната или минималната стойност на x или y има линейна зависимост O(N), следователно T 3 (n), T 4 (n), T 5 (n ), T 6 (n) , имат времева характеристика O(N), съответно.

Схемата за определяне на стойностите на интервала по оста X е показана на фиг. 2.

От горната диаграма се вижда и линейната времева зависимост O(N), тъй като целият набор от координати на стойностите на масива от точки участва в определянето на стойностите. Схемата за определяне на стойностите на интервалите по оста Y има подобна структура и времеви характеристики, следователно времевата зависимост за T 7 (n) и T 8 (n) е O(N).

Схемата за определяне на стойностите на полярния ъгъл за първоначалния масив от точки е показана на фиг. 3.

В псевдокод тази схема ще изглежда така:

за точки до точки

# Ако точката лежи на координатната ос между I и IV квадрант

Ако точка.x ≥ Xc и точка.y = Yc

Точка.ъгъл ← 0

# Ако точката лежи строго в първия квадрант

Иначе, ако точка.x > Xc и точка.y > Yc

Основа ← |точка.x - Xc|

Точка.ъгъл ← arctg(перпендикуляр/основа)

# Ако точката лежи на координатната ос между I и II квадранти

Иначе, ако точка.x = Xc и точка.y > Yc

Точка.ъгъл ← p/2

# Ако точката лежи строго във втория квадрант

Иначе, ако точка.x< Xc and point.y >Yc

Основа ← |точка.y - Yc|

Точка.ъгъл ← p/2 + arctg(перпендикуляр/основа)

# Ако точката лежи на координатната ос между II и III квадрант

Ако точка х< Xc and point.y = Yc

Точка.ъгъл ← стр

# Ако точката лежи строго в третия квадрант

Ако точка х< Xc and point.y >Yc

Основа ← |точка.x - Xc|

Перпендикуляр ← |точка.y - Yc|

Точка.ъгъл ← p + arctg(перпендикуляр/основа)

# Ако точката лежи върху координатната ос между III и IV квадрант

Ако точка.x = Xc и точка.y< Yc

Точка.ъгъл ← 3p/2

# Ако точката лежи строго в четвъртия квадрант

Ако точка.x > Xc и точка.y< Yc

Основа ← |точка.y - Yc|

Перпендикуляр ← |точка.x – Xc|

Точка.ъгъл ← 3p/2 + arctg(перпендикуляр/основа)

Очевидно времевата характеристика за определяне на стойностите на полярния ъгъл за първоначалния масив от координати на точки има формата O(N), следователно T 9 (n) = O(N).

Както е показано в , сортирането чрез сливане има зависимост от времето във формата O(N), следователно T 10 (n) = O(NlnN).

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

Псевдокодът за горната схема ще изглежда така:

за i ← 0 до дължина(точки) – 1

Draw(Xc,Yc,Points[i].x, Points[i].y)

Времевата характеристика също е линейна, следователно T 11 (n) = O(N).

Завършването на получената триангулация до изпъкнала се извършва по алгоритъма на Греъм. Входните данни на процедурата са множеството от точки Q, където |Q|≥3. Той извиква функцията Top(S), която връща точката в горната част на стека S, без да променя съдържанието му. Освен това се използва и функцията NextToTop(S), която връща точката, разположена в стека S, една позиция под горната точка; стек S не се променя.

Греъм (Q)

Нека p 0 е точка от множеството Q с минимална координата.

Нека ‹p 1 , p 2 ,...,p N › са точки от множеството Q, сортирани

Във възходящ ред на полярния ъгъл.

Натиснете (p 0 ,S)

Натиснете (p 1, S)

за i=2 до N направи

Докато ъгълът, образуван от точките NextToTop(S), Top(S) и pi,

Оформете завой, който не е ляв

# при движение по прекъснатата линия, образувана от тях

# точки, движението се извършва директно или надясно

Правете поп(и)

Натиснете (пи, S)

се завръща

Времето за изпълнение на процедурата на Греъм е O(NlnN), където N=дължина(Q). Колко лесно е да се покаже, че докато цикълът ще отнеме O(N) време, а сортирането на полярните ъгли ще отнеме O(NlnN) време, което предполага общата асимптотика на процедурата на Греъм, следователно T 12 (n) = O( NlnN).

Характеристиката на времето за възстановяване на триангулация, която удовлетворява условието на Делоне, както е показано в , има линейна зависимост O(N), така че T 13 (n) = O(N).

Ако заместим всички намерени времеви характеристики в израз (3), тогава получената времева зависимост ще изглежда така:

T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN) )+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

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

констатации

В резултат на сравнителен анализ на практически търсените алгоритми за триангулация на Делоне е показано, че разглежданите методи не отговарят на изискванията за изграждане в реално време на динамични триизмерни обекти с предварително определена степен на детайлност, поради което има практическа необходимост от тяхното модифициране. Предлага се модификация на двупроходния алгоритъм за триангулация на Делоне, чиято функционална характеристика е изчисляването на стойностите на центъра на масата на масива от координати на точките на триангулация чрез разделяне на масива от точки на подмножества по протежение на Оси X и Y. Направен е анализ на времевите характеристики на модифицирания алгоритъм за триангулация на Делоне. Тези изчисления позволяват значително подобряване на производителността на голям масив от точки при определяне на координатите на точката на центъра на масата и избягване на преливане на данни, а оттам и грешки в софтуерната реализация.

1. Кнут Д.Е. Изкуството на програмирането. Том 1. Основни алгоритми. – М.: Уилямс, 2008. – 680 с.
2. Кнут Д.Е. Изкуството на програмирането. Том 3. Сортиране и търсене. – М.: Уилямс, 2008. – 800 с.
3. Манделброт Б. Фрактална геометрия на природата. - М.: Институт за компютърни изследвания, 2002. - 656 с.
4. Скворцов А. В. Триангулация на Делоне и нейното приложение. - Томск: Издателство на Томския университет, 2002. - 128 с.
5. Скворцов A.V. Построяване на триангулацията на Делоне в линейно време. - Томск: Издателство на Томския университет, 1999. - С. 120-126.
6. Скворцов А.В., Мирза Н.С. Алгоритми за конструиране и анализиране на триангулация. - Томск: Издателство на Томския университет, 2006. - 168 с.
7. Томас Х. Кормен, Чарлз I. Лейзерън, Роналд Л. Ривест, Клифърд Стайн. Алгоритми: изграждане и анализ, 3-то изд.: Пер. от английски. – М.: Уилямс, 2013. – 1328 с.
8. Шайдуров В.В. Многомрежови методи на крайни елементи. – М.: Наука, 1989. – 288 с.
9. Стърджес Х. (1926). Изборът на клас-интервал. J.Amer. етатик. доц., 21, 65-66.

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

Модифицираният алгоритъм за триангулация на Делоне

Теплов A.A., бакалавър, MSTU Бауман, катедра "Софтуер и информационни технологии", Москва, [защитен с имейл]

Майков К.А., доктор на техническите науки, професор, MSTU Bauman, Катедра "Софтуер и информационни технологии", Москва, [защитен с имейл]

абстрактно:Резултатите от сравнителния анализ на практически популярните методи на триангулацията на Делоне с висока производителност и ниска консумация на ресурси са описани в тази статия. Обоснован е изборът на метода за по-нататъшна модернизация с цел изграждане на динамични 3-D обекти в реално време с определена степен на детайлност. Един от основните етапи на влакнест двупроходен алгоритъм на триангулацията на Делоне е модифициран. Предлага се алгоритъм за интервално разделяне на клетъчния масив на триангулацията в съответствие с плътността на разпределение, позволяващ да се избегнат грешките при хардуерната реализация.

ключови думи:виртуална реалност, триангулация върху даден клетъчен масив, триангулация на Делоне, изграждане на динамични 3-D обекти.

Във връзка с

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

Даден набор от N точки.

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

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

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

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

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

Край на алгоритъма.

По-долу е подробно описание на няколко алгоритма.

Алчен алгоритъм

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

Алчен методТова е метод, който никога не отменя това, което вече е направено преди. Следните стъпки се изпълняват последователно в алгоритъма.

1. Краищата на всички структурни сегменти се поставят в набора от начални точки.

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

3. Всички сегменти на линията на прекъсване се вмъкват в триангулацията.

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

Стъпка 4 се повтаря до изчерпване на сегментите.

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

Една триангулация се нарича алчна, ако е изградена от алчен алгоритъм.

Алгоритъм "Изтриване и изграждане"

Delete and Build не извършва никакви преизграждания. Вместо това, при всяко вмъкване на нов възел (a), всички триъгълници се изтриват незабавно, в които нов възел (b) попада вътре в описаните кръгове. В този случай всички отдалечени триъгълници имплицитно образуват определен многоъгълник. След това на мястото на изтритите триъгълници се изгражда запълваща триангулация чрез свързване на нов възел към този многоъгълник (фиг. c).

Ориз. 4. Алгоритъм "Изтриване и изграждане"

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

Алгоритъм "Изграждане чрез разбиване"

Алгоритъмът за вмъкване на структурни сегменти "Изграждане чрез счупване" е най-простият в изпълнение и стабилен при работа.

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

Ориз. 5. Алгоритъм "Изграждане чрез разбиване"

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

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

Алгоритъм с индексиране на центрове на k-D триъгълник - дърво

В алгоритъма за триангулация с k-D-дървото индексиране на центровете на триъгълници, само центровете на триъгълници се поставят в k-D-дървото (за k = 2). При изтриване на стари триъгълници е необходимо да се премахнат центровете им от k-D-дървото, а при конструиране на нови те трябва да бъдат въведени.

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

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

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

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

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

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

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

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

Ориз. 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, е равна на

За най-близкия вляво от отсечката АВ връх параметърът t има минимална стойност.

Ориентирайте всички гранични ръбове така, че областта, която ще се триангулира, да лежи отляво на всеки от тях. Започваме да конструираме триъгълници от всеки граничен ръб. Намерете за него най-близкия връх, чийто съответен кръг не съдържа други върхове. Нека за граничния ръб AB се намери най-близкият връх V. Тогава построяваме триъгълника 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).

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

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

Ориз. 9.7.6. Незавършена триангулация на повърхността

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

Върху непресечните страни на клетките от втората група изграждаме гранични ръбове и ги насочваме така, че съответната клетка да е вляво от ръба. Изграждаме затворена полилиния около клетките от първата група (възможни са няколко затворени линии), така че при движение по нея частта от областта, която не е разделена на триъгълници, да лежи вляво, ако погледнете към нормалното на повърхността. Правите участъци на тази полилиния също ще се използват като гранични ръбове. Ще считаме всички ръбове равни по права. За да завършим триангулацията, трябва да построим триъгълници между граничните ръбове. За всеки ръб ще търсим връх, който лежи вляво от него и може да се използва за изграждане на триъгълник. Ще търсим връх само сред онези върхове, които лежат в една и съща клетка с ръб. За да изберете връх, използваме метода на Делоне, описан по-горе и илюстриран на фиг. 9.7.2. Ако се намери такъв връх, тогава трябва да се провери дали два нови ръба на триъгълника се пресичат с някое гранично ръбо. Нека се намери най-близкият връх V за граничния ръб AB и трябва да се провери дали отсечките BV и VA не пресичат други гранични ръбове. След това изграждаме триъгълник ABV и прехвърляме ръба AB в категорията на неактивните. Ако няма ръб BV между граничните ръбове, тогава ще построим нов гранично ръб на отсечката VВ, но ако има ръб 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 VS

Ъгълът на отсечката ИЛИ с хоризонтала се определя от равенството

(9.7.8)

Тези данни позволяват да се определи положението на точката P спрямо елипсата (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 на многоъгълника, за които можем да построим триъгълник VSR. Точката 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 показва два различни варианта на триангулация за един и същ набор от точки (временно ще игнорираме кръговете, начертани на тези фигури).

Ориз. един

Като се има предвид набор от точки 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 съдържа няколко силно удължени триъгълника и не може да се припише на типа Делоне. На фиг. 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 .

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

Ориз. 4

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

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

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

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

Ориз. 5

Невалидна актуализацияFrontier(Речник &frontier, Point &a, Point &b) ( Edge *e = нов 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; )

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

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

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

Алгоритми за изграждане на триангулация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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