Graham扫描法
基本思想:通过设置一个关于候选点的堆栈来解决凸包问题。
操作:输入集合P中的每一个点都被压入栈一次,非凸包中的顶点的点最终将被弹出堆栈,
当算法终止时,堆栈中仅包含凸包中的顶点,其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。
(1)设P0是P中Y坐标最小的点,如果有多个这样的点则取最左边的点作为P0;
(2) 设<P1,P2,……,Pn >是P中剩余的点,对其按逆时针方向相对P0 的极角进行排序,
如果有数个点有相同的极角,则去掉其余的点,只留下一个与P0 距离最远的那个点;
(3)
//前三个点先入栈
ch[0] = p[0];
ch[1] = p[1];
ch[2] = p[2];
//判断与其余所有点的关系
for (int i = 3; i < n; i++) {
//不满足向左转的关系,栈顶元素出栈
while (top > 0 && multiply(p[i], ch[top], ch[top - 1]) >= 0)
top--;
//当前点与栈内所有点满足向左关系,因此入栈.
ch[++top] = p[i];
}
原理:沿逆时针方向通过凸包时,在每个顶点处应该向左转。因此,while循环每次发现在一个顶点处没有向左转时,就把该顶点从堆栈中弹出。)当算法向点pi推进、在已经弹出所有非左转的顶点后,就把pi压入堆栈中。
下面是POJ1113的AC代码:关于POJ1113请参见
http://128kj.iteye.com/blog/1748635
import java.util.Scanner;
class Point {
double x;
double y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
Point[] ch; //点集p的凸包
Point[] p ; //给出的点集
int n;
int l;
int len=0;
public Main(Point[] p,int n,int l){
this.p=p;
this.n=n;
this.l=l;
ch= new Point[n];
}
//小于0,说明向量p0p1的极角大于p0p2的极角
public double multiply(Point p1, Point p2, Point p0) {
return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
//求距离
public double distance(Point p1, Point p2) {
return (Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y)
* (p1.y - p2.y)));
}
public void answer(){
double sum = 0;
for (int i = 0; i < len - 1; i++) {
sum += distance(ch[i], ch[i + 1]);
}
if (len > 1) {
sum += distance(ch[len - 1], ch[0]);
}
sum += 2 * l * Math.PI;
System.out.println(Math.round(sum));
}
public int Graham_scan() {
int k = 0, top = 2;
Point tmp;
//找到最下且偏左的那个点
for (int i = 1; i < n; i++)
if ((p[i].y < p[k].y)
|| ((p[i].y == p[k].y) && (p[i].x < p[k].x)))
k = i;
//将这个点指定为pts[0],交换pts[0]与pts[k]
tmp = p[0];
p[0] = p[k];
p[k] = tmp;
//按极角从小到大,距离偏短进行排序
for (int i = 1; i < n - 1; i++) {
k = i;
for (int j = i + 1; j < n; j++)
if ((multiply(p[j], p[k], p[0]) > 0)
|| ((multiply(p[j], p[k], p[0]) == 0) && (distance(
p[0], p[j]) < distance(
p[0], p[k]))))
k = j; //k保存极角最小的那个点,或者相同距离原点最近
tmp = p[i];
p[i] = p[k];
p[k] = tmp;
}
//前三个点先入栈
ch[0] = p[0];
ch[1] = p[1];
ch[2] = p[2];
//判断与其余所有点的关系
for (int i = 3; i < n; i++) {
//不满足向左转的关系,栈顶元素出栈
while (top > 0 && multiply(p[i], ch[top], ch[top - 1]) >= 0)
top--;
//当前点与栈内所有点满足向左关系,因此入栈.
ch[++top] = p[i];
}
len=top+1;
return len;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int l = in.nextInt();
int x, y;
Point[] p = new Point[n];
for (int i = 0; i < n; i++) {
x = in.nextInt();
y = in.nextInt();
p[i] = new Point(x, y);
}
Main ma=new Main(p,n,l);
ma.Graham_scan();
ma.answer();
}
}
- 大小: 38.1 KB
分享到:
相关推荐
采用Graham扫描法,实现提取凸包最小边界JS代码实现。(代码中点坐标采用平面坐标,如要在三维贴地展示,可转换为经纬度坐标)
用VS2010写的Graham扫描法求解凸包问题 包括两个库文件和一个主文件 两个库文件包括凸包问题中栈的基本操作以及用到的一些点的运算函数 主函数中包含了程序的主要流程
一般有两种算法来计算平面上给定n个点的凸包:Graham扫描法(Graham’s scan),时间复杂度为O(nlgn);Jarvis步进法(Jarvis march),时间复杂度为O(nh),其中h为凸包顶点的个数。这两种算法都按逆时针方向输出凸包顶点...
grahamScan扫描法求凸包 输入有若干组测试数据。每一组测试数据的第一行上有整数n,表示该组测试数据有n个点组成的。接下来有n行,其每一行上有二个正整数,之间用一个或几个空格隔开。当输入行上只有一个数0时,...
采用c++进行编程的凸包算法,是和生长算法不同的另一种构建tin的算法,该算法相对难度较大,此处用的是Graham扫描法
凸包最常用的凸包算法是Graham扫描法和Jarvis步进法 本程序用Graham扫描法实现凸包的绘制
12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一...
求凸包(Graham扫描法): 旋转卡壳法: Image_BWLabel(Python): Two-Pass法: Image_DFT_IDFT(C++): Image_FFT_IFFT(C++): : Image_Hough(C++): : Image_Radon(C++): : Image_White_Balance(C++): 灰度世界算法...
方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网。结果通过500至10000个点的测试,表明这种基于C-...
12.Graham扫描法寻找凸包 13.求两条线段的交点 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7....
12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一个数是否素数 ...
一、数学问题 1.精度计算——大数阶乘.乘法.加法.减法 .任意进制转换.最大公约数、最小公倍数....计算几何.Graham扫描法寻找凸包 .数论.求解模线性方程 图论.Dijkstra算法求单源最短路径.数据结构 。
凸包算法(Graham扫描法) Graham-Scan 辗转相除法求最大公约数 Greatest-Common-Divisor 堆排序 Heap-Sort ISAP算法 Improved-Shortest-Augmenting-Path(Naive) 插入排序 Insertion-Sort 字符串匹配(KMP) ...
Graham扫描法 水平序的引进,共线凸包的补丁 完美凸包算法 相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定 经典问题 最小外接圆 近似O(n)的最小外接圆算法 点集直径 ...
该算法首先使用Canny算子提取叶片轮廓,然后使用基于平面扫描法的Graham算法构造叶片轮廓凸包,最后提取叶片最小外接矩形。仿真实验结果表明:在Flavia植物叶片数据库中进行测试,该算法优于旋转法、顶点链码法。
8.4.3 Graham扫描算法 8.5 最近点对 8.6 水平线段和竖直线段的交点 8.7 小结 第9章 代数和数值算法 9.1 引言 9.2 求幂运算 9.3 欧几里得算法 9.4 多项式乘法 9.5 矩阵乘法 9.5.1 Winograd算法 9.5.2 ...
| GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的计算几何库 35 | 求平面上两点之间的距离 35 | (P1-P0)*(P2-P0)...