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

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

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

,

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

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

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

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

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

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

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

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

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

Недостаток:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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