【摘要】：如果线段QiQj总不在多边形Q外，则称Q为凸多边形。如果凸多边形Q顶点QiS∈，且Q是可覆盖S中各点的最小凸多边形；则称凸多边形Q为二维点集S的凸壳，简称点集凸壳或凸壳。定义1.15 凡能构造性生成给定二维点集S={Pi│1≤i≤m，3≤m＜∞}的二维凸壳的算法，统称二维点集凸壳生成算法，简称点集凸壳算法或凸壳算法。二维凸壳问题的几何原型，可简单而形象地进行说明，如图1.13所示。
定义1.12 设多边形Q的顶点是给定平面内的点Q1（x1，y1），Q2（x2，y2），…，Qn（xn，yn）。如果线段QiQj（i≠j，1≤i≤n，1≤j≤n，3≤n＜+∞）总不在多边形Q外，则称Q为凸多边形。
定义1.13 设二维点集S={Pi（xi，yi）│1≤i≤m，3≤m＜∞}由给定平面内的点构成。如果凸多边形Q顶点QiS∈，且Q是可覆盖S中各点的最小凸多边形；则称凸多边形Q为二维点集S的凸壳，简称点集凸壳或凸壳。
定义1.14 如何寻求给定二维点集S={Pi（xi，yi）│1≤i≤m，3≤m＜+∞}的二维凸壳，称为二维点集凸壳（简称点集凸壳或二维凸壳）问题。
定义1.15 凡能构造性生成给定二维点集S={Pi（xi，yi）│1≤i≤m，3≤m＜∞}的二维凸壳的算法，统称二维点集凸壳生成算法，简称点集凸壳算法或凸壳算法。
二维凸壳问题的几何原型，可简单而形象地进行说明，如图1.13所示。对1≤i≤m，在木板的点集中各点Pi（xi，yi）处分别钉1个图钉，再用一条橡皮带从外沿绷紧围绕这些图钉。显然有：首先，被缠紧的橡皮带必恰好构成一个凸多边形Q；其次，所有图钉总不在该橡皮带（即：凸多边形Q）所围成的区域之外。
图1.13 二维凸壳问题几何原型的形象说明示意图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
