为描述模式外形的重要特征;在分类中,一组物体的凸壳就可勾画出这些物体的所属的类 在计算机图形学中,使用一组点的凸壳可以显示出点簇;在几何问题中,集合S中最远两 点就是凸壳的顶点,等等。 131凸壳问题及其串行算法 给定平面中的点的集合S={P1,P2…,Pn},所谓S之凸壳简记为CHS,就是包含S 所有点的最小的凸多边形。实际中,假定平面上的n个点,用n个钉在木板上的图钉表示, 用一条橡皮带缠绕着这些图钉,然后放松橡皮带,在撑紧橡皮带所构成的平面图形就是凸多 边形。 图1.1图示求凸壳的方法 参照图1.1,串行算法的基本思路如下:①识别极点( Extreme point):S中那些最大 X坐标(XMAX),最大Y坐标(YMAX),最小X坐标(XMIN),最小Y坐标(YMIN)的那些顶点称为 极点:②识别凸边( Hull edge):线段(P,P)是CH(s)的一条凸边,当且仅当S的其余 2个顶点均位于穿过P和p的(无限长的)直线的同侧。由此定义可知,P1和P一定是 CH(S)的顶点:③识别凸点( Hull point):令P和P是CH(S)上的两连续顶点。假定取P为 坐标原点,那么在所有S中的点,P和P相对于X轴所形成的正的或负的夹角是最小。这 些点称为凸点。 很明显,极点都是CH(S的顶点,任何位于由极点所围成的多边形内的点都不是CHS) 的顶点,那些在多边形外的点可以归入由XMAX、XMN、YMAX、YMN所围成的四边形 与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中 顶点的凸边,再把这些凸边连接起来就可求得CH/S 算法175单处理机上求凸壳的串行算法 输入:n点集合S={Pp1,Pn} 输出:返回包含S的凸壳的顶点表列CH(S) B (1)识别极点,它们都是CHS的顶点 (2)将顶点归入有极点确定的四个三角区中,不在四个三角区中的顶点不需要处理 (3)计算顶点的极角,并排序 (31)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己为描述模式外形的重要特征；在分类中，一组物体的凸壳就可勾画出这些物体的所属的类； 在计算机图形学中，使用一组点的凸壳可以显示出点簇；在几何问题中，集合 S 中最远两 点就是凸壳的顶点，等等。 1.3.1 凸壳问题及其串行算法 给定平面中的点的集合 { , ,..., } S = p1 p2 pn ，所谓 S 之凸壳简记为 CH(S)，就是包含 S 所有点的最小的凸多边形。实际中，假定平面上的 n 个点，用 n 个钉在木板上的图钉表示， 用一条橡皮带缠绕着这些图钉，然后放松橡皮带，在撑紧橡皮带所构成的平面图形就是凸多 边形。 YMAX YMIN XMAX XMIN 图 1.1 图示求凸壳的方法 参照图 1.1，串行算法的基本思路如下：①识别极点（Extreme Point）：S 中那些最大 X 坐标(XMAX)，最大 Y 坐标(YMAX)，最小 X 坐标(XMIN)，最小 Y 坐标(YMIN)的那些顶点称为 极点；②识别凸边(Hull Edge)：线段 ( , ) pi p j 是 CH(S)的一条凸边，当且仅当 S 的其余 n －2 个顶点均位于穿过 i p 和 j p 的(无限长的)直线的同侧。由此定义可知， i p 和 j p 一定是 CH(S)的顶点；③识别凸点(Hull Point)：令 i p 和 j p 是 CH(S)上的两连续顶点。假定取 i p 为 坐标原点，那么在所有 S 中的点， j p 和 i p 相对于 X 轴所形成的正的或负的夹角是最小。这 些点称为凸点。 很明显，极点都是 CH(S)的顶点，任何位于由极点所围成的多边形内的点都不是 CH(S) 的顶点，那些在多边形外的点可以归入由 XMAX、XMIN、YMAX、YMIN 所围成的四边形 与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中 顶点的凸边，再把这些凸边连接起来就可求得 CH(S)。 算法 17.5 单处理机上求凸壳的串行算法 输入：n 点集合 { ,.., } S = p1 pn 输出：返回包含 S 的凸壳的顶点表列 CH(S) Begin (1) 识别极点，它们都是 CH(S)的顶点 (2) 将顶点归入有极点确定的四个三角区中，不在四个三角区中的顶点不需要处理 (3) 计算顶点的极角，并排序： (3.1)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己