Разработка технологии комплексной оценки градостроительной ситуации в среде геоинформационной системы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?руется следующим образом: система взаимосвязанных неперекрывающихся треугольников имеет наименьший периметр, если ни одна из вершин не попадает внутрь ни одной из окружностей, описанных вокруг образованных треугольников (рис. 3).
Образовавшиеся треугольники при такой триангуляции максимально приближаются к равносторонним, а каждая из сторон образовавшихся треугольников из противолежащей вершины видна под максимальным углом из всех возможных точек соответствующей полуплоскости. Интерполяция выполняется по образованным ребрам.
Рисунок 3 - Триангуляция Делоне
.4Обзор методов интерполяции
Интерполяция - восстановление функции на заданном интервале по известным ее значениям конечного множества точек, принадлежащих этому интервалу.
В настоящее время известны десятки методов интерполяции поверхностей, наиболее распространенные из которых мы здесь кратко рассмотрим.
1.4.1 Линейная интерполяция
Этот простой метод основан на априорном утверждении, что каждое последующее число числовой последовательности определяется простым математическим действием. Если это действие известно, то можно восстановить пропущенные значения.
В примере из рис. 4, при предположении, что поверхность меняется линейным образом, как в арифметической прогрессии, четыре числа между 100 и 150 на равных промежутках друг от друга могут быть проинтерполированы как 110, 120, 130, 140, то есть можно создать карту изолиний, позволяющие визуализировать объекты по высоте.
Рисунок 4 - Линейная интерполяция
1.4.2 Метод обратных взвешенных расстояний (ОВР)
Этот метод основан на предположении, что чем ближе друг к другу находятся исходные точки, тем ближе их значения. Для точного описания топографии набор точек, по которым будет осуществляться интерполяция, необходимо выбирать в некоторой окрестности определяемой точки, так как они оказывают наибольшее влияние на ее высоту. Это достигается несколькими приемами поиска, включая определение окрестности на заданном удалении от каждой точки, предварительным заданием числа точек выборки данных или выбором определенного числа точек в квадрантах или октантах (когда, например, для интерполяции используется одна точка из каждого квадранта).
Какой бы метод ни использовался, измеряется расстояние между каждой парой точек и от каждой начальной точки. Затем значение высоты в каждой точке взвешивается в зависимости от квадрата расстояния, так что более близкие точки вносят больший вклад в определение интерполируемой высоты по сравнению с более удаленными (Рис.5). Существуют множество модификаций этого подхода. Одни методы сокращают объем вычислений применением поиска с обучением, другие используют в качестве весового коэффициента вместо второй степени третью или более высокую, третьи учитывают барьеры, представляющие береговую линию, скалы или иные непреодолимые объекты, которые могут воздействовать на результаты интерполяции. Как и при использовании барьеров в других задачах моделирования, процесс интерполяции не может распространяться через барьер.
Рисунок 5 - Интерполяция со взвешиванием по расстоянию. Недостающая величина будет ближе к отметке высоты 350
1.4.3 Метод поверхности тренда (тренд-интерполяция)
В некоторых случаях исследователя интересуют общие тенденции поверхности, которые характеризуются поверхностью тренда.
Аналогично методу обратных взвешенных расстояний для поверхности тренда используется набор точек в пределах заданной окрестности. В пределах каждой окрестности строится поверхность наилучшего приближения на основе математических уравнений, таких как полиномы или сплайны (polynomials, splines). Эти уравнения являются нелинейными зависимостями, которые аппроксимируют кривые или другие формы числовых последовательностей. Чтобы построить поверхность тренда, каждое из значений в окрестности подставляется в уравнение. Из уравнения, использованного для построения поверхности наилучшего приближения, получается одно значение и присваивается интерполируемой точке. Процесс продолжается для других целевых точек; кроме того, поверхность тренда может быть расширена на все покрытие.
Число, присваиваемое целевой ячейке, может быть простым средним всех значений поверхности в окрестности, или оно может быть взвешенным с учетом определенного направления, в котором ориентирован тренд. Поверхности тренда могут быть плоскими, показывая общую тенденцию для всего покрытия, или они могут быть более сложными. Тип используемого уравнения (или степень полинома) определяет величину волнистости поверхности. Чем проще выглядит поверхность тренда, тем меньший порядок, как говорят, оно имеет. Например, поверхность тренда первого порядка будет выглядеть как плоскость, простирающаяся под некоторым углом по всему покрытию, т.е. она имеет тенденцию в одном направлении. Если поверхность имеет один изгиб, то такую поверхность называют поверхностью тренда второго порядка (Рис.6), и т.д.
Рисунок 6 - Поверхности первого, второго и третьего порядка в зависимости от сложности полинома, используемого для представления поверхности
1.4.4 Кригинг
Метод интерполяции, который основан на использовании методов математической статистики. В его реализации применяется идея регионализированной переменной, т.е. переменной, которая изменяется от места к месту с некоторой видимой непрерывностью, поэт