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

Question

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Редактировать:

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

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

Обновить:

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

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

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

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

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

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

---

ОБНОВИТЕ ЕЩЕ РАЗ:

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

В ответ на ваш комментарий к @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, 10], что дает

c = [-w,v]

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

Answer 9

Я рекомендую ПОДТВЕРЖДЕНИЕ подход:

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

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