主題
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) 的說法，“這個演算法很難實現。”

另請參閱

美術館定理, 質心外心, 緊緻表面, 德勞內三角剖分, 日本定理, 簡單多邊形, 鑲嵌, 三角剖分點

使用 探索

參考文獻

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.

在 中被引用

三角剖分

請這樣引用

Weisstein, Eric W. "三角剖分。" 來自 --一個 資源。 https://mathworld.tw/Triangulation.html

主題分類