从等高线生成高程图的算法是什么类型？

Question

4

我希望您能翻译以下内容：

我希望对一些等高线进行插值，以生成3D视图。这些等高线并未存储在图片中，每个等高线上的每个点的坐标仅存储在std::vector中。

对于凸等高线：

enter image description here

据我所知（我没有亲自验证），通过使用两个最接近轮廓的最近点之间的距离，可以轻松地计算高度（线性插值）。

我的轮廓不一定是凸形的：

enter image description here

所以这更加棘手......实际上我不知道可以使用哪种算法。

更新：2013年11月26日

我完成了一个离散拉普拉斯例子的编写：

enter image description here

你可以在这里获取代码

- The Unholy Metal Machine

你能发布一张截图展示你的二维轮廓是什么样子吗？ - Nils Pipenbrinck

@NilsPipenbrinck 完成了，实际上我正在使用这些简单的轮廓。 - The Unholy Metal Machine

2个回答

2

您可以生成描述轮廓的顶点和线段的约束德劳内三角剖分，然后使用在每个顶点定义的高度作为Z坐标。生成的三角剖分然后可以像任何其他三角形网格一样渲染。

尽管名称如此，您可以使用TetGen生成三角剖分，但需要进行一些设置工作。

- defube

我还不确定这是否好用，我的第一个想法是使用网格，然后通过使用轮廓计算每个节点的高度。我将尝试使用tetgen并查看结果。 - The Unholy Metal Machine

我将尝试实现Ilmari Karonen的解决方案。无论如何，感谢TetGen链接，它将来也许对我有用。 - The Unholy Metal Machine

祝你好運！直接解Laplacian是一個棘手的問題，不過有趣的是，Pixar在開發《超人特攻隊》中使用的技術時使用了這個想法的3D變化。我現在暫時沒有鏈接可用，但這個想法是從邊界開始固定值，反復用鄰居的平均值替換內部樣本的想法。 - defube

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ilmari Karonen · Accepted Answer

你所面对的基本上是经典的狄利克雷问题:

给定空间区域边界上函数的值，为该函数在该区域内分配值，以便其满足特定方程（例如拉普拉斯方程，该方程要求函数在整个内部都没有任意“颠簸”）。

有许多方法可以计算狄利克雷问题的近似解。一种简单的方法，适用于您的问题，是通过离散化系统来开始；也就是说，您需要采取一个高度值的有限网格，将固定值赋给那些位于等值线上的点，然后为其余点解决离散化版本的拉普拉斯方程。

现在，拉普拉斯方程实际上指定了一个简单的规则，即每个点的值都应该等于其相邻点的平均值。 在方程的数学公式中，我们要求这个规则在邻域半径趋近于零的极限情况下成立，但由于我们实际上是在有限的格子上工作，因此我们只需要选择一个合适的固定邻域。一些合理的邻域选择包括：

在上述选项中，最后一个通常产生最好的结果，因为它最接近高斯核函数，但前两个选项通常也很好，并且可能计算速度更快。

一旦选择了邻域并定义了固定边界点，就可以开始计算解决方案。对此，你基本上有两个选择：

对于每个（未受限）网格点，定义一个线性方程组，其中声明该点的值是其相邻点的平均值，并求解。如果您可以访问良好的稀疏线性系统求解器，这通常是最有效的方法，但从头编写一个可能具有挑战性。
使用迭代方法，首先为每个未受限制的网格点分配任意的初始猜测（例如使用线性插值），然后循环遍历网格，用其邻居的平均值替换每个点的值。然后不断重复此过程，直到值停止改变（很多）。