问题标签 [topographical-lines]

我一直致力于二维连续数据的可视化项目。这是您可以用来研究 2D 地图上的高程数据或温度模式的东西。从本质上讲，它实际上是一种将 3 维扁平化为 2 维加颜色的方法。在我的特定研究领域中，我实际上并没有使用地理高程数据，但这是一个很好的比喻，所以我将在这篇文章中坚持使用它。

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

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

底层数据结构使用一些非常聪明的（如果我自己这么说的话）插值算法来实现对地图细节的任意深度放大。

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

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

但是，这种方法存在几个问题：

• 具有较陡坡度的图形区域会导致地形线较细（并且通常是断线）。理想情况下，所有地形线都应该是连续的。

• 具有更平坦斜率的图形区域会导致更宽的地形线（通常是整个黑色区域，尤其是在渲染区域的外围）。

所以我正在寻找一种矢量绘图方法来获得那些漂亮的、完美的 1 像素厚的曲线。算法的基本结构必须包括以下步骤：

1. 在我要绘制地形线的每个离散高程处，找到一组坐标，其中该坐标处的高程与所需的高程非常接近（给定任意 epsilon 值）。

2. 消除多余的点。例如，如果三个点在一条完全直线上，则中心点是多余的，因为可以在不改变曲线形状的情况下消除它。同样，对于贝塞尔曲线，通常可以通过调整相邻控制点的位置来消除某些锚点。

3. 将剩余的点组装成一个序列，使得两点之间的每个线段都近似于高度中性轨迹，并且没有两条线段会交叉路径。每个点序列必须要么创建一个封闭的多边形，要么必须与渲染区域的边界框相交。

4. 对于每个顶点，找到一对控制点，使得结果曲线相对于步骤 #2 中消除的冗余点显示出最小误差。

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

但即使在这些限制下，我仍然可以想到几种不同的启发式方法来寻找线条：

• 找到渲染边界框内的高点。从那个高点开始，沿着几条不同的轨迹下坡。每当遍历线越过高程阈值时，将该点添加到特定于高程的存储桶中。当遍历路径达到局部最小值时，改变路线并上坡。

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

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

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

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

编辑：

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

我想我需要一个数据结构来表示一个三维斜率，以及一个用于计算任意点的斜率向量的函数。在我的脑海中，我不知道该怎么做（虽然看起来应该很容易），但如果你有一个解释数学的链接，我会非常感激！

更新：

感谢 ellisbben 和 Azim 的出色贡献，我现在可以计算该领域中任意点的轮廓角。绘制真正的地形线将很快出现！

这是更新的渲染，有和没有我一直在使用的基于 ghetto raster 的拓扑渲染器。每个图像包含一千个随机样本点，用红点表示。该点的轮廓角由一条白线表示。在某些情况下，在给定点无法测量斜率（基于插值的粒度），因此红点出现时没有相应的等高线角度线。

享受！

（注意：这些渲染使用与以前的渲染不同的表面形貌——因为我在每次迭代时随机生成数据结构，而我正在制作原型——但核心渲染方法是相同的，所以我相信你得到这个想法。）

这是一个有趣的事实：在这些渲染图的右侧，您会看到一堆奇怪的轮廓线，它们处于完美的水平和垂直角度。这些是插值过程的产物，它使用插值器网格来减少执行核心渲染操作所需的计算数量（约 500%）。所有这些奇怪的轮廓线都出现在两个插值器网格单元之间的边界上。

幸运的是，这些文物实际上并不重要。尽管在斜率计算期间可以检测到伪影，但最终渲染器不会注意到它们，因为它以不同的位深度运行。

再次更新：

啊啊啊，作为我睡觉前的最后一次放纵，这是另一对效果图，一个是老式的“连续颜色”风格，一个有 20,000 个渐变样本。在这组渲染中，我已经消除了点样本的红点，因为它不必要地使图像混乱。

在这里，您可以真正看到我之前提到的那些插值工件，这要归功于插值器集合的网格结构。我应该强调的是，这些伪影在最终的轮廓渲染中将完全不可见（因为任何两个相邻插值器单元之间的幅度差异小于渲染图像的位深度）。

开胃！！

我需要制作一个地形的地形图，我只有相当稀疏的（x，y，高度）数据样本。显然我无法制作一张完全准确的地图，但我想要一张在某种意义上“平滑”的地图。我需要量化“平滑度”（可能是表面曲率平方的平均值的倒数），并且我想最小化作为两个量之和的目标函数：

• 表面粗糙度
• 采样点表面高度与该点实际测量高度之间的均方距离

因为我真正想要的是一张地形图，所以我真的在寻找一种方法来构建等高线的等高线，并且可能有一些巧妙的几何方法可以做到这一点，而不必谈论表面。当然，我希望轮廓线也很平滑。

欢迎任何和所有建议。我希望这是一个众所周知的数值问题。我对 C 语言非常熟悉，并且具备 FORTRAN 的工作知识。关于 Matlab 和 R 我相当一无所知。

关于我们的样本所在的位置：我们正在计划大致均匀的间距，但我们会在地形更有趣的地方采集更多样本。因此，例如，我们将比平原更密集地采样山区。但是我们在抽样方面肯定有一些选择，如果这样可以简化问题，甚至可以抽样。唯一的问题是

• 我们不知道需要映射多少地形才能找到我们正在寻找的特征。

• 取样费用适中，大约需要 10 分钟。因此，对 100x100 网格进行采样可能需要很长时间。