标签: topographical-lines

我一直致力于二维连续数据的可视化项目.这是您可以用来研究2D地图上的高程数据或温度模式的类型.从本质上讲,它实际上是一种将三维平面化为二维加彩色的方法.在我的特定研究领域,我实际上并没有处理地理高程数据,但这是一个很好的比喻,所以我会在这篇文章中坚持下去.

无论如何,在这一点上,我有一个"连续颜色"渲染器,我很满意:

渐变是标准色轮,其中红色像素表示具有高值的坐标,紫色像素表示低值.

底层数据结构使用了一些非常聪明的(如果我自己这么说的话)插值算法,可以任意深度缩放到地图的细节.

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

为了让您了解我正在考虑的内容,这里是一个穷人的实现(渲染器只要遇到与轮廓线相交的像素就使用黑色RGB值):

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

• 具有更陡峭斜率的图形区域导致更薄(并且经常断裂)的拓扑线.理想情况下,所有拓扑线应该是连续的.

• 具有更平坦斜率的图形区域导致更宽的拓扑线(并且通常是整个黑度区域,尤其是在渲染区域的外周边处).

因此,我正在研究一种矢量绘制方法,以获得那些漂亮,完美的1像素厚曲线.算法的基本结构必须包括以下步骤:

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

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

3. 将剩余的点组装成序列,使得两个点之间的每个段近似于高程中性轨迹,并且使得没有两个线段跨越路径.每个点序列必须创建一个闭合多边形,或者必须与渲染区域的边界框相交.

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

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

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

• 在渲染边界框中找到高点.从那个高点开始,沿着几条不同的轨迹下坡.只要遍历线超过高程阈值,请将该点添加到特定于高程的存储桶.当遍历路径达到局部最小值时,改变航向并向上行驶.

• 沿着渲染区域的矩形边界框执行高分辨率遍历.在每个海拔阈值处(以及在拐点处,斜坡反转方向的任何位置),将这些点添加到特定于海拔的铲斗中.完成边界遍历后,从这些桶中的边界点开始向内追踪.

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

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

在深入研究实现之前,我想看看StackOverflow上是否有其他人遇到过这类问题的经验,并且可以为准确有效的实现提供指导.

编辑:

我对ellisbben提出的"Gradient"建议特别感兴趣.而我的核心数据结构(忽略一些优化插值快捷键)可以表示为一组2D高斯函数的总和,这是完全可微的.

我想我需要一个数据结构来表示一个三维斜率,以及一个用于计算任意点的斜率矢量的函数.在我的头顶,我不知道该怎么做(虽然它看起来应该很容易),但如果你有一个解释数学的链接,我会非常感激!

更新:

由于ellisbben和Azim的出色贡献,我现在可以计算场中任意点的轮廓角.绘制真正的地形线将很快跟随!

这里有更新的渲染图,有和没有我一直在使用的基于ghetto栅格的topo-renderer.每个图像包括一千个随机采样点,由红点表示.该点处的轮廓角由白线表示.在某些情况下,在给定点处不能测量斜率(基于插值的粒度),因此红点在没有相应的轮廓线的情况下发生.

请享用!

(注意:这些渲染使用与之前渲染不同的表面形貌 - 因为我在每次迭代时随机生成数据结构,而我是原型 - 但核心渲染方法是相同的,所以我相信你会得到这个想法.)

这是一个有趣的事实:在这些渲染的右侧,你会看到一堆完美的水平和垂直角度的奇怪轮廓线.这些是插值过程的伪像,它使用插值器网格来减少执行核心渲染操作所需的计算次数(约500%).所有这些奇怪的轮廓线出现在两个插值器网格单元之间的边界上.

幸运的是,这些文物实际上并不重要.尽管在斜率计算期间可检测到伪像,但最终渲染器将不会注意到它们,因为它在不同的位深度处操作.

再次更新:

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

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

好胃口!!

我需要制作一个地形的地形图,我只有相当稀疏的(x,y,高度)数据样本.显然我不能制作一个完全准确的地图,但我想在某种意义上说"平滑".我需要量化"平滑度"(可能是表面曲率平方的平均值的倒数),我想最小化一个目标函数,它是两个量的总和:

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

由于我真正想要的是地形图,我真的在寻找一种方法来构建恒定高度的等高线,并且可能有一些聪明的几何方法来做到这一点,而无需谈论表面.当然我希望轮廓线也很平滑.

任何和所有建议欢迎.我希望这是一个众所周知的数值问题.我对C很熟悉并且具有FORTRAN的工作知识.关于Matlab和R我很无能为力.

关于我们样品的位置:我们计划大致均匀间距,但我们会在地形更有趣的地方采集更多样品.因此,举例来说,我们将比平原更加密集地对山区进行采样.但是我们肯定会有一些关于采样的选择,如果这样可以简化问题,甚至可以采用样本.唯一的问题是

• 我们不知道我们需要绘制多少地形才能找到我们正在寻找的功能.

• 取样是中等昂贵的,大约10分钟.因此,对100x100网格进行采样可能需要很长时间.