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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Edit:

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

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

UPDATE:

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

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

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

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

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

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

ОБНОВЛЕНИЕ:

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

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

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

Ответ 1

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

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

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

Я предлагаю

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

Ответ 2

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

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

Ответ 3

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

С учетом точки [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]

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

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