平面凸包 :
定义:对一个简单多边形来说,如果给定其边界上或内部的任意两个点,连接这两个点的线段上的所有点都被包含在该多边形的边界上或内部的话,则该多边形为凸多边形 。
在解决平面凸包下面介绍了两种算法:
一、 Graham扫描法,运行时间为O(nlgn)。
二、 Jarvis步进法,运行时间为O(nh),h为凸包中的顶点数。
例题 1 问题描述1: 求覆盖平面上n 个点的最小的凸多边形。也可以这样描述:给定一个连接的多边形,可能是凸多边形,也有可能是凹多边形。现在,你的任务就是编程求这个多边形的最小凸包。如果它本身是凸多边形,那么最小凸包就是它本身。 数据范围: 多边形顶点坐标X,Y 是非负整数,不超过512。 输入: 共有K 组数据,每组测试数据的点都是按逆时针顺序输入的,没有3 个点共线。 每组测试数据的第1 行是N,表示有N 个点。以下N 行,每行两个整数X,Y。 输出: 输出格式与输入格式一样,第一行是K,表示共有K 组输出。以下K 组数据: 每组的第一行为M,表示该凸包上有M 个顶点,以下M 行每行两个整数X,Y,表示凸包顶点的坐标。也按逆时针方向输出。 样例输入: 1 14 30 30 50 60 60 20 70 45 86 39 112 60 200 113 250 50 300 200 130 240 76 150 47 76 36 40 33 35 样例输出: 1 8 60 20 250 50 300 200 130 240 76 150 47 76 30 30
Graham扫描法
基本思想:通过设置一个关于候选点的堆栈s来解决凸包问题。
操作:输入集合Q中的每一个点都被压入栈一次,非CH(Q)(表示Q的凸包)中的顶点的点最终将被弹出堆栈,当算法终止时,堆栈S中仅包含CH(Q)中的顶点,其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。
注:下列过程要求|Q|>=3,它调用函数TOP(S)返回处于堆栈S 顶部的点,并调用函数NEXT-TO –TOP(S)返回处于堆栈顶部下面的那个点。但不改变堆栈的结构。
GRAHAM-SCAN(Q)
1 设P0 是Q 中Y 坐标最小的点,如果有多个这样的点则取最左边的点作为P0;
2 设
3 PUSH(p0 , S)
4 PUSH(p1 , S)
5 PUSH(p3 , S)
6 for i ←3 to m
7 do while 由点NEXT-TOP-TOP(S),TOP(S)和Pi 所形成的角形成一次非左转
8 do POP(S)
9 PUSH(pi , S)
10 return S
首先,找一个凸包上的点,把这个点放到第一个点的位置P0。然后把P1~Pm 按照P0Pi的方向排序,可以用矢量积(叉积)判定。
做好了预处理后开始对堆栈中的点
举例如下:
练习:HDU 1392 Surround the Trees
模板:http://www.cnblogs.com/jbelial/archive/2011/08/05/2128624.html