Алгоритм генерации карты высот?

Question

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

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

взвешенные баллы 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.

Мне нужно несколько указателей.

Спасибо!

Answer 1

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

Некоторые продукты существуют для этого (вот one )

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

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

• Установите эту точку для цвета (цветовая система 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

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

-Adam

Answer 6

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

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

Answer 7

Я реализовал нечто подобное в Winamp AVS некоторое время назад. Он использует подход типа «метабол» для вычисления обратного квадрата расстояния (чтобы избежать квадрата по скорости) от каждой точки данных, его ограничения (например, до 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), чтобы сгладить вершины точек, чтобы они не достигали пика на бесконечности в середине. :)

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

Answer 8

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

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))

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

Answer 9

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

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

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

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

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