Рисование топографической карты

Question

Я работал над проектом визуализации для двумерных непрерывных данных. Это та вещь, которую вы можете использовать для изучения данных высот или температурных схем на 2D-карте. По сути, это действительно способ слияния 3-х измерений в 2-х мерный плюс цвет. В моей конкретной области исследований я не работаю с географическими данными о высоте, но это хорошая метафора, поэтому я буду придерживаться ее в этом посте.

Во всяком случае, на данный момент, у меня есть рендерер "с непрерывным цветом", которым я очень доволен:

Градиент - это стандартное цветовое колесо, где красные пиксели указывают координаты с высокими значениями, а фиолетовые пиксели указывают низкие значения.

Базовая структура данных использует некоторые очень умные (если я сам так говорю) алгоритмы интерполяции для обеспечения сколь угодно глубокого увеличения деталей карты.

Сейчас я хочу нарисовать некоторые топографические контурные линии (используя квадратные кривые Безье), но мне не удалось найти хорошую литературу, описывающую эффективные алгоритмы для нахождения этих кривых.

Чтобы дать вам представление о том, о чем я думаю, вот реализация бедного человека (где средство визуализации просто использует значение черного RGB всякий раз, когда сталкивается с пикселем, который пересекает линию контура):

Однако у этого подхода есть несколько проблем:

• Области графика с более крутым наклоном приводят к более тонким (и часто ломаным) линиям топо. В идеале все линии топо должны быть непрерывными.

• Области графика с более плоским наклоном приводят к более широким топографическим линиям (и часто целым областям черноты, особенно по внешнему периметру области рендеринга).

Итак, я смотрю на векторную графику для получения этих прекрасных, идеальных кривых толщиной 1 пиксель. Базовая структура алгоритма должна будет включать в себя следующие этапы:

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

2. Устранить лишние точки. Например, если три точки находятся на совершенно прямой линии, то центральная точка является избыточной, поскольку ее можно устранить, не меняя форму кривой. Аналогичным образом, с помощью кривых Безье часто можно устранить определенные точки привязки, отрегулировав положение соседних контрольных точек.

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

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

5. Убедитесь, что все элементы топографии, видимые в текущем масштабе рендеринга, представлены соответствующими линиями топо. Например, если данные содержат всплеск с большой высотой, но с очень маленьким диаметром, линии топо все равно должны быть нарисованы. Вертикальные элементы следует игнорировать, только если их диаметр меньше общей детализации рендеринга изображения.

Но даже при этих ограничениях я все еще могу думать о нескольких различных эвристиках для нахождения линий:

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

• Выполните обход с высоким разрешением вдоль прямоугольной ограничительной рамки области рендеринга. На каждом пороговом уровне возвышения (и в точках перегиба, где наклон меняет направление), добавьте эти точки в определенную высоту. После завершения обхода границы начните трассировку внутрь от граничных точек в этих сегментах.

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

Итак, вот некоторые из моих мыслей ...

Прежде чем углубиться в реализацию, я хотел узнать, имеет ли кто-либо еще в StackOverflow опыт работы с такого рода проблемами и может ли предоставить указатели для точной и эффективной реализации.

Edit:

Меня особенно интересует предложение "Градиент", сделанное Эллисббеном. И моя основная структура данных (без учета некоторых оптимизирующих ярлыков интерполяции) может быть представлена ​​в виде суммирования набора двумерных гауссовских функций, которые полностью дифференцируемы.

Полагаю, мне понадобится структура данных для представления трехмерного наклона и функция для вычисления этого вектора наклона в произвольной точке. Вдобавок ко всему, я не знаю, как это сделать (хотя кажется, что это должно быть легко), но если у вас есть ссылка, объясняющая математику, я был бы очень признателен!

UPDATE:

Благодаря превосходному вкладу Эллисббена и Азима, теперь я могу рассчитать угол контура для любой произвольной точки в поле. Рисование настоящих линий топо будет в ближайшее время!

Вот обновленные визуализации, с использованием и без использования топо-рендерера на основе гетто, который я использовал. Каждое изображение включает в себя тысячи случайных точек выборки, представленных красными точками. Угол контура в этой точке представлен белой линией. В некоторых случаях нельзя измерить наклон в данной точке (основываясь на гранулярности интерполяции), поэтому красная точка появляется без соответствующей линии угла контура.

Наслаждайтесь!

(ПРИМЕЧАНИЕ. В этих визуализациях используется топография поверхности, отличная от предыдущих визуализаций - поскольку я случайным образом генерирую структуры данных на каждой итерации, пока я создаю прототип, - но основной метод визуализации одинаков, поэтому Я уверен, что вы поняли.)

Вот забавный факт: на правой стороне этих визуализаций вы увидите кучу странных контурных линий под идеальными горизонтальными и вертикальными углами. Это артефакты процесса интерполяции, в котором используется сетка интерполяторов, чтобы уменьшить количество вычислений (примерно на 500%), необходимых для выполнения операций рендеринга ядра. Все эти странные контурные линии происходят на границе между двумя ячейками интерполяционной сетки.

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

---

ОБНОВЛЕНИЕ СНОВА:

А-а-а-а-а-а, в качестве еще одной снисходительности перед сном, вот еще одна пара визуализаций, одна в стиле "непрерывного цвета" старой школы и одна с 20 000 градиентных выборок. В этом наборе визуализаций я убрал красную точку для точечных образцов, так как она излишне загромождает изображение.

Здесь вы действительно можете увидеть те артефакты интерполяции, о которых я упоминал ранее, благодаря сеточной структуре коллекции интерполяторов. Я должен подчеркнуть, что эти артефакты будут полностью невидимы при окончательном рендеринге контура (поскольку разница в величине между любыми двумя соседними ячейками интерполятора меньше, чем битовая глубина визуализированного изображения).

Приятного аппетита !!

Answer 1

Градиент - это математический оператор, который может вам помочь.

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

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

Я бы предложил

1. выбрать значения высоты, при которых вы будете рисовать линии
2. создайте группу точек на тонкой, равномерно распределенной сетке, затем шагните каждой точкой небольшими шагами в направлении градиента к ближайшей высоте, на которой вы хотите нарисовать линию
3. создавать кривые, шагая каждую точку перпендикулярно градиенту; Устраните лишние точки, убив точку, когда другая кривая подходит слишком близко к ней, но чтобы избежать разрушения центра песочных часов, подобных фигурам, вам может понадобиться проверить угол между ориентированным вектором, перпендикулярным градиенту для обеих точек. (Когда я говорю «ориентированный», я имею в виду, что угол между градиентом и перпендикулярным значением, которое вы вычисляете, всегда составляет 90 градусов в одном направлении.)

Answer 2

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

Учитывая точку [x, y] на вашем изображении, вы можете рассчитать градиент (направление наибольших прицелов)

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy) 

где dx и dy могут быть интервалами в вашей сетке. Контурная линия будет проходить перпендикулярно градиенту. Таким образом, чтобы получить направление контура, c, мы можем умножить g = [v, w] на матрицу, A = [0 -1, 1 0], давая

c = [-w,v]

Answer 3

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

Кривые топо, которые вы хотите нарисовать, представляют собой изоповерхности скалярного поля в двух измерениях. Для изоповерхностей в 3-х измерениях используется алгоритм марширующие кубики .

Answer 4

Я сам хотел что-то подобное, но не нашел векторное решение.

Растровое решение не так уж и плохо, особенно если ваши данные основаны на растре. Если ваши данные тоже основаны на векторах (другими словами, у вас есть 3D-модель вашей поверхности), вы должны быть в состоянии выполнить некоторые математические вычисления, чтобы найти кривые пересечения с горизонтальными плоскостями на разных высотах.

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

Может быть, некоторые примеры помогут. Предположим, что текущий пиксель находится на отметке 12 футов, соседний - на отметке 8 футов, а контурные линии - каждые 10 футов. Затем между линиями есть контурная линия; закрасьте текущий пиксель цветом линии контура с непрозрачностью 50%. Другой пиксель находится на 11 футах, а сосед - на 6 футах. Цвет текущего пикселя с непрозрачностью 80%.

alpha = (contour - neighbor) / (current - neighbor)

К сожалению, у меня нет удобного кода, и, возможно, в нем было что-то большее (я смутно припоминаю, что я тоже смотрел на диагональных соседей и корректировал sqrt(2) / 2). Я надеюсь, что этого достаточно, чтобы дать вам суть.

Answer 5

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

К счастью, GNU Octave, клон MATLAB, имеет реализации различных функций построения контуров. Вы можете посмотреть на этот код для алгоритма и реализации, которые почти наверняка математически обоснованы. Или вы можете просто перенести обработку в Octave. Посетите страницу , взаимодействующую с другими языками , чтобы узнать, будет ли это проще.

Раскрытие информации: я не очень часто использовал Octave, и я на самом деле не тестировал его контурное построение. Однако, исходя из моего опыта работы с MATLAB, я могу сказать, что он даст вам практически все, о чем вы просите, всего за несколько строк кода, при условии, что вы перенесете свои данные в MATLAB.

Кроме того, поздравляю вас с созданием очень крутого участка на склоне VanGough-esque.

Answer 6

Я рекомендую CONREC подход:

• Создать пустой список сегментов линии
• Разделите ваши данные на обычные квадраты сетки
• Для каждого квадрата сетки разбейте квадрат на 4 составляющих треугольника:
  • Для каждого треугольника обрабатывать случаи (от a до j):
    • Если отрезок пересекает один из случаев:
      • Рассчитать его конечные точки
      • Сохранить сегмент линии в списке
• Нарисуйте каждый сегмент линии в списке сегментов линии

Если линии слишком неровные, используйте меньшую сетку. Если линии достаточно гладкие и алгоритм занимает слишком много времени, используйте большую сетку.

Answer 7

Запишите данные в виде файла HGT (очень простой цифровой формат данных высот, используемый USGS) и используйте бесплатный инструмент с открытым исходным кодом gdal_contour для создания контуров. Это очень хорошо работает для наземных карт, ограничение состоит в том, что точки данных имеют подписанные 16-битные числа, что очень хорошо соответствует земному диапазону высот в метрах, но может оказаться недостаточным для ваших данных, которые, как я предполагаю, не являются карта реальной местности - хотя вы упоминаете карты местности.

Answer 8

сравните то, что вы сделали с реальной топографической картой - они выглядят одинаково для меня! я бы ничего не изменил ...

Answer 9

Я всегда проверяю такие места, как http://mathworld.wolfram.com, прежде чем углубляться самостоятельно:)

Может быть, их кривые раздел поможет? Или, может быть, запись на карты .