征集多边形和圆的相关算法

Question

计算任意多边形之间相交以后重合部分的面积还有圆和任意多边形相交以后重合部分的面积有什么好算法？欢迎大家提供相关信息，谢谢。

Answer 1

/*  判断圆是否在多边形内.ptolineseg()函数的应用2 */
bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[])
{
POINT q;
double d;
q.x=0;
q.y=0;
d=ptopointset(vcount,polygon,center,q);
if(d<radius||fabs(d-radius)<EP)
return true;
else
return false;
}

Answer 2

两圆公共面积：// 必须保证相交
double c2area(POINT p1,double r1,POINT p2,double r2)
{
POINT rp1,rp2;
c2point(p1,r1,p2,r2,rp1,rp2); if(r1>r2) //保证r2>r1
{
swap(p1,p2);
swap(r1,r2);
}
double a,b,rr;
a=p1.x-p2.x;
b=p1.y-p2.y;
rr=sqrt(a*a+b*b); double dx1,dy1,dx2,dy2;
double sita1,sita2;
dx1=rp1.x-p1.x;
dy1=rp1.y-p1.y;
dx2=rp2.x-p1.x;
dy2=rp2.y-p1.y;
sita1=acos((dx1*dx2+dy1*dy2)/r1/r1); dx1=rp1.x-p2.x;
dy1=rp1.y-p2.y;
dx2=rp2.x-p2.x;
dy2=rp2.y-p2.y;
sita2=acos((dx1*dx2+dy1*dy2)/r2/r2);
double s=0;
if(rr<r2) //相交弧为优弧
s=r1*r1*(PI-sita1/2+sin(sita1)/2)+r2*r2*(sita2-sin(sita2))/2;
else   //相交弧为劣弧
s=(r1*r1*(sita1-sin(sita1))+r2*r2*(sita2-sin(sita2)))/2; return s;
}圆和直线关系：//0----相离 1----相切 2----相交
int clpoint(POINT p,double r,double a,double b,double c,POINT &rp1,POINT &rp2)
{
int res=0; c=c+a*p.x+b*p.y;
double tmp;
if(a==0&&b!=0)
{
tmp=-c/b;
if(r*r<tmp*tmp)
res=0;
else if(r*r==tmp*tmp)
{
res=1;
rp1.y=tmp;
rp1.x=0;
}
else
{
res=2;
rp1.y=rp2.y=tmp;
rp1.x=sqrt(r*r-tmp*tmp);
rp2.x=-rp1.x;
}
}
else if(a!=0&&b==0)
{
tmp=-c/a;
if(r*r<tmp*tmp)
res=0;
else if(r*r==tmp*tmp)
{
res=1;
rp1.x=tmp;
rp1.y=0;
}
else
{
res=2;
rp1.x=rp2.x=tmp;
rp1.y=sqrt(r*r-tmp*tmp);
rp2.y=-rp1.y;
}
}
else if(a!=0&&b!=0)
{
double delta;
delta=b*b*c*c-(a*a+b*b)*(c*c-a*a*r*r);
if(delta<0)
res=0;
else if(delta==0)
{
res=1;
rp1.y=-b*c/(a*a+b*b);
rp1.x=(-c-b*rp1.y)/a;
}
else
{
res=2;
rp1.y=(-b*c+sqrt(delta))/(a*a+b*b);
rp2.y=(-b*c-sqrt(delta))/(a*a+b*b);
rp1.x=(-c-b*rp1.y)/a;
rp2.x=(-c-b*rp2.y)/a;
}
}
rp1.x+=p.x;
rp1.y+=p.y;
rp2.x+=p.x;
rp2.y+=p.y;
return res;
}