我一直工作在一个可视化项目2维连续数据。这是那种你可以用它来研究一个二维地图上的高程数据或温度模式的事情。在它的核心，它是真正扁平化三维空间分成两个维度加色的方法。在我的特殊的研究领域，我没有实际工作与地理高程数据，但这是一个很好的比喻，所以我会用它在整个这个岗位坚守。

I've been working on a visualization project for 2-dimensional continuous data. It's the kind of thing you could use to study elevation data or temperature patterns on a 2D map. At its core, it's really a way of flattening 3-dimensions into two-dimensions-plus-color. In my particular field of study, I'm not actually working with geographical elevation data, but it's a good metaphor, so I'll stick with it throughout this post.

总之，在这一点上，我有一个连续的颜色渲染器，我感到非常高兴：

Anyhow, at this point, I have a "continuous color" renderer that I'm very pleased with:

梯度的标准色轮，其中，红色像素指示坐标与高值，紫罗兰像素显示低的值。

The gradient is the standard color-wheel, where red pixels indicate coordinates with high values, and violet pixels indicate low values.

底层的数据结构使用了一些非常聪明的（如果我不这样说我自己）插值算法，使任意深度缩放到地图的详细信息。

The underlying data structure uses some very clever (if I do say so myself) interpolation algorithms to enable arbitrarily deep zooming into the details of the map.

在这一点上，我想提请一些地形等高线（使用二次贝塞尔曲线），但我一直没能找到任何好的文学作品描述了有效的算法找出那些曲线。

At this point, I want to draw some topographical contour lines (using quadratic bezier curves), but I haven't been able to find any good literature describing efficient algorithms for finding those curves.

为了让您的想法是什么，我想，这里是一个贫穷的人的实现（其中渲染器只使用了黑色的RGB值，每当遇到一个像素相交轮廓线）：

To give you an idea for what I'm thinking about, here's a poor-man's implementation (where the renderer just uses a black RGB value whenever it encounters a pixel that intersects a contour line):

有几个问题这种方法，虽然：

There are several problems with this approach, though:

图与陡破结果更薄（和经常断线）地形线领域。理想情况下，所有的地形行应该是连续的。

Areas of the graph with a steeper slope result in thinner (and often broken) topo lines. Ideally, all topo lines should be continuous.

的曲线与平坦斜率结果在较宽地形线区（和黑度往往整个区域，特别是在描绘区域的外周）。

Areas of the graph with a flatter slope result in wider topo lines (and often entire regions of blackness, especially at the outer perimeter of the rendering region).

所以，我期待在获取那些漂亮的，完美的1像素宽的曲线矢量绘图的方法。该算法的基本结构将必须包括以下步骤：

So I'm looking at a vector-drawing approach for getting those nice, perfect 1-pixel-thick curves. The basic structure of the algorithm will have to include these steps:

在每一个谨慎的高度，我想画一个地形线，发现了一组所在的坐标高程的协调是非常接近（给定任意小量值）所需的高度。

At each discreet elevation where I want to draw a topo line, find a set of coordinates where the elevation at that coordinate is extremely close (given an arbitrary epsilon value) to the desired elevation.

消除冗余点。例如，如果三个点是在完全-直线，则中心点是多余的，因为它可以在不改变曲线的形状来消除。同样地，用贝塞尔曲线，通常有可能通过调节邻近控制点的位置，以消除某类锚点。

Eliminate redundant points. For example, if three points are in a perfectly-straight line, then the center point is redundant, since it can be eliminated without changing the shape of the curve. Likewise, with bezier curves, it is often possible to eliminate cetain anchor points by adjusting the position of adjacent control points.

组装其余各点到一个序列，以使得两个点之间的每个段接近的正视中性轨迹，并且使得没有两个线段不断交叉路径。每个点序列必须创建一个封闭的多边形，或者必须相交的呈现区域的边界框。

Assemble the remaining points into a sequence, such that each segment between two points approximates an elevation-neutral trajectory, and such that no two line segments ever cross paths. Each point-sequence must either create a closed polygon, or must intersect the bounding box of the rendering region.

有关每个顶点，找到一对控制点，使得所得到的曲线显示出一个最小误差，相对于在步骤＃2消除了冗余点

For each vertex, find a pair of control points such that the resultant curve exhibits a minimum error, with respect to the redundant points eliminated in step #2.

确保地形在当前呈现规模可见的所有功能都通过适当的地形线psented重新$ P $。例如，如果数据包含具有高空尖峰，但具有非常小的直径，托波线仍然应该绘制。如果他们的特征直径比图像的整体呈现粒度较小的垂直特征应该只被忽略。

Ensure that all features of the topography visible at the current rendering scale are represented by appropriate topo lines. For example, if the data contains a spike with high altitude, but with extremely small diameter, the topo lines should still be drawn. Vertical features should only be ignored if their feature diameter is smaller than the overall rendering granularity of the image.

不过，即使在这些限制，我依然能想到的几种不同的方法可以找到行：

But even under those constraints, I can still think of several different heuristics for finding the lines:

查找在渲染包围盒的高点。从这个高点，旅游下坡沿若干不同的轨迹。任何时候，只要穿越线您越过海拔门槛，这一点添加到海拔专用桶。当遍历路径达到当地最低，改变路线和旅行上坡。

Find the high-point within the rendering bounding-box. From that high point, travel downhill along several different trajectories. Any time the traversal line crossest an elevation threshold, add that point to an elevation-specific bucket. When the traversal path reaches a local minimum, change course and travel uphill.

执行沿矩形边界框的呈现区域的高分辨率遍历。在每一个高程阈值（和拐点，只要坡度反转方向），这点增加至海拔专用桶。在完成边界穿越后，开始从这些桶的边界点向内跟踪。

Perform a high-resolution traversal along the rectangular bounding-box of the rendering region. At each elevation threshold (and at inflection points, wherever the slope reverses direction), add those points to an elevation-specific bucket. After finishing the boundary traversal, start tracing inward from the boundary points in those buckets.

扫描整个渲染区域，以高程测量在稀疏的固定时间间隔。对于每次测量，使用它的附近的正视阈值作为一种机制来决定是否利用其邻居内插的测量。使用这种技术将提供更好的保障在整个渲染区域覆盖，但它会是困难的组装产生的点到一个合理的秩序构建的路​​径。

Scan the entire rendering region, taking an elevation measurement at a sparse regular interval. For each measurement, use it's proximity to an elevation threshold as a mechanism to decide whether or not to take an interpolated measurement of its neighbors. Using this technique would provide better guarantees of coverage across the whole rendering region, but it'd be difficult to assemble the resultant points into a sensible order for constructing paths.

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

So, those are some of my thoughts...

潜水深入实施之前，我想看看其他人对计算器是否具有这类问题的经验，并能为准确，高效的实现提供了指针。

Before diving deep into an implementation, I wanted to see whether anyone else on StackOverflow has experience with this sort of problem and could provide pointers for an accurate and efficient implementation.

编辑：

我在梯度的建议由ellisbben作出特别感兴趣。和我的核心数据结构（忽略一些优化插补快捷键）可以被重新psented为一组2D高斯函数，这完全是可微的总和$ P $

I'm especially interested in the "Gradient" suggestion made by ellisbben. And my core data structure (ignoring some of the optimizing interpolation shortcuts) can be represented as the summation of a set of 2D gaussian functions, which is totally differentiable.

我想我需要一个数据结构来重新present三维坡度和函数用于计算斜率向量在任意点。关闭我的头顶，我不知道该怎么做，（虽然现在看来似乎应该是简单），但是如果你有一个链接讲解数学，我会非常感激！

I suppose I'll need a data structure to represent a three-dimensional slope, and a function for calculating that slope vector for at arbitrary point. Off the top of my head, I don't know how to do that (though it seems like it ought to be easy), but if you have a link explaining the math, I'd be much obliged!

更新：

由于受ellisbben和阿齐姆的杰出贡献，我现在可以计算轮廓角度任意点的领域。绘制真正的地形线将很快！

Thanks to the excellent contributions by ellisbben and Azim, I can now calculate the contour angle for any arbitrary point in the field. Drawing the real topo lines will follow shortly!

下面是最新效果图，有和没有贫民窟基于光栅的地形，渲染，我一直在使用。每个图像包括由红点psented一千个随机样本点，再$ P $。在对轮廓的角度，在这一点上是一条白线psented重新$ P $。在某些情况下，没有斜面可在给定的点（根据内插的颗粒度）进行测量，所以红点发生无角轮廓的对应的线。

Here are updated renderings, with and without the ghetto raster-based topo-renderer that I've been using. Each image includes a thousand random sample points, represented by red dots. The angle-of-contour at that point is represented by a white line. In certain cases, no slope could be measured at the given point (based on the granularity of interpolation), so the red dot occurs without a corresponding angle-of-contour line.

享受！

（注意：这些效果图使用不同的表面形貌比previous效果 - 因为我随机生成的数据结构在每次迭代，而我的原型 - 但核心的渲染方法是同样的，所以我敢肯定你的想法。）的

下面是一个有趣的事实：在这些效果图的右手边，你会看到一堆在完美的水平和垂直角度怪异的轮廓线。这些内插处理，它采用内插器的栅格，以减少计算的次数（约500％），必须进行芯渲染操作的工件。所有这些怪异轮廓线的发生两种内插器网格单元之间的边界上。

Here's a fun fact: over on the right-hand-side of these renderings, you'll see a bunch of weird contour lines at perfect horizontal and vertical angles. These are artifacts of the interpolation process, which uses a grid of interpolators to reduce the number of computations (by about 500%) necessary to perform the core rendering operations. All of those weird contour lines occur on the boundary between two interpolator grid cells.

幸运的是，这些文物实际上并不重要。虽然坡度计算过程中的文物被检测到，最后的渲染器不会注意到他们，因为它工作在不同的位深度。

Luckily, those artifacts don't actually matter. Although the artifacts are detectable during slope calculation, the final renderer won't notice them, since it operates at a different bit depth.

再次更新：

Aaaaaaaand，作为最后一个放纵之前，我去睡觉，这里的另一对效果图，一个在老学校不断彩的风格，和一个拥有20000梯度样品。在这组效果图，我已经消除了红点的点样品，因为这样会将杂波的形象。

Aaaaaaaand, as one final indulgence before I go to sleep, here's another pair of renderings, one in the old-school "continuous color" style, and one with 20,000 gradient samples. In this set of renderings, I've eliminated the red dot for point-samples, since it unnecessarily clutters the image.

在这里，你可以真正看到那些插的文物，我在前面提到，由于内插器收集的电网结构。我应该强调的是，这些伪影会在最终轮廓呈现完全看不见（因为任何两个相邻的内插器单元之间的大小的差小于所述比特深度渲染的图像的）。

Here, you can really see those interpolation artifacts that I referred to earlier, thanks to the grid-structure of the interpolator collection. I should emphasize that those artifacts will be completely invisible on the final contour rendering (since the difference in magnitude between any two adjacent interpolator cells is less than the bit depth of the rendered image).

个饱！

推荐答案

在梯度是一个数学运算符可以帮助你。

The gradient is a mathematical operator that may help you.

如果你可以把你插成微函数，高度的梯度永远指向最速上升的方向。相等的高度的所有曲线都是垂直于高度的在该点评估梯度

If you can turn your interpolation into a differentiable function, the gradient of the height will always point in the direction of steepest ascent. All curves of equal height are perpendicular to the gradient of height evaluated at that point.

您知道关于从最高点开始是明智的，但可能会失去功能，如果有多个本地最大。

Your idea about starting from the highest point is sensible, but might miss features if there is more than one local maximum.

我建议

在接高度值上，你会画线 在罚款，规则排列的网格创建一批点，然后步行一小步一小步的每个点的梯度方向朝向上，你想画一条线最近的身高 创建步进每个点垂直梯度曲线;杀死一个点消除多余的点时，另一条曲线太接近它 - 但要避免破坏沙漏状的数字中心，你可能需要检查的定向矢量之间的角度垂直于这两个点的梯度。 （我说的导向，我的意思是确保梯度和你计算垂直值之间的角度总是在相同的方向90度。）