大家好,欢迎来到IT知识分享网。
目录
一. 凸包概念
1. 凸多边形
凸多边形(Convex Polygon)指如果把一个多边形的所有边中,任意一条边向两方无限延长成为一直线时,其他各边都在此直线的同旁,那么这个多边形就叫做凸多边形,其内角应该全不是优角,任意两个顶点间的线段位于多边形的内部或边上。
2. 凸包
一组平面上的点,求一个包含所有点的最小的凸多边形,这就是凸包问题了。这可以形象地想成这样:在地上放置一些不可移动的木桩,用一根绳子把他们尽量紧地圈起来,并且为凸边形,这就是凸包了。
二. 凸包性质
1. 凸包上的每一个点与它相邻点构成的角都是向左转的。
2. 凸包对应了包含这些点的最小凸多边形,最大多边形面积,最小多边形周长。
三. 凸包求解
Problem Description
给定二维平面上n个点,求出这n个点所对应的凸包。
1. Graham扫描算法
2. Andrew算法
2.1 算法思路
定义以水平为x轴,竖直为y轴,给出点坐标,叉积z轴指向屏幕外正向,指向内负向。其算法过程如下:
(1)初始化:将所有的点,按照x由小到大排序(x相同时按照y由小到大排序),则最左侧第一个点和最右侧最后一个点一定在凸包上;
(2)第一遍扫描:从左到右,先将第一个点P0放入栈中,P1不一定在不在凸包上,先放入栈中;然后若P0P1P0P3 > 0,则说明P3在左拐方向,符合凸包定义,入栈继续判断;每次取出栈顶两点构成向量,若跟新点符合凸包定义则入栈,否则就删除栈顶元素直到符合。这时一定会形成一个下凸包;
(3)第二遍扫描:从右到左,同上做法,这时一定会形成一个上凸包;
(4)合并凸包:上下凸包合并就是一个凸包;
该算法的平均复杂度为O(n),其中nlogn排序+n扫描。其正确性证明参考:二位凸包Andrew算法
2.2 代码模板
Poj3348 Cows
#include <iostream> //#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define eps 1e-6 const int maxn = + 7; int dcmp(double x){if(fabs(x)<eps)return 0;else return x<0?-1:1;} struct Point{ double x,y; Point(double xx = 0,double yy = 0):x(xx),y(yy) {} bool operator<(const Point&another)const{ if(x==another.x)return y<another.y; return x<another.x; } }p[maxn],ch[maxn]; typedef Point Vector; Vector operator+(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);} Vector operator-(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);} double Length(Vector A){return sqrt(A.x*A.x+A.y*A.y);} double Cross(Vector A,Vector B){ return A.x*B.y - B.x*A.y; } double ConvexPolygonArea(Point *point,int len){//求面积 double area = 0; for(int i = 1;i<len-1;i++){ area+=Cross(point[i]-point[0],point[i+1]-point[0]); } return area/2; } double ConvexPolygonPerimeter(Point *point,int len){//求周长 double l = 0; for(int i = 1;i<len;i++){ l+=Length(point[i]-point[i-1]); } l+=Length(point[0]-point[len-1]); return l; } int Andrew(int n){ sort(p,p+n); int m = 0; for(int i = 0;i<n;i++){//第一遍扫描 while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++] = p[i]; } int k = m; for(int i = n-2;i>=0;i--){//第二遍扫描 while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++] = p[i]; } if(n>1)m--; return m; } int main() { int n; while(scanf("%d",&n)!=EOF){ for(int i = 0;i<n;i++){ scanf("%lf%lf",&p[i].x,&p[i].y); } int ans = Andrew(n); printf("%d\n",(int)(ConvexPolygonArea(ch,ans)/50)); } return 0; }
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/123036.html