Подтвердить что ты не робот

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

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

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

взвешенные точки 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.

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

Спасибо!

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

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

Чтобы сделать это правильно, вам нужно сломать плоскость в Voronoi tesselation.

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Алгоритм градиента

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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 кадров в секунду).:)

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

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