Триангуляция Делоне
Триангуляция - построение линий уровня
При этом используется алгоритм Делона
Задача аппроксимации функции от трех переменных состоит в следующем – значение функции задано в n произвольным образом расположенных точках и требуется аппроксимировать ее в некоторой новой точке, один из возможных подходов в решении этой задачи – основывается на кусочно-линейной аппроксимации, при которой поверхность определяемая функцией приближается к кусочно-линейной поверхности, состоящей из треугольников. Для этого на плоскости XY создается сеть из непересекающихся треугольников. Процесс триангуляции состоит в создании сети не пересекающихся треугольниках с вершинами в заданных точках. По сравнению с прямоугольной сеткой, триангуляция исходных данных имеют ряд преимуществ
1) Отсутствие единого – произвольно выбранного масштаба, в то время как размер ячейки треугольной сетки автоматически устанавливает предел … и все значения точек будут усредняться до размера ячейки. При триангуляции, в тех местах, где исходные точки разрежены треугольники крупнее, где есть сгущения – мельче. Количество треугольников определяется количеством исходных точек по теореме Эйлера, ноне превышает удвоенного числа исходных точек.
2) У прямоугольной сетки есть два выделенных направления, ни как не согласованных с начальными данными, поэтому при ее построении требовать точности аппроксимации при повороте решетки на любой угол не приходится. Для адекватного отображения сильно меняющейся поверхности приходится значительно измельчать сетку, что требует больших затрат и ведет к образованию неустойчивости, при триангуляции этого нет, в то же время за преимуществ триангуляции приходится платить сложностью программирования, для определения качества триангуляции известно несколько критериев, которые выбираются исходя из ошибки интерполяции. На практике может возникнуть потребность минимизировать … (минимальная взвешенная триангуляция), жадная триангуляции – никогда не отменяется то, что было сделано задано, последовательно порождаются ребра и процесс завершается после того как порождено необходимое число ребер. В настоящее время в большинстве случаем используется триангуляция Делоне. Она строится однозначно и соединяет исходные точки в сеть наиболее правильных треугольников, что удобно в расчетах.
|
|
|
Для множества точек S на плоскости, называют триангуляцию DT, такую что ни какая точка A из множества S не содержится внутри окружности, описанной внутри любого треугольника из DT, такого, что ни одной из вершин его не является точка A. Свойства триангуляции Делоне – минимизируют минимальный радиус окружности, обладает минимальной суммой радиусов окружностей описанных около треугольников среди всех возможных триангуляций. Максимизирует минимальный угол среди всех углов, всех построенных треугольников, тем самым избегаются тонкие треугольники.
|
|
|
Дата добавления: 2015-12-17; просмотров: 22; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!