cha*_*rit 16 gis algorithm arcgis geospatial heatmap
我正在环顾互联网,无法找到解决此特定问题的完美算法:
我们的客户有一组点数和重量数据以及每个点,如下图所示:
加权点http://chakrit.net/files/stackoverflow/so_heightmap_points.png
其中,我们有一个GIS程序,可以从这些点和它们的重量值生成"高度图"或一种地形数据但是因为我们有近千个数据点并且这些将随着时间的推移而变化,我们希望创建我们自己的工具来自动生成这些高度图.
到目前为止,我已经尝试计算每个像素从其到最近数据点的Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)距离的权重,并将权重和距离因子应用于数据点的颜色,以生成该特定像素的结果渐变颜色:
heightmap结果http://chakrit.net/files/stackoverflow/so_heightmap_result.png
您可以看到某些数据点配置仍然存在问题,并且当存在大量数据点时,算法有时会生成相当多边形的图像.理想的结果应该看起来更像一个省略号,而不像多边形.
这是维基百科关于渐变上升的文章中的一个示例图像,它展示了我想要的结果:
山http://chakrit.net/files/stackoverflow/so_gradient_descent.png
渐变上升算法不是我感兴趣的.我感兴趣的是什么; 是首先计算该图中原始函数的算法,提供具有权重的数据点.
我没有参加拓扑数学课程,但我可以做一些微积分.我想我可能会遗漏一些东西,而且我宁愿迷失在Google搜索框中输入的内容.
我需要一些指示.
谢谢!
您正在寻找的是Surface Interpolation.
有些产品可以做到这一点(这里是一个)
然后可以以所需的分辨率询问所得的函数/样条/其他数学构造以提供高度图.
你的插值函数
Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
类似于反距离加权 方法,除了您应用任意过滤器并丢弃许多其他数据点.
大多数这些技术依赖于合理数量的样本和支持这些值的"类似地形"的行为.
我建议使用权重作为高度样本并在第二个链接中尝试简单的Shepard方法(不要过滤任何像素开始),方法是将一个样本点贡献的比例与可以混合的插值点的总高度值相比较这些比例中的样本的颜色也使点着色.使用强度(粗略地说简单RGB空间中的灰度)来显示高度或添加黑色轮廓线,如示例图像所示.
这个问题并不像表面上看起来那么容易。您的问题是两个区域的边界两侧需要具有相同的高度，也就是说，给定像素的高度不仅仅由一个最近的邻居决定。
如果我理解正确，你至少需要两种算法（和第三段行话）。
要正确执行此操作，您需要将平面分解为Voronoi 镶嵌。
您可能想要使用kd-tree来帮助您找到最近的邻居。这不是采用 O(n^2)，而是将其降低到 O(n log(n))（额外的好处是您的 Voronoi 区域生成阶段在开发过程中将足够快，可以在高度计算阶段工作）。
现在您有一个二维地图，将每个点索引到其最近的邻居 i，您需要遍历地图上的每个 x,y 点并计算其高度。
要对给定的点 x,y 执行此操作，首先获取其最近的邻居 i 并将其粘贴到列表中，然后收集 Voronoi 图上的所有连续区域。一个简单的方法是使用洪水填充找到该区域中的所有点，然后环顾边界并收集其他身份。
使用所有最近邻居的列表，您现在可以正确地进行插值！（有关插值方案，请参阅其他答案）。