c++ - 从等高线生成高度图的算法是什么？

Question

我正在寻找内插一些轮廓线以生成 3D View 。轮廓未存储在图片中，轮廓每个点的坐标仅存储在 std::vector 中。

对于凸轮廓:

，似乎(我没有自己检查)通过使用两个最近轮廓的两个最近点之间的距离可以很容易地计算出高度(线性插值)。

我的轮廓不一定是凸的:

，所以它更棘手......实际上我不知道我可以使用什么样的算法。

更新:2013 年 11 月 26 日

我完成了一个离散拉普拉斯示例的编写:

您可以获得代码here

Answer 1

你拥有的基本都是经典的 Dirichlet problem :

Given the values of a function on the boundary of a region of space, assign values to the function in the interior of the region so that it satisfies a specific equation (such as Laplace's equation, which essentially requires the function to have no arbitrary "bumps") everywhere in the interior.

有很多方法可以计算狄利克雷问题的近似解。一种应该非常适合您的问题的简单方法是从离散化系统开始；也就是说，您采用有限的高度值网格，为位于等高线上的那些点分配固定值，然后为其余点求解拉普拉斯方程的离散版本。

现在，拉普拉斯方程实际上指定的是，简单来说，每个点的值都应等于其相邻点的平均值。在方程的数学公式中，我们要求它当邻域的半径趋于零时，在极限情况下成立，但由于我们实际上是在有限格上工作，我们只需要选择一个合适的固定邻域。一些合理的社区选择包括:

• 围绕中心点的四个正交相邻点(又名 von Neumann neighborhood )，
• 八个正交和对角线相邻的网格点(又名 Moore neigborhood )，或
• 八个正交和对角线相邻的网格点，加权使得正交相邻点被计算两次(基本上是上述两个选择的总和或平均值)。

(在上面的选择中，最后一个通常会产生最好的结果，因为它最接近 Gaussian kernel ，但前两个通常几乎一样好，而且计算速度可能更快。)

一旦您选择了邻域并定义了固定边界点，就可以计算解决方案了。为此，您基本上有两种选择:

1. 定义一个 system of linear equations ，每个(不受约束的)网格点一个，说明每个点的值是其邻居的平均值，并且 solve it .这通常是最有效的方法，如果您可以访问一个好的 sparse linear system solver ，但从头开始编写可能具有挑战性。

2. 使用迭代方法，首先为每个不受约束的网格点分配一个任意的初始猜测值(例如，使用线性插值，如您所建议的)，然后在网格上循环，将每个点的值替换为平均值它的邻居。然后继续重复此操作，直到值停止变化(很大)。