主题
Search

三角剖分

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
Triangulation

三角剖分是将一个曲面或平面多边形划分为一组三角形，通常限制为每个三角形边完全由两个相邻的三角形共享。1925 年证明了每个曲面都有一个三角剖分，但这可能需要无限数量的三角形，并且证明很困难 (Francis and Weeks 1999)。三角剖分中三角形数量有限的曲面称为紧致曲面。

Wickham-Jones (1994) 给出了一个 O(n^3) 三角剖分算法（“otectomy”），O'Rourke (1998, p. 47) 概述了一种将此算法改进为 O(n^2) 的方法，Lennes (1911) 首先完成了这个改进。Garey等人。(1978) 给出了一个算法上直接的 O(nlnn) 三角剖分方法，多年来一直被认为是最佳方法。然而，Tarjan 和 van Wyk (1988) 提出了一个 O(nlglgn) 算法。Chazelle (1991) 随后提出了一个出乎意料的结果，他表明任意简单多边形可以在 O(n) 时间内进行三角剖分。然而，根据 Skiena (1997) 的说法，“这个算法很难实现。”

另请参阅

美术馆定理, 质心外心, 紧致表面, 德劳内三角剖分, 日本定理, 简单多边形, 镶嵌, 三角剖分点

使用 Wolfram|Alpha 探索

参考文献

Amato, N. M.; Goodrich, M. T.; and Ramos, E. A. "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time." Discr. Comput. Geom. 26, 245-265, 2001.Chazelle, B. "Triangulating a Simple Polygon in Linear Time." Disc. Comput. Geom. 6, 485-524, 1991.de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O. "Polygon Triangulation: Guarding an Art Gallery." Ch. 3 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 45-61, 2000.Eppstein, D. "Triangles and Simplices." http://www.ics.uci.edu/~eppstein/junkyard/triangulation.html.Fournier, A. and Montuno, D. Y. "Triangulating Simple Polygons and Equivalent Problems." ACM Trans. Graphics 3, 153-174, 1984.Francis, G. K. and Weeks, J. R. "Conway's ZIP Proof." Amer. Math. Monthly 106, 393-399, 1999.Friedman, E. "Triangulating Triangles." http://www.stetson.edu/~efriedma/triang/.Garey, M. R.; Johnson, D. S.; Preparata, F. P.; and Tarjan, R. E. "Triangulating a Simple Polygon." Inform. Process. Lett. 7, 175-179, 1978. Kraus, M. "Polygon Triangulation." http://library.wolfram.com/infocenter/MathSource/23/.Lennes, N. J. "Theorems on the Simple Finite Polygon and Polyhedron." Amer. J. Math. 33, 37-62, 1911.O'Rourke, J. §2.3 in Computational Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.Radó, T. "Über den Begriff der Riemannschen Fläche." Acta Litt. Sci. Reg. Univ. Hungar. Francisco-Josephinae 2, 101-121, 1924-1926.Skiena, S. S. "Triangulation." §8.6.3 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 355-357, 1997.Tarjan, R. and van Wyk, C. "An O(nlglgn) Algorithm for Triangulating a Simple Polygon." SIAM J. Computing 17, 143-178, 1988. Wickham-Jones, T. "ExtendGraphics Packages." http://library.wolfram.com/infocenter/Books/3753/.Wickham-Jones, T. Mathematica Graphics: Techniques and Applications. New York: Springer-Verlag, pp. 406 and 448, 1994.

在 Wolfram|Alpha 中被引用

三角剖分

请这样引用

Weisstein, Eric W. "三角剖分。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/Triangulation.html

主题分类