主題
Search

凸包

下載 Mathematica Notebook下載 Wolfram Notebook
ConvexHull2D
ConvexHull3D

點集 S 在 n 維空間中的凸包是包含 S 的所有凸集的交集。對於 N 個點 p_1, ..., p_N，凸包 C 由以下表達式給出

C={sum_(j=1)^Nlambda_jp_j:lambda_j>=0 for all j and sum_(j=1)^Nlambda_j=1}.

計算凸包是計算幾何中的一個問題。指定二維點集凸包的點的索引由以下命令給出ConvexHull[pts] 在 Wolfram 語言 包中ComputationalGeometry`。未來版本的 Wolfram 語言 將支援三維凸包。Meeussen 和 Weisstein 編寫了一個在 Wolfram 語言 中計算三維凸包的臨時包。

在 d 維中，“禮品包裝”演算法可以使用，其複雜度為 O(n^(|_d/2_|+1))，其中 |_x_| 是向下取整函式 (Skiena 1997, p. 352)。然而，在二維和三維中，存在複雜度為 O(nlnn) 的專用演算法 (Skiena 1997, pp. 351-352)。Yao (1981) 證明，對於二維情況，任何決策樹演算法都需要二次或更高階的測試，並且任何使用二次測試的演算法（包括所有當前已知的演算法）的複雜度都不能低於 O(nlnn)。然而，是否可以使用更高階的多項式測試獲得更好的複雜度仍然是一個開放問題 (Yao 1981)。Yao 的分析適用於最困難的情況，其中頂點數 n 等於凸包中的頂點數 h。在更簡單的情況下，其中 h<n，O(nlnn) 的界限可以提高到 O(nlnh) (Chan 1996)。

O'Rourke (1998) 給出了一個健壯的二維實現以及一個 O(n^2) 三維實現。Qhull在 2 到 8 維中高效工作 (Barber et al. 1996)。

任何非凸均勻多面體的對偶多面體是給定多面體凸包的星狀形式 (Wenninger 1983, pp. 3-4 和 40)。

另請參閱

Carathéodory 基本定理, 計算幾何, 交叉多胞形, Delaunay 三角剖分, 擴張, 幾何張成, Groemer 堆積, Groemer 定理, 半空間交集, 快樂結局問題, Radon 定理, 香腸猜想, 扭稜變換, Sylvester 四點問題, 溫度, Voronoi 圖 在 課堂中探索此主題

使用 探索

參考文獻

Barber, C. B.; Dobkin, D. P.; and Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software 22, 469-483, 1996.Chan, T. "Optimal Output-sensitive Convex Hull Algorithms in Two and Three Dimensions." Disc. Comput. Geom. 16, 361-368, 1996. http://www.cs.uwaterloo.ca/~tmchan/pub.html#conv23d.Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved Problems in Geometry. New York: Springer-Verlag, p. 8, 1991.de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O. "Convex Hulls: Mixing Things." Ch. 11 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 235-250, 2000.Edelsbrunner, H. and Mücke, E. P. "Three-Dimensional Alpha Shapes." ACM Trans. Graphics 13, 43-72, 1994.The Geometry Center. "Qhull." http://www.qhull.org/. Meeussen, W. L. J. and Weisstein, E. W. "Convex Hull." Mathematica package ConvexHull.m.O'Rourke, J. Computational Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.Preparata, F. R. and Shamos, M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.Santaló, L. A. Integral Geometry and Geometric Probability. Reading, MA: Addison-Wesley, 1976.Seidel, R. "Convex Hull Computations." Ch. 19 in Handbook of Discrete and Computational Geometry (Ed. J. E. Goodman and J. O'Rourke). Boca Raton, FL: CRC Press, pp. 361-375, 1997.Skiena, S. S. "Convex Hull." §8.6.2 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 351-354, 1997.Wenninger, M. J. Dual Models. Cambridge, England: Cambridge University Press, 1983.Yao, A. C.-C. "A Lower Bound to Finding Convex Hulls." J. ACM 28, 780-787, 1981.

在 上引用

凸包

請引用為

Weisstein, Eric W. "凸包。" 來自 Web 資源。 https://mathworld.tw/ConvexHull.html

主題分類