计算几何基础

    计算几何是研究几何目标在计算机环境内的数学表示，计算等方面的理论和应用。

    首先必须理解向量的点积和叉积。点积一般用来计算投影，数学证明等。叉积用来判断相对方位，求面积等，叉积的模为平行四边形面积。

    问题1. 如何判断两条线段相交

   通过快速排斥实验和跨立实验。快速排斥实验室看以两条线段作为对角线的矩形是否相交，若不相交，则必定两条线段不相交；跨立实验是看其中一条线段是否跨立另一条线段，可以通过矢量叉积实现。

 

   问题2. 如何判断点在多边形内（ZOJ1081）

   一种简单的方法——射线法。从该点引一条水平射线，根据射线与多边形的交点数的奇偶性来判断。注意一些特殊情况。

   问题3. 如何求任意简单多边形面积（凸或者凹）

   根据矢量的叉积求解。按顺时针or逆时针将多边形顶点排序，构造向量pi=(xi,yi)，相当于从原点到多边形顶点的向量。将这些向量叉乘，最后取绝对值除以2就是多边形面积。

 

   问题4. 如何求凸包(POJ1113)

   Graham扫描法求凸包：

   a. 选择基点。首先将所有点按y坐标从小到大排序，若y坐标一样，再按x坐标排序。总之，基点就是最下最左的点。

   b. 将其余点和基点构成的向量按极角排序（逆时针），极角一样的，按照距离从小到大排。

   c. 用一个栈保存在凸包的点（顶点or边上的点），将前3个点加入到凸包中，然后判断当前点，设栈顶为p1，栈顶下一个顶点为p2，当前点为p，判断p2p相对于p2p1是不是非向右（p2p1叉乘p2p>=0），若是，则将p加入到栈中；否则p1必定不是凸包的顶点，将p1出栈，继续判断，直到所有点都被访问，栈中的点就包含了凸包上的点。注意，此时栈中的点不全是凸包的顶点，有可能是在凸包的边上。

 

附ZOJ1081和POJ1113的代码

 

ZOJ1081

/**
判断点是否在多边形内
解: 从该点向右发出一条射线,与多边形的交点为奇数则说明点在多边形内,否则在外.
注意特殊情况:
1. 点在多边形上-->根据题目意思确定
2. 多边形边与x轴平行-->不考虑
3. 射线与多边形的顶点相交-->只考虑某条线段的两个顶点中的一个(上点or下点)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
const int MaxN = 105;
const double eps = 1e-6;
int n,m;
struct Point
{
    double x;
    double y;
}p[MaxN];

///p0p1 X p0p2
double multi(const Point& p0, const Point& p1, const Point& p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}

bool zero(double a) { return fabs(a)<eps; }

///p0是否在线段[p1,p2]上
bool onSegment(const Point& p0, const Point& p1, const Point& p2)
{
    if( p0.x<=max(p1.x,p2.x)&&p0.x>=min(p1.x,p2.x)
        &&p0.y<=max(p1.y,p2.y)&&p0.y>=min(p1.y,p2.y) && zero(multi(p0,p1,p2)) )
        return true;
    return false;
}

///要判断的点,多边形顶点集(按顺时针or逆时针),顶点个数
bool InPolygon(const Point& p, Point* polygon, int n)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        Point p1 = polygon[i%n];
        Point p2 = polygon[(i+1)%n];
        if(onSegment(p,p1,p2))  ///1.是否落在多边形边上
            return true;
        if(p1.y==p2.y)          ///2.水平边(不考虑)
            continue;
        if(p.y>min(p1.y,p2.y)&&p.y<=max(p1.y,p2.y))     ///***3.有交点,若是交在顶点,只考虑上点
        {
            double x = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y) + p1.x;
            if(p.x < x)         ///只考虑右侧(向右的射线)
                cnt++;
        }
    }
    return cnt%2==1;
}

int main()
{
    int i;
    int cases = 0;
    while(true)
    {
        scanf("%d",&n);
        if(n==0) break;
        scanf("%d",&m);
        for(i = 0; i < n; i++)
            scanf("%lf %lf",&p[i].x,&p[i].y);
        if(cases)
            printf("\n");
        printf("Problem %d:\n",++cases);
        for(i = 0; i < m; i++)
        {
            Point pp;
            scanf("%lf %lf",&pp.x,&pp.y);
            if(InPolygon(pp,p,n))
                printf("Within\n");
            else
                printf("Outside\n");
        }
    }
    return 0;
}

 

POJ1113

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Max = 1100;

struct Point
{
    int x;
    int y;
};
int num;
Point p[Max];   ///原始点集
Point ch[Max];  ///凸包点集
Point ans[Max];
int number;

///p0p1叉乘p0p2
int xmult(const Point& p0, const Point& p1, const Point& p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}

double dis(const Point& a, const Point& b)
{
    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

///逆时针顺序把极角排序
bool cmp(const Point& a, const Point& b)
{
    int ret = xmult(p[0],a,b);
    if(ret>0)
        return true;
    if(ret==0&&dis(p[0],a)<dis(p[0],b))
        return true;
    return false;
}

/**
p: 原始点序列
n: 原始点的个数
ch: 栈,用来保存凸包上的点
top: 凸包上点的个数
*/
void Graham(Point* p, int n, Point* ch, int& top)
{
    int i,k=0;
    for(i=1; i < n; i++)
    {
        if(p[k].y>p[i].y || ((p[k].y==p[i].y)&&p[k].x>p[i].x))
            k = i;
    }
    swap(p[k],p[0]);
    sort(p+1,p+n,cmp);
    top = 0;
    ch[top++] = p[0];
    ch[top++] = p[1];
    ch[top++] = p[2];
    for(i = 3; i < n; ch[top++]=p[i++])
        while(top>=2 && xmult(ch[top-2],ch[top-1],p[i])<0)    ///是否向左
            top--;
}

int main()
{
    int i;
    int n,l;
    while(scanf("%d %d",&n,&l)!=EOF)
    {
        for(i = 0; i < n; i++)
            scanf("%d %d",&p[i].x,&p[i].y);
        Graham(p,n,ch,num);
        double result = acos(-1.0)*l*2;

        number = 1;
        for(ans[0]=ch[0],i=1; i < num; i++)
        {
            if(xmult(ch[i-1],ch[i],ch[(i+1)%num])!=0)
                ans[number++] = ch[i];
        }
        for(i = 0; i < number-1; i++)
            result += dis(ans[i],ans[i+1]);
        result += dis(ans[0],ans[number-1]);
        /*for(i = 0; i < num-1; i++)
            result += dis(ch[i],ch[i+1]);
        result += dis(ch[0],ch[num-1]);*/
        printf("%.0f\n",result);
    }
    return 0;
}