【计算几何】 凸包问题

【计算几何】 凸包问题一组平面上的点 求一个包含所有点的最小的凸多边形 这就是凸包问题了

大家好,欢迎来到IT知识分享网。

目录

一. 凸包概念

1. 凸多边形

2. 凸包

二. 凸包性质

三. 凸包求解

1.  Graham扫描算法

2. Andrew算法

2.1 算法思路

2.2 代码模板


一. 凸包概念

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不一定在不在凸包上,先放入栈中;然后若P0P1\timesP0P3 > 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

(0)
上一篇 2025-10-12 09:26
下一篇 2025-10-12 09:45

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信