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

Триангуляция полигона это декомпозиция полигона в набор треугольников.
Триангуляционная сетка — это совокупность треугольников, которые не пересекаются и создают замкнутый контур. В вершинах треугольников (узлах) могут быть заданы значения любые величины или параметры.

Существует много способов построения триангуляции. Все методы триангуляции по принципу построения можно разбить на две большие группы: прямые методы и итерационные методы.

Если говорить про общие недостатки всех методов, построенных на основе критерия Делоне, то нужно упомянуть крайне высокую чувствительность алгоритма к точности машинных вычислений. Множество вычислительных процедур, используемых в предоставленных методах являются плохо обусловленными задачами, а их неизбежно интенсивное использование так же приводит к накоплению ошибок в округлении. А в результате это может привести к многочисленным ошибкам в структуре сетки или зацикливанию алгоритма.

В реализации этого класса алгоритмов часто допускается одна типичная ошибка. Она заключается в использовании приближенных вычислений и операций. Например: вместо использования для сравнения нуля (x> 0.0) используется заданная точность (x>EPS или x>-EPS). Конечно, данный подход можно считать вполне оправданным и даже верным, но только не в методах на основе критерия Делоне.

К сожалению, простое увеличение точности не дает существенных результатов. Использование числовых типов с удвоенной точностью перестает работать уже на задачах средней сложности (сетки с несколькими тысячами узлов). Частичным решением этой проблемы может быть использование числовых типов с фиксированной запятой. За счет отдельного хранения в 24-байтной структуре целой и десятичной частей числа (в виде целых чисел), на указанных выше плохо обусловленных задачах можно добиться точности вплоть до 10 знака, что уже более-менее допустимым результатом.

Также возможно использование так называемой «точной арифметики», модули для реализации которой уже разработаны для многих популярных прикладных языков программирования (например для С++.). Недостатком обоих подходов есть (весьма существенное) снижение скорости вычислений, поскольку ни точная арифметика, ни числа с фиксированной запятой пока аппаратно не поддерживаются процессорами современных персональных компьютеров. Поэтому все эти операции приходится реализовывать на уровне подпрограмм, что приводит к дополнительным затратам ресурсов.

Изучение применения триангуляционной сетки есть достаточно широко распространено. Она используется и в компьютерной графике, и в медицине, и в сетях связи, и в физике, и в горном деле (геодезия) и даже в философии и религии. Назначение сетки практически во всех областях одно и то же — построение цифровых моделей поверхностей.

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

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.