Цифровая модель рельефа (ЦМР)

Исходные данные: набор точек , , расположенных нерегулярно, тогда надо строить интерполяционную (иногда экстраполяционную) поверхность , .

Отображение – упорядоченный набор точек  , т.к. поверхность может быть построена по какому то критерию. Обычно строят кривые по данным точкам изначально сплайнами или интерполяционно. Берем вместо  полином  Лагранжа:

Он проходит через все точки набора.

Недостатки:

1. Значение высоты в заданной точке зависит от всех остальных точек, то есть нет локальности;

2. Плохо удалять и добавлять точки, так как это приводит к перестройке всего многочлена.

2. Долго вычислять.

Достоинство: прост в построении.

Рассмотрим модели рельефа:

Существует два способа построения :

------Билет 13. GRID-модель рельефа. Алгоритмы построения GRID-моделей ------

GRID- модели – модели регулярных ячеек.

Пусть введена система координат  и  и . Пользователь задает  и шаги дискретизации .

     ,

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

Вычисляем  и ,  - разрядная сетка.

 - квантованные значения. Реальные:

- параметр алгоритма – количество точек,  - вес. Чем ближе точка, тем больше вес.

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

Нормировочный коэффициент:

Чем  ближе к 1, тем больше учитываются точки с большим весом.

Это метод IDW – долгий, для каждой т. необходимо найти соседей. Набор соседей     может быть эффективно найден - ближайшим. Каждая из точек продуцирует «колышек» определенной высоты. От нерегулярности постановок точки многое зависит, для этого берут  или  т.е. разделяют на сектора и в окрестности точки строим.

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

Недостаток:

1) На значение высоты влияет набор точек. Чтобы этого избежать, матрицу разбивают на сектора и вводят коэффициенты  или

2)  – локальные экстремумы построенной функции.

------Билет 14. TIN-модель. Алгоритмы триангуляции Делоне ------

Триангуляционные (TIN).

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

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

Триангуляция – планарный граф, все внутренние ребра которого – треугольники; способ представления пространства в виде примыкающих друг к другу треугольников без перекрытий. На наборе точек триангуляция строится несколькими способами.

Нужен алгоритм для построения оптимальной триангуляции.

Плоскость, проходящая через 3 точки.

1) Найдем треугольник, который ;

2)  - строим уравнение плоскости.

Чтобы проверить находятся ли точки внутри треугольника или нет, необходимо подставить значение в уравнение линий – ребер треугольника. Если все 3 уравнения > 0, то внутри.

Структура представления:

Каждая триангуляция содержит одинаковое количество треугольников.

, где  – количество внутренних точек,  – количество точек.

Жадный триангуляция.

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

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

 Внутрь окружности, описанной вокруг любого треугольника, не попадают точки других треугольников. Строится единственным образом.

Флипом называется переброска ребер. Она позволяет перейти от обычной триангуляции к триангуляции Делоне. Чтобы проверить принадлежность точки к окружности: подставить, если  < R, то внутри.

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

Уравнение окружности, проходящей через три точки:

Если меньше нуля, то внешняя, иначе – внутренняя.

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

Алгоритм построения триангуляции Делоне:

1) Подследственного добавления точек – простой итеративный алгоритм:

Есть набор  добавляем в треугольник, осуществляется построение  разбиение треугольника  перестроение. На нулевом этапе добавляем 3-4 фиктивные точки, которые заведомо покрывают наш конверт, все точки внутри. После кидаем точку, смотрим в какой треугольник попала, разбиваем на 3, для каждого треугольника проверяем условие Делоне и осуществляем флип переброску ребер. Среднее количество перестроений равно трем.

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

2) Методы ускорения. Основан на статистически зависимых точках. Затравочный треугольник – треугольник в который попала предыдущая точка. Затем соединяем две точки – предыдущую и новую.

Перемещаемся из первой точки в другую.