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

Question

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

В любом случае, на данный момент, у меня есть «непрерывный» цвет средства визуализации, что я очень доволен:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Edit:

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

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

UPDATE:

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

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

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

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

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

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

---

UPDATE РАЗ:

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

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

Bon appetit !!

Answer 1

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

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

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

Я предлагаю

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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

где дх и ду может быть расстояние в сетке. Контурная линия будет работать перпендикулярно градиенту. Таким образом, чтобы получить направление контура, с, мы можем умножить г = [V, W] матрицей А = [0 -1, 1 0] дает

c = [-w,v] 

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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

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