Введение
Возникла однажды интересная задача: организовать возможность работы программы с трехмерными изображениями земной поверхности больших размеров. После изучения множества литературы и различных источников, стало ясно, что эффективных подходов в общем доступе не найти.
Есть либо сложная математика, которую еще надо адекватно перенести на исходный код, либо закрытые коммерческие продукты. Игровые алгоритмы для этой задачи подходят мало, потому что требуется высокая точность и достоверность получаемых результатов.
Задача
Иметь возможность получить высоту в любой точке, имея две координаты:
h=f(x, y);
Координаты могут быть как географическими, так и линейными. Иметь возможность получать высоты с любым шагом координат в пределах машинной точности. Размеры карт от нескольких сотен километров, до тысяч, вплоть до всей земли. Операция получения высоты должна иметь сложность О(1) и выполнятся достаточно быстро для работы графического движка.
Исходные данные
Карты поставляются в различных форматах, поэтому выполнялась предварительная обработка. После обработки имеется карта изолиний (неравномерная сетка) земной поверхности в унифицированном формате:
<Количество точек> <Высота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
<Количество точек> <Высота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
<Широта> <Долгота>
…
Или в цифрах:
3 0.000000
32.071945 69.587814
32.074299 69.586975
32.070995 69.585907
4 0.000000
32.063576 69.578514
32.062050 69.578270
32.059124 69.578407
32.057785 69.579376
Изолинии могут быть замкнутыми и состоять из отдельных линий. Пересечения изолиний не допускаются, хотя используемый подход обработает и неверные данные. Также в большом количестве имеются одиночные точки высоты.
Содержание работы
Всю работу решено было разбить на три этапа: подготовка данных, получение равномерной сетки, получение аналитической поверхности с использованием сплайн-интерполяции.
В первой части необходимо увеличить разрешающую способность предоставленных данных, чтобы избежать потерь при преобразованиях. Представьте себе ситуацию, когда у вас есть точки, некоторые из них связаны линией. Эта линия гарантирует, что вдоль нее высота постоянна
Во второй части неравномерная сетка преобразуется в равномерную с требуемым разрешением.
Завершает работу этап создания сплайновой поверхности из равномерной сетки, вычисление коэффициентов, поправочных значений.
На каждом этапе встречаются свои проблемы и особенности. Все они будут расписаны в соответствующих разделах.
Часть 1. Подготовка данных
Введение
Все карты поставляются с некоторым масштабом. Этот параметр напрямую влияет на количество деталей, которые есть возможность получить (пространственный аналог теоремы Шеннона-Котельникова). От правильности подготовки данных будет зависеть качество всей работы.
Содержание работы
Часть 1. Подготовка данных
Часть 2. Генерация равномерной сетки
Часть 3. Создание аналитической поверхности
Цель подзадачи
Определить максимально эффективную детализацию неравномерной сетки, для сохранения деталей.
Алгоритмы
В данной части применяется достаточно простой подход к обработке данных. Предположим, в некоторой части карты у нас встречается несколько точек. Одни соединены и представляют изолинию. И еще одна точка расположена близко к изолинии, но имеет сильный перепад по высоте с ней. При простой обработке точек, после интерполяции часть изолинии изменит свою высоту на нечто среднее, между двумя высотами (Рисунок 1). Как Вы думаете, какая высота будет в точке, помеченной вопросительным знаком? Чтобы избежать искажений при перепадах высот, необходимо увеличить количество точек на изолинии.
Рисунок 1. Начальные данные.
Оптимальным вариантом является задание разрешения равномерной сетки на данном этапе. В этом случае можно контролировать качество генерируемой поверхности. Поэтому зададим разрешение сетки и дополним все изолинии точками по некоторому алгоритму, чтобы все точки изолиний стали неразрывными.
Самый простой способ: линейная интерполяция. Просто добавляем точки в изолинию по алгоритму Брезенхема или подобному.
Немного сложнее и требовательнее к ресурсам ЭВМ сплайн интерполяция на плоскости. Мы использовали кубическую интерполяцию. Очень важно использовать именно интерполяционные алгоритмы (новые элементы содержат все заданные точки), аппроксимация (новые элементы приближены к изначальным точкам) в данном случае будет лишь искажать данные. При высоком качестве исходных данных, даже линейная интерполяция дает прекрасные результаты.
Результаты обработки
После обработки неравномерной сетки ее размер на диске возрастает, где то в 3-5 раз, в зависимости от качества данных. Графически результат выглядит так:
Рисунок 2. Линейная интерполяция.
Рисунок 3. Сплайн интерполяция c некоторым шагом.
При использовании сплайн интерполяции (Рисунок 3), линия получается не прямой, так как принимается во внимание информация о положении крайних точек.
Выводы
После предварительной обработки неравномерной сетки можно перейти ко второму этапу работы — созданию равномерной сетки высокой детализации. Видно, сколько различных данных необходимо обработать, чтобы получить результат. Возможно применение различных алгоритмов, для получения высококачественных данных.
В следующей части будет приведен интересный, весьма качественный и простой алгоритм получения равномерной сетки, который прекрасно себя показал на больших объемах данных.
