计算几何 部分模板

struct vector
{
   double x,y;
   vector (double X=0,double Y=0)
   {
       x=X,y=Y;
    }
}
typedef vector point;

 

向量四则运算

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);}
vector operator *  (vector a,double p)  {return vector (a.x*p,a.y*p);}
vector operator /  (vector a.double p){return vector (a.x/p,a.y/p);}

 

精度控制

const double eps=1e-8;
int dcmp(double x)
{
    if (fabs(x)<eps) return 0; 
    else return x<0?-1:1;
}

 

求a向量的长度

double len(vector a)
{
    return sqrt(a.x*a.x+a.y*a.y)
}

 

点积

a·b的几何意义为a在b上的投影长度乘以b的模长

a·b=|a||b|cosθ,其中θ为a,b之间的夹角

坐标表示

a=(x1,y1) b=(x2,y2)

a·b=x1*x2+y1*y2;

double dot(vector a,vector b)
{
    return a.x*b.x+a.y*b.y;
}

 

两个向量的叉积是一个标量，a×b的几何意义为他们所形成的平行四边形的有向面积

坐标表示a=(x1,y1) b=(x2,y2)

a×b=x1y2-x2y1

double cross(vector a,vector b)
{
    return a.x*b.y-a.y*b.x;
}

 

点、直线、线段的关系

点到直线的距离

利用叉积求面积，然后除以平行四边形的底边长，得到平行四边形的高即点到直线的距离

double distl(point p,point a,point b)
{
    vector v=p-a; vector u=b-a;
    return fabs(cross(v,u))/len(u);
}

点到线段的距离

比点到直线的距离稍微复杂。因为是线段，所以如果平行四边形的高在区域之外的话就不合理，这时候需要计算点到距离较近的端点的距离

double dists(point p,point a,point b)
{
    if (a==b) return len(p-a);
    vector v1=b-a,v2=p-a,v3=p-b;
    if (dcmp(dot(v1,v2))<0) return len(v2);
    else if (dcmp(dot(v1,v3))>0) return len(v3);
    return fabs(cross(v1,v2))/len(v1);
}

 

判断两个线段是否相交

跨立实验：判断一条线段的两端是否在另一条线段的两侧（两个端点与另一线段的叉积乘积为负）。需要正反判断两侧

bool segment(point a,point b,point c,point d)
{
    double c1=cross(b-a,c-a),c2=cross(b-a,d-a);
    double d1=cross(d-c,a-c),d2=cross(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;
}

 

求两条直线的交点

point line_intersection(point a,point a0,point b,point b0)  
{  
    double a1,b1,c1,a2,b2,c2;  
    a1 = a.y - a0.y;  
    b1 = a0.x - a.x;  
    c1 = cross(a,a0);  
    a2 = b.y - b0.y;  
    b2 = b0.x - b.x;  
    c2 = cross(b,b0);  
    double d = a1 * b2 - a2 * b1;  
    return point((b1 * c2 - b2 * c1) / d,(c1 * a2 - c2 * a1) / d);  
}   

 

多边形相关 判断点在多边形内部

射线法：以该点为起点引一条射线，与多边形的边界相交奇数次，说明在多边形的内部

int pointin(point p,point* a,int n)   
{  
    int wn=0,k,d1,d2;  
    for (int i=1;i<=n;i++)  
    {  
        if (dcmp(dists(p,a[i],a[(i+1-1)%n+1]))==0)  return -1;//判断点是否在多边形的边界上   
        k=dcmp(cross(a[(i+1-1)%n+1]-a[i],p-a[i]));  
        d1=dcmp(a[i].y-p.y);  
        d2=dcmp(a[(i+1-1)%n+1].y-p.y);  
        if (k>0&&d1<=0&&d2>0)  wn++;  
        if (k<0&&d2<=0&&d1>0)  wn--;  
    }  
    if (wn)  return 1;  
    else return 0;  
}  

 

求多边形的面积

double PolygonArea(Point* p,int n)
{
    double area=0;
    for(int i=1;i<n-1;i++)
        area+=cross(p[i]-p[0],p[i+1]-p[0]);
    return area/2;
}