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

Устна кухина

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

20 август 2012 г. в 22:41 ч

Оптимизиране на алгоритъма за проверка на условието на Делоне чрез уравнението на описаната окръжност и неговото приложение

Ще ви кажа една тайна за това как бързо да проверите условието на Делоне за два триъгълника.
Всъщност самата оптимизация е описана малко по-долу (вижте „Оптимизиране на алгоритъма за проверка на условието на Delaunay чрез уравнението на описаната окръжност“), но ще ви разкажа за всичко по ред.

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

На входа

След като открих и преминах границите, получих много външни контури на изхода. Всеки докосващ контур има различни цветове. Всяка такава верига също съдържа известен брой вътрешни вериги.
По този начин, от гледна точка на „почистване на равнината“, ако разглеждаме външните контури поотделно, имаме набор от точки, всяка от които има по един съсед отдясно и отляво. Тези. всички точки са затворени във верига, няма нито една „висяща“ точка и всяка верига съдържа най-малко 3 точки (Фигура 1).

Фигура 1

Какво да правя

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

Търсене

След като прочетох книгата, не намерих нито един (поне един) метод за конструиране на триангулация на Делоне, който да е поне донякъде подходящ за моя случай. Не съм търсила други книги. И това беше достатъчно, подреди мислите в главата ми. В резултат на това той изобретил свой собствен „велосипед“.

Алгоритъм

1) Да приемем, като за начало, че има само една последователност в разглежданата фигура. След това всичко се свежда до последователно вземане на триъгълници. Взимаме всяка точка и се опитваме да построим триъгълник със съседни точки. Ако не беше възможно да се изгради триъгълник (линията, свързваща тези две точки, се пресича с вече изградените или линията минава в зоната на изключване (Фигура 2), преминаваме към следващата точка, да речем вдясно. Когато следващият триъгълник е намерено, добавяме го към списъка (Фигура 3) и премахваме точката, от която е построено (Фигура 4).

Фигура 2

Фигура 3

Фигура 4

Още нещо: при запис на следващия триъгълник е необходимо върховете да се запишат в обход по посока на часовниковата стрелка (в дясната координатна система). Това ще бъде полезно в бъдеще за намаляване на изчислителните ресурси.

2) Повтаряйте стъпка 1, докато пометем цялата равнина.

3) Ако има няколко последователности, т.е. един, а вътре в него има един или повече вътрешни контури (Фигура 1). Тук е необходимо да се разгледа всяка последователност поотделно. Нека вземем друг вътрешен контур. От една външна и една вътрешна ще направим две единични вериги. За да направите това, трябва да намерите два „порта“ от една верига към друга. Условие за "пристанища": те не трябва да се пресичат помежду си (дори краищата им не трябва да се допират) и не трябва да се пресичат с контурни линии (Фигура 5).

Фигура 5

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

Фигура 7

5) След 4-тия етап имаме списък с триъгълници (Фигура 8). Сякаш задачата вече е изпълнена, но остава само да направим картината красива: проверете дали условието на Delaunay е изпълнено (Фигура 9).

Фигура 8

Фигура 9

6) Гледайки напред, ще ви разкажа за шестата точка. Състои се от последователно преминаване през списъка с получени триъгълници чрез стъпка № 5. Първо маркираме всички триъгълници като „мръсни“. Във всеки цикъл проверяваме условието на Делоне за всеки триъгълник. Ако условието не е изпълнено, тогава изграждаме отново и маркираме съседите и текущия триъгълник като „мръсни“. Ако условието е изпълнено, тогава го маркираме чисто. В моето изпълнение на алгоритъма всеки триъгълник има връзка към своите съседи. В този случай точка 6 работи най-бързо.

Повече за петия етап

Сега, доколкото знам, са две възможни начиниопределете дали триъгълниците отговарят на условието на Delaunay или не: 1) Проверете сумата от противоположните ъгли. Трябва да е по-малко от 180. 2) Изчислете центъра на описаната окръжност и изчислете разстоянието до 4-та точка. Всеки знае, че условието на Делоне е изпълнено, ако точката е извън описаната окръжност.

Изчислителна мощност #1: 10 умножение/деление и 13 събиране/изваждане.
Изчислителна мощност #2: 29 умножение/деление и 24 събиране/изваждане.

От гледна точка на изчислителната мощност, която е изчислена например в книгата, вариант No1 е по-изгоден. Бих го приложил, ако не... (Фигура 10). Както се оказа след продукцията този методвърху „конвейерната лента“, резултатът беше несигурност. Това е опция, когато самият ъгъл А е повече от 180 градуса. В книгата се разглежда като един от индивидуалните частни методи. И с това изчезва цялата му елегантност, прозрачност и ефективност. И също така по-късно се оказа, че метод № 2 може да бъде много значително оптимизиран.

Фигура 10

Оптимизиране на алгоритъма за проверка на условието на Делоне чрез уравнението на описаната окръжност

Следва чиста математика.

Така че имаме:
Проверка на условието за точката M(X, Y) чрез уравнението на окръжност, минаваща през точките A(x1, y1), B(x2, y2), C(x3, y3), може да се запише като:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ знак a ≥ 0

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

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

D>=0

Фигура 11

Просто, нали?

Според книгата, отново,

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

Имаме: 15 операции умножение/деление и 14 операции събиране/изваждане.

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

Списък на използваната литература

1. Скворцов А.В. Триангулация на Делоне и нейното приложение. – Томск: Издателство Том. университет, 2002. – 128 с. ISBN 5-7511-1501-5

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

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

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

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

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

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

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

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

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

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

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

недостатък:

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

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

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

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

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

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

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

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

2)
- съставяне на уравнение на равнината.

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

Структура на презентацията:

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

, Къде – брой вътрешни точки,
– брой точки.

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

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

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

Вътрешността на окръжност, описана около всеки триъгълник, не включва точките на други триъгълници. Изгражда се по единствения начин.

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

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

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

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

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

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

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

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

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

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

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

20 август 2012 г. в 22:41 ч

Оптимизиране на алгоритъма за проверка на условието на Делоне чрез уравнението на описаната окръжност и неговото приложение

Обработка на изображения,
Програмиране

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

На входа

След като открих и преминах границите, получих много външни контури на изхода. Всеки докосващ контур има различен цвят. Всяка такава верига също съдържа известен брой вътрешни вериги.
По този начин, от гледна точка на „почистване на равнината“, ако разглеждаме външните контури поотделно, имаме набор от точки, всяка от които има по един съсед отдясно и отляво. Тези. всички точки са затворени във верига, няма нито една „висяща“ точка и всяка верига съдържа най-малко 3 точки (Фигура 1).

Фигура 1

Какво да правя

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

Търсене

Алгоритъм

Фигура 2

Фигура 3

Фигура 4

2) Повтаряйте стъпка 1, докато пометем цялата равнина.

Повече за петия етап

Сега, доколкото знам, има два възможни начина да се определи дали триъгълниците отговарят на условието на Delaunay или не: 1) Проверете сумата от противоположни ъгли. Трябва да е по-малко от 180. 2) Изчислете центъра на описаната окръжност и изчислете разстоянието до 4-та точка. Всеки знае, че условието на Делоне е изпълнено, ако точката е извън описаната окръжност.

От гледна точка на изчислителната мощност, която е изчислена например в книгата, вариант No1 е по-изгоден. Бих го приложил, ако не... (Фигура 10). Както се оказа, след поставянето на този метод на „конвейера“ се появи несигурност. Това е опция, когато самият ъгъл А е повече от 180 градуса. В книгата се разглежда като един от индивидуалните частни методи. И с това изчезва цялата му елегантност, прозрачност и ефективност. И също така по-късно се оказа, че метод № 2 може да бъде много значително оптимизиран.

Фигура 10

Оптимизиране на алгоритъма за проверка на условието на Делоне чрез уравнението на описаната окръжност

Следва чиста математика.

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ знак a ≥ 0

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

D>=0

Фигура 11

Просто, нали?

Според книгата, отново,

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

Имаме: 15 операции умножение/деление и 14 операции събиране/изваждане.

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

Списък на използваната литература

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

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

Свойства:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.3

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

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

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

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

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

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

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

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

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

Фиг.4.

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

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

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

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

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

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

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

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

ориз. 9.7.1. Изпъкнала област с дадени точки вътре

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

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

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

ориз. 9.7.2. Избор на трета точка от алгоритъма на Делоне

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

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

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