# 计算几何基础

# 基础几何要素的表示

# 点

在二维空间中，点可以用二元组 $(x,y)$ 表示；在三维空间中，点可以用三元组 $(x,y,z)$ 来表示。以此类推，可以给出任意维度空间中点的表示，但在CP中，通常只需要考虑二维和三维的情形，只有在一些特殊的数据结构中会涉及到更高维度，比如K-D树和区间树。

点同时也可以看成是从原点开始的向量，因此可以进行加减、数乘、点乘、叉乘等运算。

下面的示例中给出了点的结构体定义，其中定义了加减和数乘运算。

二维空间中点的结构体定义示例

struct point2d {
    ftype x, y;
    point2d() {}
    point2d(ftype x, ftype y): x(x), y(y) {}
    point2d& operator+=(const point2d &t) {
        x += t.x;
        y += t.y;
        return *this;
    }
    point2d& operator-=(const point2d &t) {
        x -= t.x;
        y -= t.y;
        return *this;
    }
    point2d& operator*=(ftype t) {
        x *= t;
        y *= t;
        return *this;
    }
    point2d& operator/=(ftype t) {
        x /= t;
        y /= t;
        return *this;
    }
    point2d operator+(const point2d &t) const {
        return point2d(*this) += t;
    }
    point2d operator-(const point2d &t) const {
        return point2d(*this) -= t;
    }
    point2d operator*(ftype t) const {
        return point2d(*this) *= t;
    }
    point2d operator/(ftype t) const {
        return point2d(*this) /= t;
    }
};
point2d operator*(ftype a, point2d b) {
    return b * a;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

三维空间中点的结构体定义示例

struct point3d {
    ftype x, y, z;
    point3d() {}
    point3d(ftype x, ftype y, ftype z): x(x), y(y), z(z) {}
    point3d& operator+=(const point3d &t) {
        x += t.x;
        y += t.y;
        z += t.z;
        return *this;
    }
    point3d& operator-=(const point3d &t) {
        x -= t.x;
        y -= t.y;
        z -= t.z;
        return *this;
    }
    point3d& operator*=(ftype t) {
        x *= t;
        y *= t;
        z *= t;
        return *this;
    }
    point3d& operator/=(ftype t) {
        x /= t;
        y /= t;
        z /= t;
        return *this;
    }
    point3d operator+(const point3d &t) const {
        return point3d(*this) += t;
    }
    point3d operator-(const point3d &t) const {
        return point3d(*this) -= t;
    }
    point3d operator*(ftype t) const {
        return point3d(*this) *= t;
    }
    point3d operator/(ftype t) const {
        return point3d(*this) /= t;
    }
};
point3d operator*(ftype a, point3d b) {
    return b * a;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 线

直线的表示方法很多，以二维空间为例，常见的表示方法有：

点斜式：直线上一点和直线斜率（无法表示平行于 $y$ -轴的直线）
两点式：直线上不相同的两点
斜截式：直线在 $y$ -轴上的截距和直线斜率。斜截式是点斜式的特殊情形。
截距式：直线在 $x$ -轴和 $y$ -轴上的截距。截距式是两点式的特殊情形。
参数式：已知直线上一点 $\mathbf{a}$ 和直线方向 $\mathbf{d}$ ，可以用参数方程 $\mathbf{r}=\mathbf{a}+t\cdot\mathbf{d}$ 来表示直线，其中 $t\in\mathbb{R}$ 。

# 面

# 多边形

# 圆形

← 关于计算几何