Алгоритм поколения Heightmap?

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

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

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

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

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

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

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

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

, Если Вы хотите что-то более простое, существует много процедур интерполяции, которые обрабатывают это вполне хорошо. Если можно схватить копии Числовые Рецепты , Глава 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

я использую + здесь, но необходимо определить алгоритм 'усреднения', подходящий для приложения.

-Adam

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

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

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

Для реализации алгоритмов: можно попытаться гуглить или перейти по ссылкам в некоторых из других ответов. Существуют некоторые пакеты GIS с открытым исходным кодом, которые включают интерполяцию, поэтому возможно, можно извлечь алгоритмы от них, если Вам нравится спелеология через C++. Или эту книгу David Watson, по-видимому, считают классиком, хотя это - хитрое чтение, и пример кода является Основными спагетти!! Но, от того, что я слышу, это - наилучшее имеющееся. Если кто-либо еще на Переполнении стека знает лучше, исправьте меня, поскольку я не могу верить этому также.

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

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

Это настоящий метод решения "в лоб", но это просто.

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

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

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

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

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

I implemented something like this in Winamp AVS a while ago. It uses a "metaballs" type approach of calculating the inverse squared distance (to avoid the sqrt for speed) from each data point, capping it (e.g. to 1.0), and taking a sum of those distances for each point on the 2D grid. This will give a smoothly varying colour/height map.

If you want to look at the code, its in the "Glowy" preset from my J10 AVS pack.

EDIT: Just looking at it I added some other jazz to make it look prettier, the part that is most important is:

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;

Which takes the sum for the 6 points. Everything else done to the red, green and blue output values is to make it look prettier. 6 points isn't much but bear in mind I was trying to make this run in real-time on a 320x200 grid on a 400MHz machine when it was new (which it does at ~20fps). :)

Replace the red =, green = and blue = ... lines with red = d; etc... to see what I mean. All the prettiness goes away and you are left with a greyscale image of smoothly varying blobs around the data points.

Another edit: I forgot to say "s" is the shared weight for all of the points, changing it for each one gives weights individual to each point, e.g. d1 = 2/(...) and d2 = 1/(...) would give d1 twice as much height at its centre as d2. You might also want to cap the expression at the bottom with something like d1 = 2/max(..., 1.0) to smooth off the tops of the points so that they don't peak at infinity in the middle. :)

Sorry for the messiness of the answer... I thought posting the code example would be good enough but on inspection my code is confusing and difficult to read. :(

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

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