Методы решения задач математической физики. Рындин Е.А. - 36 стр.

UptoLike

Составители:

Рубрика:

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

В целом рекурсивный алгоритм реализуется в три этапа [2]:

- ранее построенный элемент остается неизменным при добавлении новой

точки, если последняя не попадает в описанную около него окружность;

- если новая точка попадает внутрь окружности, описанной около ранее по-

строенного элемента, то новая точка соединяется со всеми его вершинами

(при этом ранее построенный элемент рассекается на части);

- существующая между двумя точками линия сетки устраняется тогда и толь-

ко тогда, когда новая точка попадает внутрь всех окружностей, описанных

около любого ранее построенного элемента, границе которого принадлежит

данная линия сетки.

На каждом этапе определяются элементы, подлежащие разбиению, то есть

содержащие новую точку в описанных около них окружностях. Грань, общая

для двух таких элементов, отбрасывается, а каждая из оставшихся граней и но-

вая точка определяют новые элементы и линии сетки. Завершает процесс по-

строение линий сетки по полученным элементам [2].

Триагнуляцию Делоне можно получить из любой другой триангуляции по

тому же множеству точек, последовательно перестраивая пары соседних тре-

угольников АВС и ВСD, не удовлетворяющих условиям Делоне, в пары тре-

угольников АВD и АСD (рис. 12) [9].

Рис. 12. Перестроение треугольников, не удовлетворяющих условиям Делоне