什么算法的一种从轮廓线产生高度的地图？

问题描述

我在找一些插值轮廓线，以产生一个三维视图。轮廓不存储在一个画面中，每个点的轮廓的坐标被简单地存储在一个std ::矢量

I'm looking for interpolating some contour lines to generating a 3D view. The contours are not stored in a picture, coordinates of each point of the contour are simply stored in a std::vector.

有关凸轮廓：

，看来（我没有独自检查），该高度可以容易地计算（线性插值）通过使用两个最近轮廓的两个最近点之间的距离。

, it seems (I didn't check by myself) that the height can be easily calculates (linear interpolation) by using the distance between the two closest points of the two closest contours.

我的轮廓不一定是凸的：

my contours are not necessarily convex :

，所以它更棘手...... actualy我没有任何想法是什么样的算法，我可以使用。

, so it's more tricky... actualy I don't have any idea what kind of algorithm I can use.

我说完写离散拉普拉斯例如：

I finished to write a Discrete Laplace example :

您可以得到code 这里

you can get the code here

推荐答案

你有什么基本上是经典的的

What you have is basically the classical Dirichlet problem:

给定的函数的值的空间中的区域的边界上，在该区域的内部将值分配给该函数，使得它满足一个特定的方程（如，基本上需要的功能都没有乱颠簸），到处都在内部。

有很多方法来计算近似解的Dirichlet问题。一个简单的方法，应该很适合你的问题，是先离散系统;也就是说，你把高度值的有限的网格，分配固定值，那些位于轮廓线上的点，进而解决拉普拉斯方程的离散版本为剩余点

There are many ways to calculate approximate solutions to the Dirichlet problem. A simple approach, which should be well suited to your problem, is to start by discretizing the system; that is, you take a finite grid of height values, assign fixed values to those points that lie on a contour line, and then solve a discretized version of Laplace's equation for the remaining points.

现在，什么拉普拉斯方程实际上指定，在平原而言，是每一点应该有一个价值等于其邻国的平均水平。在公式的数学公式，我们要求这持有真正在极限附近的半径趋向于零，但由于我们实际上是工作的一个有限的格子，我们只需要选择一个合适的固定附近。邻里的几个合理的选择包括：

Now, what Laplace's equation actually specifies, in plain terms, is that every point should have a value equal to the average of its neighbors. In the mathematical formulation of the equation, we require this to hold true in the limit as the radius of the neighborhood tends towards zero, but since we're actually working on a finite lattice, we just need to pick a suitable fixed neighborhood. A few reasonable choices of neighborhoods include:

• 围绕中心点的四个垂直相邻的点（又名冯·诺依曼附近），
• 八大垂直和对角相邻网格点（又名摩尔邻域内），或
• 的八个正交和对角相邻网格点，加权使得正交相邻点被计数两次（以上两种选择的实质上的总和或平均值）。

• the four orthogonally adjacent points surrounding the center point (a.k.a. the von Neumann neighborhood),
• the eight orthogonally and diagonally adjacent grid points (a.k.a. the Moore neigborhood), or
• the eight orthogonally and diagonally adjacent grid points, weighted so that the orthogonally adjacent points are counted twice (essentially the sum or average of the above two choices).

（出上述选择的，最后一个通常产生最好的结果，因为它最接近一个高斯核，但前两者往往几乎一样好，而且可能会更快来计算。）

(Out of the choices above, the last one generally produces the nicest results, since it most closely approximates a Gaussian kernel, but the first two are often almost as good, and may be faster to calculate.)

一旦你选择了一个社区，并确定固定的边界点，它的时间来计算的解决方案。对于这一点，你基本上有两种选择：

Once you've picked a neighborhood and defined the fixed boundary points, it's time to compute the solution. For this, you basically have two choices:

1. 定义线性方程组的系统的，每各（无限制）网格一点一点，指出每一点的价值是其邻国的平均水平，解决。这通常是最有效的方法，如果你有机会获得一个良好的sparse解线性方程组，但从头开始编写可能是具有挑战性的。

1. Define a system of linear equations, one per each (unconstrained) grid point, stating that the value at each point is the average of its neighbors, and solve it. This is generally the most efficient approach, if you have access to a good sparse linear system solver, but writing one from scratch may be challenging.

使用迭代的方法，在这里您第一次给一个任意初始猜测到每个不受约束的网格点（例如，使用线性内插，你的建议），然后遍历所有的网格，平均替换每一点的价值其邻国。然后不断重复，直到值不再变化（多）。

Use an iterative method, where you first assign an arbitrary initial guess to each unconstrained grid point (e.g. using linear interpolation, as you suggest) and then loop over the grid, replacing the value at each point with the average of its neighbors. Then keep repeating this until the values stop changing (much).

这篇关于什么算法的一种从轮廓线产生高度的地图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！