「计算几何」

落影汐雾 4月 01, 2022

更新于：A.D.2022.04.01

参考资料

1.授课PDF

2.OI-Wiki

几何定理

欧拉公式

对于一个平面图 $G=\left \langle V,E,C,F \right \rangle$ ，有 $|V|$ 个顶点， $|E|$ 条连边， $|C|$ 个（弱）连通分量， $|F|$ 个区域（包含无限域），则

$|F|+|V|-|E|=|C|+1$

皮克公式

对于一个定点都位于格点上的多边形，设其面积为 $S$ ，多边形非边界内部的点数为 $a$ ，多边形边界上的点数为 $b$ ，则

$2S=2a+b-2$

二维几何

向量类（V vector）

class V {
    protected:
        double x, y;
    public:
        V() { x = y = 0; }
        V(double _x, double _y) : x(_x), y(_y) {}
        //...
};

点类（P point）

class P : public V {
    protected:
        int i;
    public:
        P() { x = y = 0; }
        P(double _x, double _y, int _i = -1): V(_x, _y), i(_i) {}
        //...
};

线段类（S segment）

 class S {
     protected:
         P u, v;
     public:
         S() {}
         S(P _u, P _v) : u(_u), v(_v) {}
         //...
 };

直线类（L line）

class L : public S {
    protected:
    public:
        L() {}
        L(P _u, P _v) : S(_u, _v) {}
        //...
};

圆类（C circle）

class C {
    protected:
        P o;
        double r;
       public:
        C() {}
        C(P _o, double _r) : o(_o), r(_r) {}
        //...
};

凸包类（CH convex_hull）

凸包是对于给定点集而言的，凸包是包含给定点集的最小凸多边形的边界点的集合。

一个多边形是凸的，当且仅当其内部任意两点的连线都被该多边形所包含。

class CH { //逆时针方向给出点
    protected:
        int n;
        P* p;
       public:
        CH() : n(0), p(NULL) {}
        CH(int _n) : n(0) { p = (P*)calloc(_n, sizeof(P)); }
        //...
};

常用函数

符号函数与比实数大小

const double eps = 1e-8;
int sgn(double a) { return a < -eps ? -1 : a > eps; }
int cmp(double a, double b) { return sgn(a - b); }

平方函数

double sqr(double x) { return x * x; }

向量的加减乘除

V operator + (const V& o) const { return V(x + o.x, y + o.y); }
V operator - (const V& o) const { return V(x - o.x, y - o.y); }
V operator * (double k) const { return V(x * k, y * k); }
V operator / (double k) const { return V(x / k, y / k); }

取出向量的某一分量

double operator [](int i) const { return i == 0 ? x : y; }

向量的模与辐角

$整型绝对值: abs(x) \\ 浮点型绝对值: fabs(x) \\ atan2(y,x)=\arctan(\frac{y}{x})$

double norm2() const { return sqr(x) + sqr(y); } //模长的平方
double norm() const { return sqrt(norm2()); } //模长
double arg() const { return atan2(y, x); } //辐角

向量的单位方向向量

V operator ~() const { return *this / norm(); }

两向量的点乘和叉乘

friend double dot(const V& a, const V& b) { return a.x * b.x + a.y * b.y; }
friend double det(Const V& a, const V& b) { return a.x * b.y - b.x * a.y; }

两向量的距离与夹角

$\mathbf{a}\cdot \mathbf{b}=|\mathbf{a}||\mathbf{b}| \cos\left \langle \mathbf{a},\mathbf{b} \right \rangle \\ \mathbf{a}\times \mathbf{b}=|\mathbf{a}||\mathbf{b}|\sin\left \langle \mathbf{a},\mathbf{b} \right \rangle \\ atan2(\mathbf{a}\times \mathbf{b},\mathbf{a}\cdot \mathbf{b})=atan2(\frac{\mathbf{a}\times \mathbf{b}}{\mathbf{a}\cdot \mathbf{b}})=atan2(\tan\left \langle \mathbf{a},\mathbf{b} \right \rangle)=\left \langle \mathbf{a},\mathbf{b} \right \rangle \\$

friend double dis(const V& a, const V& b) { return (a - b).norm(); }
friend double irad(const V& a, const V& b) { return atan2(det(a, b), dot(a, b)); }

旋转某向量（逆时针）

$\mathbf{V} = \begin{bmatrix} x \\ y \end{bmatrix} \\ 旋转矩阵(向逆时针方向转\alpha\ rad)\ \mathbf{T} = \begin{bmatrix} \cos(\alpha) & -\sin(\alpha) \\ \sin(\alpha) & \cos(\alpha) \end{bmatrix} \\ \mathbf{\hat{V}}=\mathbf{T}\mathbf{V}$

V rot(double a) { return V(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }

某向量的垂直向量（逆时针）

V perp() const { return V(-y, x); }

两点间的位移向量

V operator - (const P& o) const { return V(x - o.x, y - o.y); }

点的位移

P operator + (const V& o) const { return P(x + o[0], y + o[1]); }

点的微小扰动

void shake(double e = eps) {
    srand(time(0));
    x += (rand() / (double)RAND_MAX - 0.5) * e;
    y += (rand() / (double)RAND_MAX - 0.5) * e;
}

点到直线距离

$P(x,y) \quad l:uv\\ S=\frac{1}{2}|uv|\cdot d=\frac{1}{2}|(u-p)\times(v-p)| \\ d=\frac{|(u-p)\times(v-p)|}{|uv|}$

friend double dis(const L& l, const P& p) {
    return fabs(det(p - l[0], l[1] - l[0]) / l.len());
}

线段上定比分点

friend P defpoint(const L& l, double k) {
    return l[0] + l.dir() * k;
}

点关于直线的投影点

friend P proj(const L& l, const P& p) {
    return l[0] + ~l.dir() * dot(p - l[0], l[1] - l[0]) / l.len();
}

其他

跨立实验判断两线段是否相交

射线法判断点是否在多边形内部

经典问题及算法

二维凸包

平面最远点对

平面最近点对

圆反演

三维凸包

进阶内容

几何（计算机图形学）

仿射变换

射影几何

算法

自适应辛普森积分

最左转线法

三角剖分

问题

最小圆覆盖

圆的面积并

半平面交

平面图转对偶图 & 点定位

题目

圈奶牛Fencing the Cows /【模板】二维凸包

简单实验了一下封装方法和C++11

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
using std::cin;
using std::cout;
using std::endl;
using std::swap;
using std::sort;
const double eps = 1e-8;
int sgn(double a) { return a < -eps ? -1 : a > eps; }
int cmp(double a, double b) { return sgn(a - b); }
double sqr(double x) { return x * x; }
class V {
    protected:
        double x, y;
    public:
        V() { x = y = 0; }
        V(double _x, double _y) : x(_x), y(_y) {}
        //...
        V operator + (const V& o) const { return V(x + o.x, y + o.y); }
        V operator - (const V& o) const { return V(x - o.x, y - o.y); }
        V operator * (double k) const { return V(x * k, y * k); }
        V operator / (double k) const { return V(x / k, y / k); }
        double operator [](int i) const { return i == 0 ? x : y; }
        double norm2() const { return sqr(x) + sqr(y); }
        double norm() const { return sqrt(norm2()); }
        double arg() const { return atan2(y, x); }
        V operator ~() const { return *this / norm(); }
        friend double dot(const V& a, const V& b) { return a.x * b.x + a.y * b.y; }
        friend double det(const V& a, const V& b) { return a.x * b.y - b.x * a.y; }
        friend double dis(const V& a, const V& b) { return (a - b).norm(); }
        friend double irad(const V& a, const V& b) { return atan2(det(a, b), dot(a, b)); }
        V rot(double a) { return V(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
        V perp() const { return V(-y, x); }
};
class P : public V {
    protected:
        int i;
    public:
        P() { x = y = 0; }
        P(double _x, double _y, int _i = -1): V(_x, _y), i(_i) {}
        //...
        V operator - (const P& o) const { return V(x - o.x, y - o.y); }
        P operator + (const V& o) const { return P(x + o[0], y + o[1]); }
        bool operator < (const P& p) const {
            if(cmp(this->x, p.x) == 0) return cmp(this->y, p.y) == -1;
            else return cmp(this->x, p.x) == -1;
        }
        void shake(double e = eps) {
            srand(time(0));
            x += (rand() / (double)RAND_MAX - 0.5) * e;
            y += (rand() / (double)RAND_MAX - 0.5) * e;
        }
};
class S {
    protected:
        P u, v;
    public:
        S() {}
        S(P _u, P _v) : u(_u), v(_v) {}
        double len() const { return dis(u, v); }
        V dir() const { return u - v; }
        //...
        P operator [](int i) const { return i == 0 ? u : v; }
};
class L : public S {
    protected:
    public:
        L() {}
        L(P _u, P _v) : S(_u, _v) {}
        //...
        friend double dist(const L& l, const P& p) {
            return fabs(det(p - l[0], l[1] - l[0]) / l.len());
        }
        friend P defpoint(const L& l, double k) {
            return l[0] + l.dir() * k;
        }
        friend P proj(const L& l, const P& p) {
            return l[0] + ~l.dir() * dot(p - l[0], l[1] - l[0]) / l.len();
        }
};
class C {
    protected:
        P o;
        double r;
       public:
        C() {}
        C(P _o, double _r) : o(_o), r(_r) {}
        //...
};
class CH {
    protected:
        int n;
        P* p;
       public:
        CH() : n(0), p(NULL) {}
        CH(int _n) : n(0) { p = (P*)calloc(_n, sizeof(P)); }
        //...
        P operator [](int i) const { return p[i]; }
        void push_back(const P& _p) { p[n++] = _p; }
        void pop_back() { n--; }
        int size() { return n; }
        double sumPointDist() {
            double sum = dis(p[n-1], p[0]);
            for(int i = 1; i < n; i++) sum += dis(p[i], p[i-1]);
            return sum;
        }
};
CH graham(int n, P p[]) {
    int b = 0;
    for(int i = 1; i < n; i++) {
        if(p[i] < p[b]) { b = i; }
    }
    swap(p[0], p[b]);
    sort(p + 1, p + n, [&p](const P& u, const P& v) {
        return sgn(det(u - *p, v - *p)) > 0 || (sgn(det(u - *p, v - *p)) == 0 && sgn(dis(u, *p) - dis(v, *p)) < 0); 
    });
    CH ch(n);
    ch.push_back(p[0]), ch.push_back(p[1]);
    for(int i = 2; i < n; i++) {
        int ls = ch.size() - 1;
        while(ls > 0 && sgn(det(p[i] - ch[ls - 1], ch[ls] - ch[ls - 1])) >= 0) {
            ch.pop_back(), --ls;
        }
        ch.push_back(p[i]);
    }
    return ch;
}
int main()
{
    int n;
    cin >> n;
    P* p = new P[n];
    for(int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        p[i] = P(x, y, i);
    }
    CH ch = graham(n, p);
    cout << std::setiosflags(std::ios::fixed);
    cout << std::setprecision(2) << ch.sumPointDist() << endl;
    return 0;
}

Beauty Contest G /【模板】旋转卡壳

本文由落影汐雾原创，采用保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://shiokiri.com/2022-04-01-computational-geometry/