algorithm - 绘制地形图

Question

我一直在从事二维连续数据的可视化项目。您可以使用这种东西来研究2D map 上的海拔数据或温度模式。从本质上讲，它实际上是将3维平面化为2维彩色的一种方法。在我的特定研究 Realm ，我实际上并没有使用地理海拔数据，但这是一个很好的隐喻，因此在本文中我将坚持使用。

无论如何，在这一点上，我有一个令我非常满意的“连续颜色”渲染器:

渐变是标准色轮，其中红色像素表示坐标较高，紫色像素表示坐标较低。

底层数据结构使用一些非常聪明的(如果我自己说的话)插值算法来实现对 map 细节的任意深度缩放。

在这一点上，我想绘制一些地形轮廓线(使用二次贝塞尔曲线)，但是我还没有找到任何好的文献来描述找到这些曲线的有效算法。

为了让您了解我的想法，这是一个穷人的实现(渲染器在遇到与轮廓线相交的像素时仅使用黑色RGB值):

但是，这种方法存在一些问题:

斜率较大的图形区域会导致地形线更细(且经常断裂)。理想情况下，所有地形线应该是连续的。

坡度较平坦的图形区域会导致宽的拓 flutter 线(通常是整个黑色区域，尤其是在渲染区域的外围)。

因此，我正在寻找一种 vector 绘制方法，以获取那些漂亮的，完美的1像素厚的曲线。该算法的基本结构必须包括以下步骤:

在要绘制地形线的每个离散高程处，找到一组坐标，其中该坐标处的高程与所需的高程极其接近(给定任意epsilon值)。

消除冗余点。例如，如果三个点在一条直线上，则该中心点是多余的，因为可以在不更改曲线形状的情况下将其消除。同样，使用贝塞尔曲线，通常可以通过调整相邻控制点的位置来消除某些 anchor 。

将其余的点组合成一个序列，以使两点之间的每个线段近似于高程-中性轨迹，并且没有两个线段穿过路径。每个点序列必须创建一个封闭的多边形，或者必须与渲染区域的边界框相交。

对于每个顶点，找到一对控制点，以使所得曲线相对于在步骤＃2中消除的冗余点表现出最小的误差。

确保在当前渲染比例下可见的所有地形特征均由适当的地形线表示。例如，如果数据包含高海拔但直径极小的尖峰，则仍应绘制地形线。仅当垂直特征的特征直径小于图像的总体渲染粒度时，才应忽略它们。

但是即使在这些约束下，我仍然可以想到几种不同的启发式方法来寻找界限:

在渲染边界框中找到最高点。从那个高点，沿着几种不同的轨迹下坡。每当遍历线超过海拔阈值时，都将该点添加到海拔特定的存储段中。当遍历路径达到局部最小值时，请改变路线并上坡行驶。

沿着渲染区域的矩形边界框执行高分辨率遍历。在每个高程阈值处(以及在拐点处，无论坡度反转方向如何)，都将这些点添加到特定于高程的铲斗中。完成边界遍历后，从这些存储桶中的边界点开始向内跟踪。

扫描整个渲染区域，以稀疏的规则间隔进行高程测量。对于每次测量，都使用它与海拔阈值的接近度作为一种机制来决定是否对其邻域进行插值测量。使用这种技术可以更好地保证整个渲染区域的覆盖范围，但是很难将生成的点组合成合理的顺序来构建路径。

所以，这些是我的一些想法...

在深入研究实现之前，我想了解一下StackOverflow上的其他人是否有处理此类问题的经验，并可以为准确，高效的实现提供指导。

编辑:

我对ellisbben提出的“渐变”建议特别感兴趣。我的核心数据结构(忽略一些优化的插值快捷方式)可以表示为一组2D高斯函数的总和，这是完全可区分的。

我想我需要一个数据结构来表示三维斜率，以及一个用于在任意点计算斜率 vector 的函数。我不知道该怎么做(尽管看起来应该很容易)，但是如果您有一个解释数学的链接，我将非常有义务!

更新:

由于ellisbben和Azim的出色贡献，我现在可以计算出该场中任意点的轮廓角。绘制真实的地形线将很快出现!

这是更新的渲染图，带有或不带有我一直使用的基于贫民窟栅格的拓 flutter 渲染器。每个图像包括一千个随机采样点，用红点表示。该点的轮廓角由白线表示。在某些情况下，无法在给定点测量斜率(基于插值的粒度)，因此出现红点而没有相应的轮廓线。

请享用!

(注意:这些渲染使用的曲面拓 flutter 与以前的渲染不同-因为我在原型(prototype)制作时每次迭代都会随机生成数据结构-但是核心渲染方法是相同的，所以我确定您可以这个想法。)



这是一个有趣的事实:在这些渲染图的右侧，您会看到一堆怪异的轮廓线，它们的水平和垂直 Angular 都很完美。这些是插值过程的构件，该过程使用插值器网格来减少执行核心渲染操作所需的计算数量(减少约500％)。所有这些奇怪的轮廓线都出现在两个插值器网格单元之间的边界上。

幸运的是，这些 Artifact 实际上并不重要。尽管在斜率计算过程中可以检测到伪像，但最终渲染器不会注意到它们，因为它以不同的位深度进行操作。

再次更新:

Aaaaaaaand，作为我睡前的最后一个沉迷，这是另一对效果图，一个是老式的“连续颜色”风格，另一个是20,000个渐变样本。在这套渲染中，我消除了点样本的红点，因为它不必要地使图像困惑。

在这里，由于interpolator集合的网格结构，您可以真正看到我之前提到的那些插值 Artifact 。我要强调的是，这些伪像在最终轮廓渲染中将是完全不可见的(因为任意两个相邻插值器单元之间的幅度差小于渲染图像的位深度)。

胃口好!

Answer 1

gradient是可以帮助您的数学运算符。

如果您可以将插值转换为微分函数，则高度梯度将始终指向最陡峭的上升方向。所有等高曲线均垂直于在该点评估的高度梯度。

您关于从最高点开始的想法很明智，但是如果存在多个以上的局部最大值，则可能会错过功能。

我建议

选择要绘制线条的高度值

在精细且规则间隔的网格上创建一堆点，然后在渐变方向上以小步长逐步移动每个点，直至其最接近要绘制线的高度

通过垂直于渐变的每个点来创建曲线；当另一条曲线离它太近时，通过杀死一个点来消除多余的点-但为避免破坏沙漏之类的图形，您可能需要检查两个点的垂直于梯度的定向 vector 之间的 Angular 。 (当我说“定向”时，我的意思是确保梯度和您计算的垂直值之间的 Angular 始终在同一方向上为90度。)