高度图生成算法?

你要找的是曲面插值。

有些产品就是这样做的(这里是 one

然后可以以所需的分辨率查询生成的函数/样条曲线/其他数学构造,以提供高度图。

你的插值函数

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

Inverse Distance Weighted 方法,除非应用任意筛选器并丢弃许多其他数据点。

这些技术中的大多数都依赖于合理数量的样本和支持这些值的“地形”行为。

这个问题不像表面上看起来那么容易。您的问题是,两个区域边界的两侧需要具有相同的高度,也就是说,给定像素处的高度由多个最近邻确定。

如果我理解正确,您至少需要两个算法(和第三个术语)。

要正确执行此操作,您需要将飞机分解为 Voronoi tesselation .

kd-tree 帮你找到最近的邻居。这将不采用O(n^2),而是将其降到O(n log(n))(额外的好处是,Voronoi区域生成阶段的开发速度足够快,可以在高度计算阶段工作)。

现在您已经有了一个二维地图,将每个点索引到其最近的邻居i,您需要遍历地图上的每个x,y点并计算其高度。

要对给定的点x,y执行此操作,首先获取其最近的邻居i并将其粘贴到列表中,然后收集Voronoi图上的所有连续区域。一个简单的方法是使用 flood fill 要找到该区域的所有点,请环顾边界并收集其他身份。

使用所有最近邻居的列表,您现在有机会正确插值!(参见插值方案的其他答案)。

强烈建议 你需要插值吗 automatically 在ArcGIS中使用其内置的 features 用于自动计算。我相信那会很好 容易得多 而不是编写自己的插值算法。我已经完成了一些ArcGIS的自动化,它相当简单。

如果你自己写插值代码-我建议你不要-第一件事是选择合适的算法,因为有几个算法都有各自的优缺点。下面是一些来自于“帮助”的关于优秀插值工具的建议 Surfer (顺便说一句,这也可以很容易地实现自动化)。还有更多的算法,这些就是我尝试过的。

• 是一种更灵活的方法,适用于网格化几乎任何类型的数据集。对于大多数数据集,使用默认线性变异函数的克里金法非常有效。一般来说,我们最常推荐这种方法。克里格法是默认的网格划分方法,因为它可以为大多数数据集生成良好的地图。对于较大的数据集,克里金法可能相当缓慢。克里金法可以将栅格值外推到数据的Z范围之外。
• 反距离权重法
• 线性插值三角剖分 速度很快。使用小数据集时,带线性插值的三角剖分会在数据点之间生成不同的三角形面。使用线性插值的三角测量不会将Z值外推到数据范围之外。
• 谢泼德法 可以外推超出数据Z范围的值。

要实现这些算法:您可以尝试谷歌搜索,或者按照其他答案中的链接进行操作。有一些开源的GIS软件包,包括插值,所以也许你可以从他们提取算法,如果你喜欢通过C++的坑坑洼洼。或 this book 大卫·沃森的作品显然被认为是一部经典之作,尽管这本书读起来很难,而且示例代码是意大利面条基础!!但是,据我所知,这是最好的。如果堆栈溢出上的其他人知道得更好,请纠正我,因为我也不敢相信。

Kriging 是实现这一点的重要方法之一,特别是在GIS领域。它有几个很好的数学性质-缺点是它可能会很慢,这取决于你的 variogram .

如果您想要更简单的东西,有许多插值例程可以很好地处理这个问题。如果你能找到一份 Numerical Recipes ,第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中实现了类似的东西。它使用“metaballs”类型的方法计算每个数据点的平方反比距离(以避免速度的平方反比),将其封顶(例如,至1.0),并为2D网格上的每个点获取这些距离的总和。这将提供平滑变化的颜色/高度图。

如果您想查看代码,它位于我的 J10 AVS pack .

编辑:只是看看它,我添加了一些其他爵士乐,使它看起来更漂亮,最重要的部分是:

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点并不多,但请记住,当它是新的(每秒20帧)时,我正试图在400MHz机器上的320x200网格上实时运行它:)

替换红色=、绿色=和蓝色=。。。红色线=d;等明白我的意思。所有的美丽都消失了,剩下的是数据点周围平滑变化的斑点的灰度图像。

另一个编辑:我忘了说“s”是所有点的共享权重,对每个点更改它会为每个点提供单独的权重,例如d1=2/(…)和d2=1/(…)会使d1在其中心的高度是d2的两倍。你可能还想把底部的表达式用D1=2/max(…,1)来把点的顶点平滑,这样它们就不会在中间无限大。

对不起,答案太混乱了。。。我认为发布代码示例就足够了,但经过检查,我的代码令人困惑,难以阅读(

有一个开源项目叫做 Surfit

你要找的东西 Blender 电话“ metaballs " ( Wikipedia article with links , example ).这样想:

你的物体是伸出地面的圆锥体。它们都是抛物线,重量告诉我们它们离地面有多远。或者,使它们都具有相同的高度,并相应地调整抛物线的“平面度”,以便大重量使圆锥体非常宽,而小重量使其锋利。甚至在某种程度上两者都有可能。

接下来,您需要在结果上挂一块布或橡胶板。布料会有一定程度的拉伸,由于重力的作用,它通常会下垂。圆锥体使它保持在上面。

只要靠近圆锥体的中心,Z坐标就是圆锥体表面上的位置。离开圆锥体中心时,重力开始向下拉,其他圆锥体的影响也会增大。