https://stackoverflow.com/questions/557496
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我在互联网上查找，找不到解决这个特定问题的完美算法：
我们的客户有一组点和每个点的重量数据，如下图所示：
加权点http://chakrit.net/files/stackoverflow/so_heightmap_points.png
其中，我们有一个 GIS 程序，可以根据这些点及其权重值生成“高度图”或某种地形数据，但由于我们有近一千个数据点，并且这些数据会随着时间的推移而变化，我们希望创建我们自己的工具来自动生成这些高度图。
到目前为止，我尝试根据每个像素到最近数据点的距离来计算其权重 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
梯度上升算法不是我的兴趣。我感兴趣的是什么；是首先计算该图片中原始函数的算法，提供带有权重的数据点。
我没有上过任何拓扑数学课，但我会做一些微积分。我想我可能遗漏了一些东西，并且不知道应该在谷歌搜索框中输入什么内容。
我需要一些指点。
谢谢！
解决方案
你所寻找的是曲面插值。
存在一些产品要做到这一点（这里的一个 ）
将得到的功能/花键/其他数学结构然后可以在所要求的分辨率来提供高度地图被询问。
您插值函数
Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
类似于除非你反距离权重方法被施加一个任意滤波和丢弃许多其他数据点。
大多数这些技术依赖于样本的合理数量和'地形状行为支撑该值。
我建议使用重量为高度样本和在所述第二连杆试图简单Shepard的方法通过利用整体高度值的样本点的贡献的比例在一个插补点（不过滤的任何像素到开始）你可以混合样品的颜色的比率也颜色的点。使用强度（粗略地说在简单RGB空间中的灰度）来显示的高度或在黑色加轮廓线像的例子的图像一样。
其他提示
此问题不是因为它看起来在表面上一样简单。你的问题是，两个区域的边界两边需要具有相同的高度，这是说，在给定像素的高度由不止一个近邻确定。
如果我理解正确，需要至少两个算法（以及第三片行话）。
要正确地做到这一点，你需要打破平面成沃罗诺伊镶嵌。
你可能会想使用 kd树来帮助你找到最近的邻居。而不是采取为O（n ^ 2），这将使其下降到O（N日志（N））（额外的好处是，你的Voronoi区生成阶段将是足够快的速度在发展，在高度计算阶段工作）。
现在你有一个2-d地图索引的每个点到其最近的邻居我，需要跨越每x行走，Y点在地图上，并计算其高度。
要做到这一点对于给定的点x，y，第一抓住它的最近邻i和粘，到一个列表中，然后收集维诺图上的所有连续的区域。一个简单的方法是使用洪水填充找到所有点的区域，然后环顾四周边界，并收集了其他标识。
使用所有的最近邻居的这份名单中，你现在在正确地插了一枪！ （参见插值方案其他答案）。
您询问了有关不规则数据二维插值算法的信息，这是一个相当复杂的领域。既然你说你有ArcGIS，我 强烈建议 你来插值 自动地 在 ArcGIS 中使用其内置 特征 用于自动计算。我确信那将会是 容易得多 而不是编写自己的插值算法。我已经完成了ArcGIS的一些自动化，它相当简单。
如果您确实编写了自己的插值代码（我建议您不要这样做），那么第一件事就是选择合适的算法，因为有几种算法各有优缺点。以下是从优秀插值工具的帮助中摘录的一些建议 冲浪者 （顺便说一句，也可以很容易地实现自动化）。还有更多的算法，这些只是我尝试过的。
- 克里金法 是更灵活的方法之一，可用于对几乎任何类型的数据集进行网格化。对于大多数数据集，使用默认线性变异函数的克里金法非常有效。一般来说，我们最常推荐这种方法。克里金法是默认的网格化方法，因为它可以为大多数数据集生成良好的地图。对于较大的数据集，克里金法可能会相当慢。克里金法可以推断超出数据 Z 范围的网格值。
- 反距离加权 速度很快，但倾向于在数据点周围生成同心轮廓的“牛眼”图案。幂距离反比不会推断超出数据范围的 Z 值。简单的反距离加权算法很容易实现，但速度会很慢。
- 线性插值三角测量 速度很快。当您使用小型数据集时，线性插值三角测量会在数据点之间生成不同的三角形面。使用线性插值进行三角测量不会推断超出数据范围的 Z 值。
- 谢泼德法 类似于幂距离反比，但不会生成“牛眼”模式，特别是在使用平滑因子时。 谢泼德方法 可以推断超出数据 Z 范围的值。
实现算法：您可以尝试谷歌搜索，或点击其他一些答案中的链接。有一些开源 GIS 软件包包含插值，因此如果您喜欢通过 C++ 进行探索，也许您可以从中提取算法。或者 这本书 David Watson 的作者显然被认为是经典，尽管它读起来很棘手，而且示例代码是意大利面条式的基本！！但是，据我所知，这是最好的。如果 Stack Overflow 上的其他人更了解，请纠正我，因为我也不敢相信。
是首先在该图片中计算原始功能的算法，并提供了权重的数据点。
这是可能的。如果你从单个点开始，你总是会得到圆形，但如果你对数据点进行加权并考虑到这一点，你可以将圆形压缩成椭圆形，如图所示。
最终得到多边形的原因是您在计算中使用了离散函数 - 首先找到最接近的颜色，然后确定颜色。
相反，您应该研究梯度算法，该算法根据将点包围在三角形中的三个数据点的距离和权重为点分配颜色。
梯度算法
这取决于您想要显示的内容。一个简单的算法是：
对于每个像素：
- 找到围绕该像素形成最小三角形的三个点
将此点设置为受每个数据点的权重和距离影响的颜色（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前一阵子。它使用计算逆的“元球”型方法平方距离（以避免对速度的平方根）从每个数据点，封盖它（例如1.0），并考虑这些距离的总和为在二维网格中的每个点。这将使一个平滑变化的颜色/高度图。
如果你想看看代码，它在从我的
编辑：只是看着它，我增加了一些其他的爵士乐，使它看起来更漂亮，这是最重要的部分是：
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分并不多，但记住我试图让一个320×200格在400MHz机器上的实时运行这个新的时候（这确实在〜20FPS）。 ：）
更换红色=，绿色=和蓝色= ...红色= d线;等等，看看我的意思。所有美貌消失，你还剩下的数据点周围平滑变化的斑点的灰度图像。
另一个编辑：我忘了说的“s”是所有点的共享体重，改变它为每一个给出的权重个体的每个点，例如D1 = 2 /（...）和d2 = 1 /（...）将在其为d2中心得到D1的两倍高度。您可能还需要封顶底部表达的东西，如D1 = 2 / MAX（...，1.0），以平滑掉点的顶部，使它们不会在中间的无限高峰。 ：）
对不起，我回答的混乱...我想张贴代码例子是不够好，但在检查我的代码是混乱和难以阅读。 ：（
我知道这是一个很老的问题，但我碰到它绊倒了，而试图解决同样的问题。
有一个称为一个开源项目 Surfit 实现正是这种类型的功能性。
