模拟退火判断一个圆是否可以放在一个多边形内

本文主要是介绍模拟退火判断一个圆是否可以放在一个多边形内，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
给定n个点的一个多边形，一个圆的半径，判断圆是否可以放在多边形里
*/
/* ***********************************************
Author :rabbit
Created Time :2014/7/3 22:46:38
File Name :2.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-4
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;
}
struct Point{double x,y;Point(double _x=0,double _y=0){x=_x;y=_y;}
};
Point operator + (Point a,Point b){return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a, Point b){return Point(a.x-b.x,a.y-b.y);
}
Point operator * (Point a,double p){return  Point(a.x*p,a.y*p);
}
Point operator / (Point a,double p){return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a, Point b){return a.x*b.x+a.y*b.y;
}
double Length(Point a){return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){return atan2(a.y,a.x);
}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;
}
Point vecnit(Point x){return x/Length(x);
}
Point normal(Point x){return Point(-x.y,x.x)/Length(x);
}
Point Rotate(Point a,double rad){return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){Point u=p-q;double t=Cross(w,u)/Cross(v,w);return p+v*t;
}
struct Line{Point p,v;double ang;Line(){};Line(Point _p,Point _v):p(_p),v(_v){ang=atan2(v.y,v.x);}Point point(double a){return p+(v*a);}bool operator < (const Line &L)const{return ang<L.ang;}
};
Point GetLineIntersection(Line a,Line b){return GetLineIntersection(a.p,a.v,b.p,b.v);
}
bool OnLeft(const Line &L,const Point &p){return Cross(L.v,p-L.p)>=0;
}
bool getdir(Point *p,int n){double ans=0;for(int i=0;i<n;i++)ans+=Cross(p[i],p[(i+1)%n]);if(dcmp(ans)>0)return 1;return 0;
}
bool OnSegment(Point p,Point a1,Point a2){return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<=0;
}
double DistanceToSegment(Point p,Point a,Point b){if(a==b)return Length(p-a);Point v1=b-a,v2=p-a,v3=p-b;if(dcmp(Dot(v1,v2))<0)return Length(v2);else if(dcmp(Dot(v1,v3))>0)return Length(v3);else return fabs(Cross(v1,v2))/Length(v1);
}
int isPointInPolygon(Point p,Point *poly,int n){int wn=0;for(int i=0;i<n;i++){if(OnSegment(p,poly[i],poly[(i+1)%n]))return -1;int k=dcmp(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));int d1=dcmp(poly[i].y-p.y);int d2=dcmp(poly[(i+1)%n].y-p.y);if(k>0&&d1<=0&&d2>0)wn++;if(k<0&&d2<=0&&d1>0)wn--;}if(wn!=0)return 1;return 0;
}
Point p[60],ret[60];
double ans[60];
int n;
double cal(Point tt){double ret=INF;for(int i=0;i<n;i++)ret=min(ret,DistanceToSegment(tt,p[i],p[(i+1)%n]));return ret;
}
int main()
{srand(time(NULL));while(~scanf("%d",&n)&&n){double maxx=-INF,minx=INF,maxy=-INF,miny=INF;for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);maxx=max(maxx,p[i].x);minx=min(minx,p[i].x);maxy=max(maxy,p[i].y);miny=min(miny,p[i].y);}double R;scanf("%lf",&R);bool flag=0;if(getdir(p,n)==0)reverse(p,p+n);maxx-=minx;maxy-=miny;double pp=sqrt(maxx*maxx+maxy*maxy)/2;p[n]=p[0];for(int i=0;i<n;i++)ret[i]=(p[i]+p[i+1])/2;memset(ans,0,sizeof(ans));while(!flag&&pp>1e-4){for(int i=0;!flag&&i<20;i++)for(int j=0;j<5&&!flag;j++){double gg=rand();Point temp;temp.x=ret[i].x+pp*cos(gg);temp.y=ret[i].y+pp*sin(gg);if(isPointInPolygon(temp,p,n)){double ss=cal(temp);if(ss>ans[i]){ans[i]=ss;ret[i]=temp;if(dcmp(ans[i]-R)>=0)flag=1;}}}pp*=0.8;}if(flag)puts("Yes");else puts("No");}
}

这篇关于模拟退火判断一个圆是否可以放在一个多边形内的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---