Алгоритм создания карты высот?

StackOverflow https://stackoverflow.com/questions/557496

Вопрос

Я искал в Интернете и не смог найти идеальный алгоритм для этой конкретной задачи:

У нашего клиента есть набор точек и данные о весе для каждой точки, что можно продемонстрировать на этом изображении:

взвешенные точки http://chakrit.net/files/stackoverflow/so_heightmap_points.png

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

До сих пор я пытался вычислить вес каждого пикселя исходя из его расстояния до ближайшей точки данных с помощью Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) и применяя коэффициент веса и расстояния к цвету точки данных, чтобы получить результирующий цвет градиента для этого конкретного пикселя:

результат карты высот http://chakrit.net/files/stackoverflow/so_heightmap_result.png

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

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

горы http://chakrit.net/files/stackoverflow/so_gradient_descent.png

Алгоритм градиентного подъема меня не интересует.Что меня интересует;— это алгоритм для вычисления исходной функции на этом изображении в первую очередь с учетом точек данных с весами.

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

Мне нужны некоторые указатели.

Спасибо!

Это было полезно?

Решение

То, что вы ищете, — это поверхностная интерполяция.

Для этого существуют некоторые продукты (вот один)

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

Ваша функция интерполяции 

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)

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

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

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

Другие советы

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

Если я правильно понимаю, нужно как минимум два алгоритма (и третий жаргонизм).

Чтобы сделать это правильно, нужно разбить самолет на Мозаика Вороного.

Вероятно, вы захотите использовать kd-дерево чтобы помочь вам найти ближайшего соседа.Вместо того, чтобы брать O(n^2), это снизит его до O(n log(n)) (дополнительным преимуществом является то, что ваша фаза генерации региона Вороного будет достаточно быстрой в разработке, чтобы работать на этапе расчета высоты).

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

Чтобы сделать это для данной точки x,y, сначала возьмите ее ближайшего соседа i и вставьте его в список, затем соберите все смежные области на диаграмме Вороного.Простой способ — использовать заливка чтобы найти все точки региона, затем осмотрите границу и соберите другие личности.

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

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

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

  • Кригинг Это один из наиболее гибких методов, который полезен для построения сетки практически любого типа набора данных.Для большинства наборов данных достаточно эффективен кригинг с линейной вариограммой по умолчанию.В общем, мы чаще всего рекомендуем именно этот метод.Кригинг — это метод построения сетки по умолчанию, поскольку он создает хорошую карту для большинства наборов данных.Для больших наборов данных кригинг может быть довольно медленным.Кригинг может экстраполировать значения сетки за пределы диапазона Z ваших данных.
  • Обратное взвешивание расстояния работает быстро, но имеет тенденцию генерировать шаблоны «бычий глаз» из концентрических контуров вокруг точек данных.Функция «Обратное расстояние до степени» не экстраполирует значения Z за пределы диапазона данных.Простой алгоритм взвешивания обратного расстояния легко реализовать, но он будет медленным.
  • Триангуляция с линейной интерполяцией быстро.Когда вы используете небольшие наборы данных, триангуляция с линейной интерполяцией создает отдельные треугольные грани между точками данных.Триангуляция с линейной интерполяцией не экстраполирует значения Z за пределы диапазона данных.
  • Метод Шепарда аналогичен методу «Обратное расстояние к степени», но не имеет тенденции к созданию моделей «бычий глаз», особенно при использовании коэффициента сглаживания. Метод Шепарда может экстраполировать значения за пределы диапазона Z ваших данных.

Для реализации алгоритмов:вы можете попробовать Google или перейти по ссылкам в некоторых других ответах.Существуют некоторые ГИС-пакеты с открытым исходным кодом, которые включают интерполяцию, так что, возможно, вы сможете извлечь из них алгоритмы, если вам нравится копаться в C++.Или эта книга Дэвида Уотсона, по-видимому, считается классикой, хотя ее сложно читать, а пример кода - спагетти Basic!Но, насколько я слышал, это лучшее, что есть на свете.Если кто-то еще из Stack Overflow знает лучше, поправьте меня, потому что я тоже не могу в это поверить.

Кригинг является одним из сложных методов достижения этой цели, особенно в области ГИС.У него есть несколько хороших математических свойств, но недостатком является то, что он может работать медленно, в зависимости от ваших возможностей. вариограмма.

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

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

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

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

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

Градиентный алгоритм

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

Для каждого пикселя:

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

  • Установите для этой точки цвет (система цвета HSV), на который влияет как вес, так и расстояние до каждой точки данных:

    pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

Здесь я использую +, но вам нужно определить алгоритм «усреднения», подходящий для вашего приложения.

-Адам

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

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

Пример весовой функции:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

Это довольно грубый подход, но он простой.

Некоторое время назад я реализовал что-то подобное в Winamp AVS.Он использует подход типа «метаболлы» для расчета обратного квадрата расстояния (чтобы избежать sqrt для скорости) от каждой точки данных, ограничивая его (например,до 1,0) и взяв сумму этих расстояний для каждой точки двумерной сетки.Это даст плавно меняющуюся карту цвета/высоты.

Если вы хотите посмотреть на код, то он в пресете «Glowy» из моего Пакет J10 AVS.

РЕДАКТИРОВАТЬ:Просто глядя на это, я добавил немного другого джаза, чтобы оно выглядело красивее, самая важная часть:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

Что берет сумму за 6 очков.Все остальное, что делается с выходными значениями красного, зеленого и синего, сделано для того, чтобы они выглядели красивее.6 баллов — это немного, но имейте в виду, что я пытался выполнить этот запуск в реальном времени на сетке 320x200 на машине с частотой 400 МГц, когда она была новой (что и происходит со скоростью ~ 20 кадров в секунду).:)

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

Еще одно редактирование:Я забыл сказать, что «s» — это общий вес для всех точек, изменение его для каждой дает индивидуальный вес для каждой точки, например.d1 = 2/(...) и d2 = 1/(...) дадут d1 в два раза большую высоту в центре, чем d2.Вы также можете захотеть ограничить выражение внизу чем-то вроде d1 = 2/max(..., 1.0), чтобы сгладить верхние точки, чтобы они не достигали бесконечности в середине.:)

Извините за сумбурность ответа...Я думал, что опубликовать пример кода будет достаточно, но при проверке мой код оказался запутанным и трудным для чтения.:(

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

Есть проект с открытым исходным кодом под названием Серфит который реализует именно этот тип функциональности.

Вы ищете что-то, что Блендер звонит "метаболы" (Статья в Википедии со ссылками, пример).Подумайте об этом так:

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

Предлагаю вам реализовать это и посмотреть, как это будет выглядеть.

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

Пока вы находитесь близко к центру конуса, координата Z — это просто положение на поверхности конуса.Когда вы покидаете центр конуса, гравитация начинает снижаться и влияние других конусов возрастает.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top