Триангуляция Делоне Пусть задано множество A точек на плоскости Для каждой точки определена высота f(p) Как наиболее естественно аппроксимировать высоты точек не из A ? Такая задача возникает, например, при построении графиков функций, генерации сложных ландшафтов. Возможное решение этой проблемы состоит в дискретизации: для всех точек не из A пусть f(p) равняется высоте ближайшей точки из A. Получится нечто вроде нарисованного справа. Выглядит довольно неестественно... Гораздо лучше воспользоваться триангуляцией данного набора точек, а потом поднять каждую точку на высоту, соответствующую ее положению в треугольнике. Формальное определение триангуляции: планарный граф, получающийся при соединении точек A отрезками, такой, что нельзя добавить ни одного нового отрезка без нарушения планарности (т.е без пересечения отрезками друг друга). При этом граница триангуляции будет, очевидно, выпуклой оболочкой множества A. Одно и то же множество можно триангулировать разными способами. Рассмотрим углы в получающихся треугольниках. Выберем минимальный угол. Триангуляция дает тем лучшую аппроксимацию, чем больше ее минимальный угол, при этом формируемые треугольники 'стремятся к равноугольности'. Особенно важна максимизация минимального угла в задачах вычислительной математики, когда точность производимых вычислений очень сильно зависит от размера минимального угла триангуляции графика. Наилучшей в этом смысле триангуляцией является триангуляция Делоне. Простейшим способом ее построения является инкрементальный алгоритм, работающий за O(n2) операций. Реализация из соответствующей статьи не поддерживает вырожденные случаи, когда 4 точки из множества лежат на одной окружности: в этом случае триангуляция Делоне не уникальна, их несколько, но минимальные углы этих триангуляций равны. Иногда даже минимальный угол триангуляции Делоне оказывается слишком малым для устойчивой работы использующего ее алгоритма. Тогда ее можно улучшить, используя метод Раперта. При этом будут добавлены новые вершины триангуляции и образованы дополнительные треугольники, но их количество невелико, а стабильность алгоритма (метода конечных элементов, например) может возрасти многократно за счет появления нижней границы для углов. Обычно рассматривают триангуляцию на плоскости, однако триангуляция Делоне аналогично определяется и для n-мерного пространства.  8  Комментарии к статье  8 8  Обсудить в чате