主题
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 图 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

凸包

请引用为

Weisstein, Eric W. "凸包。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ConvexHull.html

主题分类