凸包算法

凸包算法（convex hull algorithm），理学-计算机科学技术-计算机科学理论-算法-计算几何算法，求凸包的算法。凸包是包含一组给定点的最小凸多面体。概念简介凸包是计算几何（见计算几何算法）中非常基础、非常普遍的结构之一。由于凸包的特性，它是构成其他几何对象的有效工具，并且非常多的实际问题可以用凸包进行建模。非常多算法被提出用于计算有限点集或者有限几何对象集合的凸包。其相关的概念和方法被广泛应用于多个领域，例如数据挖掘、图像处理、数值模拟和模式识别等。1970年，Chand和Kapur提出包裹法（Gift wrapping）。该种方法的二维版本也叫Jarvis步进法（Jarvis march），由R.A.Jarvis在1973年发表。1972年，R.Graham发表了著名的Graham扫描法（Graham's scan），这是该领域早期的一项重要成果。Preparata和Hong在1977年首先将分治方法（见分治法）（Divide and conquer）应用于凸包计算。