计算几何_多边形

判定凸多边形：顶点凹凸性法

连续三个顶点p1,p2,p3。计算p1p2,p2p3的叉乘，阶乘大于0，则表示p3点在线段p1和p2的左侧，然后依次计算下一个前后所组成向量的阶乘，如果在计算时，出现负值，则此多边形是凹多边形，如果所有顶点计算完毕，其结果都大于0，则多边形是凸多边形。

判断点在凸多边形内外：

①：与判定凸多边形差不多，用判断点与多边形两顶点叉乘，都大于0，点在多边形内，小于0，点在多边形外。
②：水平/垂直交叉点数判别法（适用于任意多边形包括凹凸边形）
注意到如果从P作水平向左的射线的话，如果P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。

判断线段在任意多边形内：

（1）首先，要判断一条线段是否在多边形内，先要判断线段的两个端点是否在多边形内。如果两个端点不全在多边形内，那么，线段肯定是不在多边形内的。
（2）其次，如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），则线段肯定不在多边形内。
（3）如果多边形的某个顶点和线段相交，则必须判断两相交交点之间的线段是否包含于多边形内。

求多边形重心：

以第一个顶点为基准，分别连接p[i]，p[i+1]，1<i<n。将多边形划分为若干个三角形，求出了每个三角形的重心，用叉积求三角形面积，对凸多边形和凹多边形都适用（因为值有正负）；作为二维的多边形，把面积作为权值，分别乘以重心坐标的X和Y值；分别将求出的X, Y值的加权平均数除以总面积，即多边形面积的重心坐标。

具体代码实现：

#include <iostream>
#include <stdlib.h>
#include <math.h>
#define MAXN 1000
#define offset 10000
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))

using namespace std ;

struct point{double x,y;}p[MAXN];
struct line{point a,b;};

double xmult(point p1,point p2,point p0)  //计算向量p1p2，p2p3的叉积
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

int is_convex(int n,point* p)  //判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线
{
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    return s[1]|s[2];
}
int is_convex_v2(int n,point* p)  //判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线
{
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[0]&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    return s[0]&&s[1]|s[2];
}

int inside_convex(point q,int n,point* p)  //判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
{
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
    return s[1]|s[2];
}
int inside_convex_v2(point q,int n,point* p)  //判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0
{
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[0]&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
    return s[0]&&s[1]|s[2];
}

int inside_polygon(point q,int n,point* p,int on_edge=2)  //判点在任意多边形内,顶点按顺时针或逆时针给出,on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限
{
	point q2;
	int i=0,count;
	while (i<n)
		for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)//随机取一个足够远的点q,以p为起点q为终点做射线L,依次对多边形的每条边进行考察
			if( zero(xmult(q,p[i],p[(i+1)%n])) && (p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps && (p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps )
				return on_edge;//点p在边上,返回on_edge
			else if (zero(xmult(q,q2,p[i])))
				break;//点q在射线pq2上，停止本循环，另取q2
			else if
				(xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)
				count++;
    return count&1;
}
inline int opposite_side(point p1,point p2,point l1,point l2)
{
	return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;
}
inline int dot_online_in(point p,point l1,point l2)
{
	return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}
int inside_polygon(point l1,point l2,int n,point* p)  //判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
{
    point t[MAXN],tt;
    int i,j,k=0;
    if (!inside_polygon(l1,n,p)||!inside_polygon(l2,n,p))
        return 0;
    for (i=0;i<n;i++)
        if (opposite_side(l1,l2,p[i],p[(i+1)%n])&&opposite_side(p[i],p[(i+1)%n],l1,l2))
            return 0;
        else if (dot_online_in(l1,p[i],p[(i+1)%n]))
            t[k++]=l1;
        else if (dot_online_in(l2,p[i],p[(i+1)%n]))//线段的某个端点在S上
            t[k++]=l2;
        else if (dot_online_in(p[i],l1,l2))
            t[k++]=p[i];
        for (i=0;i<k;i++)
            for (j=i+1;j<k;j++)
            {
                tt.x=(t[i].x+t[j].x)/2;
                tt.y=(t[i].y+t[j].y)/2;
                if (!inside_polygon(tt,n,p))
                return 0;
            }
        return 1;
}

point intersection(line u,line v)  //求多边形重心
{
    point ret=u.a;
    double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
    ret.x+=(u.b.x-u.a.x)*t;
    ret.y+=(u.b.y-u.a.y)*t;
    return ret;
}
point barycenter(point a,point b,point c)
{
    line u,v;
    u.a.x=(a.x+b.x)/2;
    u.a.y=(a.y+b.y)/2;
    u.b=c;
    v.a.x=(a.x+c.x)/2;
    v.a.y=(a.y+c.y)/2;
    v.b=b;
    return intersection(u,v);
}
point barycenter(int n,point* p)
{
    point ret,t;
    double t1=0,t2;
    int i;
    ret.x=ret.y=0;
    for (i=1;i<n-1;i++)
    if (fabs(t2=xmult(p[0],p[i],p[i+1]))>eps)
    {
        t=barycenter(p[0],p[i],p[i+1]);
        ret.x+=t.x*t2;
        ret.y+=t.y*t2;
        t1+=t2;
    }
    if (fabs(t1)>eps)
        ret.x/=t1,ret.y/=t1;
    return ret;
}

int main()
{
}