我需要实现一种等高线绘图算法（而不是只使用一个算法）。输入是（连续）函数 f: R^2 - > R（该函数是在整个域上定义的，而不仅仅是针对某些输入）。输出应该是矢量形式，即一组样条线或线段。
我正在寻找有关如何实现这一点的建议，最好以（科学）论文的形式。
我发现了一些 80 年代开发的算法的参考资料（“关卡追踪算法”）。过去30年这方面有什么发展吗？解决这个问题的标准方法是什么？
该算法将用于实时可视化，因此它需要速度快，同时仍能产生不错的结果。
（小型、独立且经过良好测试的 C/C++ 实现也将受到欢迎。）
I need to implement a contour plotting algorithm (as opposed to just using one). The input is a (continuous) function f: R^2 - > R (the function is defined over the entire domain, not just for certain inputs). The output should be in vector form, i.e. a set of splines or line segments.
I'm looking for recommendations on how to implement this, preferably in the form of (scientific) papers.
I found some references to algorithms developed in the 80s ("Level Tracing Algorithm"). Have there been any development in this area in the past 30 years? What's the standard method(s) used to solve this problem?
The algorithm will be used for real-time visualization, so it needs to be fast while still producing decent results.
(Small, self-contained and well tested C/C++ implementations would be welcomed as well.)
发布评论
评论（4）
我记得 TI-89 计算器使用了一个非常简单的方案，如下所示：
现在，您可能想要自适应地细化有趣的方块。 TI-89 的屏幕非常小（160x120），但这是没有必要的。可以在有趣的正方形内使用完全相同的方法。
I recall the TI-89 calculator used a very simple scheme like this:
Now, you may want to refine the interesting squares adaptatively. The TI-89 had a damn small screen (160x120) and this was not necessary. The exact same method can be used inside an interesting square.
例如，请参见 xfarbe。
See for instance xfarbe.
我可以建议最直接的方法：考虑一下您必须找到特定
Z的f(x,y) = Z轮廓。然后用顶点和边的等边三角形网格M = (V,E,r)为绘图字段D = Subset(RxR)播种，其中 < code>M - 网格，V- 顶点集，E- 边集，r- 三角形边长，细节级别，LOD。然后，对于V中的每个顶点，计算f的值。然后，对于E中的每条边，检查边 (e[k]) 的顶点 (f) 值是否为f例如 >v[i] 和v[j]）位于Z的不同侧面，即，如果f(v[i ])>Z和f(v[j])。如果是这样，则 f(x,y) = Z的轮廓线与该边e[k]相交于某个点 (c[k]< /code>)，可以线性近似：由于具有一个边缘轮廓相交的三角形在其余两条边缘中的一些边缘处有第二个相交（证明是微不足道的），我们得到第二个
c'[k]。因此，对于M中的每个三角形，我们要么没有线段，要么只有一条线段，近似于轮廓线。绘制所有找到的线段将为我们提供具有一定细节水平的f(x,y)=Z的近似等值线图r。降低r将产生更精细的轮廓，提高r将提供性能。May I suggest the most straightforward method: consider you have to find a contour of
f(x,y) = Zfor certainZ. Then seed your field of plot,D = subset(RxR)with net of equilateral triangle mesh of vertices and edges,M = (V,E,r), whereM- mesh,V-set of vertices,E- set of edges,r- triangle side length, thelevel of detail, LOD. Then, for every vertex inV, compute the value off. Then, for every edge inE, check if the edge (e[k]) has a value offon it's vertices (v[i]andv[j]for example) on the different sides aboutZ, that is, iff(v[i])>Zandf(v[j])<Z. If so, than the contour line off(x,y) = Zintersects this edgee[k]at a certain point (c[k]), which can be linearly approximated:As the triangle with one edge contour intersection has second intersection at some of the remaining two edges (proof is trivial), we obtain a second
c'[k]. Thus, for every triangle fromMwe have either none or single line segment, approximating the contour line. Drawing all the found segments will provide us an approximate contour plot off(x,y)=Zwith certain level of detailr. Loweringrwill produce finer contouring, raisingrwill give the performance.我认为你需要在某个网格上为你的函数创建一个数据数组 f[i,j] ，从每个单元格收集线段，然后将它们连接成一条曲线。您应该记住可能的圆圈（即网格中存在几条闭合曲线）。这个算法正是在 MathGL（跨平台 GPL 绘图库）中使用的 - 请参阅 mglGraph::Cont 的实现（） 功能。
I think you need to make a data arrays f[i,j] for yours function at some grid, collect line segment from each cell and connect them later into a curve(s). You should keep in mind possible circles (i.e. presence of several closed curves in the grid). Exactly this algorithm is used in MathGL (cross-platform GPL plotting library) -- see realization of mglGraph::Cont() function.