凸包之Jarvis步进法

xiaoxiao2021-02-28  97

Jarvis步进法:

概述:也可称为卷包裹法,思路是先找到一个在凸包上的点,然后卷过去,由于每次确定凸包上的一个点需要遍历所有的点,因此时间复杂度为O(N*H),其中N为全部点的数目,H为凸包上的点数目;

适用性:从时间复杂度可以看出此方法适用点的数目不易过多,建议适用Graham扫描法;

方法和步骤:(下述采用固定两点的方式)

(1)找到位于最低最左边的点p0,最高最右边的点pk,则此两点必为凸包上的点;

(2)对逆时针方向排列的顶点序列按p0pk构造右链,左链;

(3)右链构造:设定一个栈,先将p0入栈,对其他的点依据相对于栈顶元素的最小极角,并距离最远的点入栈,左链同理;

(4)核心:如何求相对于栈顶元素的最小极角?

设pk为最高点,p0位栈顶元素;

只要栈顶元素不是pk,循环做以下工作:

{

          pm=pk;

          for(int i=0;i<n;i++)//依次考查其他的点p[i],是否有相对于p[top]的最小极角

          {

                    if((p[top]p[i]×p[top]pm>0)||(p[top]p[i]与P[top]pm共线)&&(|p[top]p[i]|>|p[top]pm|)

                    {

                                pm=p[i];

                    }

          }

          经过上述一次遍历,得到的pm为相对于当前p[top]的具有最小极角的顶点,即右链中连接p[top]的下一个凸包的顶点;

}

左链同上述操作同理;

代码:(&&优先级高于||)

#include <stdio.h> #include <algorithm> using namespace std; struct POINT { int x,y; }; POINT point[100],pk; int n,top,k,Stack[100]; int det(POINT a,POINT b,POINT c){ return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } int dis(POINT a,POINT b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } void Jarvis(int n,int flag) { int m,tmp; POINT pm; Stack[0]=0;//p0进栈 top=0; while(m!=k) { pm=pk;m=k; for(int i=1;i<n;i++) { tmp=det(point[Stack[top]],point[i],pm); if((tmp>0&&flag==1)||(tmp<0&&flag==0)|| (tmp==0)&&(dis(point[Stack[top]],point[i])>dis(point[Stack[top]],pm))) { pm=point[i]; m=i; } } top++; Stack[top]=m; } if(flag==1) { for(int i=0;i<=top;i++) printf("(%d,%d)",point[Stack[i]].x,point[Stack[i]].y); } if(flag==0) { for(int i=top-1;i>0;i--) printf("(%d,%d)",point[Stack[i]].x,point[Stack[i]].y); printf("\n"); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&(point[i].x),&(point[i].y)); if(point[i].y<point[0].y||point[i].y==point[0].y&&point[i].x<point[0].x)//最左最低点 swap(point[0],point[i]); if(i==0) { pk=point[0]; k=0; } if(point[i].y>pk.y||point[i].y==pk.y&&point[i].x>pk.x)//最右最高点 { pk=point[i]; k=i; } } Jarvis(n,1);//右链 Jarvis(n,0);//左链 return 0; }

转载请注明原文地址: https://www.6miu.com/read-850378.html

最新回复(0)