凸包算法设计_49703.ppt

凸包问题算法设计; 凸包概念 1.点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 2.一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。 算法：增量式算法,包裹法（Jarvis步进法）,葛立恒（Graham）扫描法,单调链,分治法,快包法（Akl-Toussaint启发式）等。;1.1 分治法的概念;1.2 问题分析图（PFD图）;1.3 过程描述;1.4 凸包问题的分治思想：;;1.5 凸包问题的分治算法;;; 2.1 凸包问题蛮力算法;2.2 具体描述;2.3 算法设计;;