刚接触一点计算几何,就把一些知识点记录在这里,后面会不断补充。

一、点 向量

这两个东西都可以用一对 double 来表示且运算基本相同,于是就放在一起。

0.储存

struct Vector
{
    int x, y;
    Vector(int _x, int _y) {x=_x, y=_y;}
};

1.加

Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

2.减

Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

3.点积

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

4.叉积

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

二、线段

0.储存

struct Line
{
    int k, b;
    int cal(int x) {return k * x + b;}
};

1.跨立实验

2.李超线段树
算法:用线段树标记永久化维护平面内线段覆盖情况

//维护线段的下凸壳
void insert(int &root, int l, int r, Line x) //插入线段
{
    if (!root) {t[root = ++tot] = x; return;}
    int lx=x.cal(l), rx=x.cal(r), ly=t[root].cal(l), ry=t[root].cal(r);
    if(lx<=ly && rx<=ry) {t[root]=x; return;}
    if(lx>ly && rx>ry) return;
    double p = 1.0 * (t[root].b - x.b) / (x.k - t[root].k);
    if(lx<ly)
    {
        if(p<=mid) insert(ls[root], l, mid, x);
        else insert(rs[root], mid+1, r, t[root]), t[root]=x;
    }
    else
    {
        if(p<=mid) insert(ls[root], l, mid, t[root]), t[root]=x;
        else insert(rs[root], mid+1, r, x);
    }
}

int query(int root, int l, int r, int x) //询问下凸壳纵坐标
{
    int temp = INF;
    if (root) temp = t[root].cal(x);
    if (l == r) return temp;
    if (x <= mid) temp = min(temp, query(ls[root], l, mid, x));
    else temp = min(temp, query(rs[root], mid + 1, r, x));
    return temp;
}

三、多边形

1.多边形面积
算法:取一点进行三角形剖分,然后用叉积求出三角形面积

double area()
{
    double ans=0;
    for(rint i=2; i<=n; ++i) ans+=cross(con[i-1], con[i])/2;
    return ans;
}

2.凸包
性质:所有邻边的叉积符号相同
算法:Graham扫描法

void Graham()
{
    sta[++top]=con[1];
    for(rint i=2; i<=n; ++i)
    {
        while(top>1 && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
    int lim=top;
    for(rint i=n; i>=1; --i)
    {
        while(top>lim && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注