算法竞赛模板计算几何部分

计算几何基础模板：向量、线段、直线与多边形

本文整理二维计算几何中常用的基础知识与 C++ 模板，包括向量运算、To-Left 测试、线段相交、直线表示、投影、直线交点、多边形面积以及点与多边形的位置关系。

1. 二维基础

1.1 点与向量

在二维计算几何中，点和向量都可以用一对坐标表示：

$$P=(x,y)$$

因此实际写代码时，可以直接使用同一个 Point 结构体表示点和向量。

cpp

struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

如果需要区分语义，也可以直接写：

cpp

using Vector = Point;

---

1.2 点积

设两个二维向量分别为：

$$\overrightarrow{a}=(a_x,a_y),\overrightarrow{b}=(b_x,b_y)$$

它们的点积为：

$$\boxed{{\displaystyle \overrightarrow{a}\cdot \overrightarrow{b}=a_x{b}_x+a_y{b}_y}}$$

点积与夹角之间满足：

$$\boxed{{\displaystyle \overrightarrow{a}\cdot \overrightarrow{b}=|\overrightarrow{a}||\overrightarrow{b}|\cos \theta }}$$

因此点积常用于：

• 求向量夹角；
• 求投影；
• 判断两个向量是否垂直。

当

$$\overrightarrow{a}\cdot \overrightarrow{b}=0$$

时，两向量垂直。

代码：

cpp

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

---

1.3 叉积

二维向量叉积通常取其标量部分：

$$\boxed{{\displaystyle \overrightarrow{a}\times \overrightarrow{b}=a_x{b}_y-a_y{b}_x}}$$

代码：

cpp

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

三个点时，经常需要计算：

$$\overrightarrow{P_1{P}_2}\times \overrightarrow{P_1{P}_3}$$

可以封装为：

cpp

double cross(const Point& p1,
             const Point& p2,
             const Point& p3) {
    Point v1(p2.x - p1.x, p2.y - p1.y);
    Point v2(p3.x - p1.x, p3.y - p1.y);

    return cross(v1, v2);
}

几何意义

叉积绝对值等于两个向量构成的平行四边形面积：

$$\boxed{{\displaystyle S=|\overrightarrow{a}\times \overrightarrow{b}|}}$$

如果

$$\overrightarrow{a}\times \overrightarrow{b}=0$$

说明两个向量平行。

---

1.4 To-Left 测试

对于有向直线

$$A\to B$$

和待判断点 $P$，计算：

$$\overrightarrow{AB}\times \overrightarrow{AP}$$

也就是：

cpp

cross(A, B, P)

根据叉积符号可以判断点位于有向直线的哪一侧：

• cross(A, B, P) > 0：$P$ 在 $AB$ 左侧；
• cross(A, B, P) < 0：$P$ 在 $AB$ 右侧；
• cross(A, B, P) = 0：三点共线。

To-Left 测试是后续判断线段相交、点与多边形关系等问题的重要基础。

---

1.5 二维向量旋转

设向量：

$$\overrightarrow{a}=(a_x,a_y)$$

逆时针旋转 $\theta$ 后：

$$\boxed{{\displaystyle \begin{array}{rl}{x}^{\prime }& =a_x\cos \theta -a_y\sin \theta \\ y^{\prime }& =a_x\sin \theta +a_y\cos \theta \end{array}}}$$

C++ 中 sin()、cos() 使用的是弧度。

角度转换成弧度：

$$\boxed{{\displaystyle \text{radian}=\text{degree}\times \frac{\pi }{180}}}$$

cpp

const double PI = acos(-1.0);

double theta = 30.0 * PI / 180.0;

向量旋转模板：

cpp

Point rotate(Point a, double theta) {
    return {
        a.x * cos(theta) - a.y * sin(theta),
        a.x * sin(theta) + a.y * cos(theta)
    };
}

逆时针旋转 ${90}^{\circ }$：

cpp

Point rotate90(Point a) {
    return {-a.y, a.x};
}

---

2. 线段

2.1 点是否在线段上

判断点 $Q$ 是否在线段 $P_1{P}_2$ 上，需要满足：

1. 三点共线；
2. $Q$ 的横纵坐标都在线段端点对应的范围内。

代码：

cpp

#include 
using namespace std;

const double eps = 1e-8;

struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

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

double cross(const Point& p1,
             const Point& p2,
             const Point& p3) {
    return cross(
        Point(p2.x - p1.x, p2.y - p1.y),
        Point(p3.x - p1.x, p3.y - p1.y)
    );
}

// 点 q 是否在线段 p1p2 上
bool onSeg(const Point& p1,
           const Point& p2,
           const Point& q) {
    return fabs(cross(p1, p2, q)) < eps
        && q.x >= min(p1.x, p2.x) - eps
        && q.x <= max(p1.x, p2.x) + eps
        && q.y >= min(p1.y, p2.y) - eps
        && q.y <= max(p1.y, p2.y) + eps;
}

---

2.2 两线段是否相交

判断线段 $AB$ 和 $CD$ 是否相交，主要使用：

• 快速排斥；
• 跨立实验；
• 端点与共线情况判断。

快速排斥

如果两条线段的包围盒都没有交集，那么线段一定不相交。

跨立实验

判断 $C,D$ 是否分别位于直线 $AB$ 两侧：

$$cross(A,B,C)\times cross(A,B,D)<0$$

同时判断 $A,B$ 是否分别位于直线 $CD$ 两侧：

$$cross(C,D,A)\times cross(C,D,B)<0$$

两者同时成立时，两线段规范相交。

完整模板

cpp

bool segIntersect(Point a, Point b,
                  Point c, Point d) {
    // 快速排斥：包围盒不相交
    if (max(a.x, b.x) < min(c.x, d.x) - eps) return false;
    if (max(a.y, b.y) < min(c.y, d.y) - eps) return false;
    if (max(c.x, d.x) < min(a.x, b.x) - eps) return false;
    if (max(c.y, d.y) < min(a.y, b.y) - eps) return false;

    // 跨立实验
    double c1 = cross(a, b, c);
    double c2 = cross(a, b, d);
    double c3 = cross(c, d, a);
    double c4 = cross(c, d, b);

    // 规范相交
    if (c1 * c2 < -eps && c3 * c4 < -eps)
        return true;

    // 非规范相交：
    // 包括端点接触、共线重叠
    if (onSeg(a, b, c)) return true;
    if (onSeg(a, b, d)) return true;
    if (onSeg(c, d, a)) return true;
    if (onSeg(c, d, b)) return true;

    return false;
}

使用示例：

cpp

int main() {
    Point a(0, 0), b(2, 2);
    Point c(0, 2), d(2, 0);

    if (segIntersect(a, b, c, d))
        cout << "相交\n";
    else
        cout << "不相交\n";

    return 0;
}

---

3. 直线

3.1 Point / Vector 基础模板

这一部分可以作为后续直线、多边形等内容共同使用的基础模板。

cpp

#include 
using namespace std;

using db = double;

const db EPS = 1e-9;
const db PI = acos(-1.0);

int sgn(db x) {
    if (fabs(x) < EPS)
        return 0;

    return x < 0 ? -1 : 1;
}

struct Point {
    db x, y;

    Point() {}

    Point(db _x, db _y)
        : x(_x), y(_y) {}

    Point operator + (const Point& p) const {
        return {x + p.x, y + p.y};
    }

    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }

    Point operator * (db k) const {
        return {x * k, y * k};
    }

    Point operator / (db k) const {
        return {x / k, y / k};
    }

    bool operator < (const Point& p) const {
        if (sgn(x - p.x) != 0)
            return x < p.x;

        return y < p.y;
    }

    bool operator == (const Point& p) const {
        return sgn(x - p.x) == 0
            && sgn(y - p.y) == 0;
    }
};

using Vector = Point;

// 点积
db dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

// 叉积
db cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}

// OA × OB
db cross(Point O, Point A, Point B) {
    return cross(A - O, B - O);
}

// 向量长度平方
db len2(Vector a) {
    return dot(a, a);
}

// 向量长度
db len(Vector a) {
    return sqrt(len2(a));
}

// 两点距离
db dist(Point a, Point b) {
    return len(a - b);
}

// 单位向量
Vector normalize(Vector a) {
    return a / len(a);
}

// 逆时针旋转 90°
Vector rotate90(Vector a) {
    return {-a.y, a.x};
}

// 向量旋转 theta
Vector rotate(Vector a, db theta) {
    return {
        a.x * cos(theta) - a.y * sin(theta),
        a.x * sin(theta) + a.y * cos(theta)
    };
}

---

3.2 直线的表示

直线推荐使用点向式表示：

• 直线上一点 $P$；
• 一个方向向量 $\overrightarrow{v}$。

即：

$$\boxed{{\displaystyle X=P+t\overrightarrow{v}}}$$

代码：

cpp

struct Line {
    Point p;  // 直线上一点
    Point v;  // 方向向量
};

---

3.3 点在直线上的投影

设点 $P$ 在直线 $AB$ 上的投影点为 $H$。

直线方向向量：

$$\overrightarrow{v}=\overrightarrow{AB}=B-A$$

从 $A$ 指向 $P$：

$$\overrightarrow{AP}=P-A$$

根据点积的投影性质，可以得到参数：

$$\boxed{{\displaystyle t=\frac{\overrightarrow{AP}\cdot \overrightarrow{v}}{\overrightarrow{v}\cdot \overrightarrow{v}}}}$$

因此投影点：

$$\boxed{{\displaystyle H=A+t\overrightarrow{v}}}$$

进一步写成：

$$\boxed{{\displaystyle H=A+\frac{(P-A)\cdot (B-A)}{(B-A)\cdot (B-A)}(B-A)}}$$

模板：

cpp

Point projection(Point P, Point A, Point B) {
    Point v = B - A;
    Point AP = P - A;

    double t = dot(AP, v) / len2(v);

    return A + v * t;
}

示例：

cpp

int main() {
    Point P, A, B;

    cin >> P.x >> P.y;
    cin >> A.x >> A.y;
    cin >> B.x >> B.y;

    Point H = projection(P, A, B);

    cout << fixed << setprecision(10);
    cout << H.x << ' ' << H.y << '\n';

    return 0;
}

---

3.4 两直线交点

设两条直线分别为：

$$P+t\overrightarrow{v}$$

和

$$Q+s\overrightarrow{w}$$

交点模板：

cpp

Point lineIntersection(Point P, Vector v,
                       Point Q, Vector w) {
    Vector u = P - Q;

    db t = cross(w, u) / cross(v, w);

    return P + v * t;
}

如果使用四个点 $A,B,C,D$ 表示两条直线：

cpp

Point lineIntersection(Point A, Point B,
                       Point C, Point D) {
    Vector v = B - A;
    Vector w = D - C;

    db t = cross(w, A - C) / cross(v, w);

    return A + v * t;
}

使用之前一般先判断：

cpp

cross(B - A, D - C)

是否为 0。

若为 0，说明两条直线平行或者重合。

---

4. 多边形

4.1 三角形面积

利用叉积可以直接计算三角形面积：

$$\boxed{{\displaystyle S_{\mathrm{△}ABC}=\frac{1}{2}|\overrightarrow{AB}\times \overrightarrow{AC}|}}$$

模板：

cpp

db triangleArea(Point A, Point B, Point C) {
    return fabs(cross(B - A, C - A)) / 2.0;
}

---

4.2 多边形面积

多边形面积可以通过叉积累加计算。

模板：

cpp

db polygonArea(vector& p) {
    int n = p.size();

    db ans = 0;

    for (int i = 0; i < n; i++) {
        ans += cross(p[i], p[(i + 1) % n]);
    }

    return fabs(ans) / 2.0;
}

---

4.3 判断点是否在多边形内

这里使用回转数思想判断点 $P$ 与多边形的位置关系。

返回值约定：

text

0 -> 多边形外
1 -> 多边形边界上
2 -> 多边形内

多边形顶点顺时针、逆时针给出都可以。

先判断点是否在边界上

cpp

bool onSegment(Point p, Point a, Point b) {
    return sgn(cross(b - a, p - a)) == 0
        && sgn(dot(p - a, p - b)) <= 0;
}

第一部分：

cpp

cross(b - a, p - a) == 0

判断三点共线。

第二部分：

cpp

dot(p - a, p - b) <= 0

判断点 $P$ 位于线段 $AB$ 两端之间。

回转数判断

遍历多边形每一条有向边 $a\to b$。

向上穿过水平线时：

cpp

a.y <= p.y && b.y > p.y

如果点 $P$ 位于有向边左侧，则：

cpp

wn++;

向下穿过水平线时：

cpp

a.y > p.y && b.y <= p.y

如果点 $P$ 位于有向边右侧，则：

cpp

wn--;

最终：

• wn == 0：点在多边形外；
• wn != 0：点在多边形内。

其中 <= 与 > 的搭配也可以避免水平射线恰好经过多边形顶点时，对同一个顶点重复统计。

完整模板

cpp

// 判断点 p 是否在线段 ab 上
bool onSegment(Point p, Point a, Point b) {
    return sgn(cross(b - a, p - a)) == 0
        && sgn(dot(p - a, p - b)) <= 0;
}

/*
    判断点 p 与多边形的位置关系

    返回值：
    0 -> 多边形外
    1 -> 多边形边界上
    2 -> 多边形内

    多边形顶点可以顺时针，也可以逆时针
*/
int pointInPolygon(Point p, const vector& poly) {
    int n = poly.size();

    int wn = 0;

    for (int i = 0; i < n; i++) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];

        // 先判断是否恰好在边界上
        if (onSegment(p, a, b)) {
            return 1;
        }

        // 向上穿过水平射线
        // a 在 p 下方或同高度
        // b 严格在 p 上方
        if (a.y <= p.y && b.y > p.y) {
            // p 在有向边 a -> b 的左侧
            if (sgn(cross(b - a, p - a)) > 0) {
                wn++;
            }
        }

        // 向下穿过水平射线
        // a 严格在 p 上方
        // b 在 p 下方或同高度
        else if (a.y > p.y && b.y <= p.y) {
            // p 在有向边 a -> b 的右侧
            if (sgn(cross(b - a, p - a)) < 0) {
                wn--;
            }
        }
    }

    if (wn == 0)
        return 0;

    return 2;
}

时间复杂度：

$$\boxed{{\displaystyle O(n)}}$$

其中 $n$ 为多边形顶点数量。

---

5. 常用公式与函数速查

内容	公式 / 函数
点积	dot(a, b)
叉积	cross(a, b)
三点叉积	cross(O, A, B)
向量长度平方	len2(a)
向量长度	len(a)
两点距离	dist(a, b)
单位向量	normalize(a)
逆时针旋转 90°	rotate90(a)
任意角旋转	rotate(a, theta)
点在线段上	onSegment(p, a, b)
两线段相交	segIntersect(a, b, c, d)
点在直线上的投影	projection(P, A, B)
两直线交点	lineIntersection(...)
三角形面积	triangleArea(A, B, C)
多边形面积	polygonArea(poly)
点与多边形位置关系	pointInPolygon(p, poly)

---

6. 完整基础模板

如果比赛时希望直接复制一套基础模板，可以把常用的点、向量操作统一到一起：

cpp

#include 
using namespace std;

using db = double;

const db EPS = 1e-9;
const db PI = acos(-1.0);

int sgn(db x) {
    if (fabs(x) < EPS)
        return 0;

    return x < 0 ? -1 : 1;
}

struct Point {
    db x, y;

    Point() {}

    Point(db _x, db _y)
        : x(_x), y(_y) {}

    Point operator + (const Point& p) const {
        return {x + p.x, y + p.y};
    }

    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }

    Point operator * (db k) const {
        return {x * k, y * k};
    }

    Point operator / (db k) const {
        return {x / k, y / k};
    }

    bool operator < (const Point& p) const {
        if (sgn(x - p.x) != 0)
            return x < p.x;

        return y < p.y;
    }

    bool operator == (const Point& p) const {
        return sgn(x - p.x) == 0
            && sgn(y - p.y) == 0;
    }
};

using Vector = Point;

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

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

db cross(Point O, Point A, Point B) {
    return cross(A - O, B - O);
}

db len2(Vector a) {
    return dot(a, a);
}

db len(Vector a) {
    return sqrt(len2(a));
}

db dist(Point a, Point b) {
    return len(a - b);
}

Vector normalize(Vector a) {
    return a / len(a);
}

Vector rotate90(Vector a) {
    return {-a.y, a.x};
}

Vector rotate(Vector a, db theta) {
    return {
        a.x * cos(theta) - a.y * sin(theta),
        a.x * sin(theta) + a.y * cos(theta)
    };
}

bool onSegment(Point p, Point a, Point b) {
    return sgn(cross(b - a, p - a)) == 0
        && sgn(dot(p - a, p - b)) <= 0;
}

Point projection(Point P, Point A, Point B) {
    Vector v = B - A;

    db t = dot(P - A, v) / dot(v, v);

    return A + v * t;
}

Point lineIntersection(Point P, Vector v,
                       Point Q, Vector w) {
    Vector u = P - Q;

    db t = cross(w, u) / cross(v, w);

    return P + v * t;
}

db triangleArea(Point A, Point B, Point C) {
    return fabs(cross(B - A, C - A)) / 2.0;
}

db polygonArea(vector& p) {
    int n = p.size();

    db ans = 0;

    for (int i = 0; i < n; i++) {
        ans += cross(p[i], p[(i + 1) % n]);
    }

    return fabs(ans) / 2.0;
}

int pointInPolygon(Point p, const vector& poly) {
    int n = poly.size();

    int wn = 0;

    for (int i = 0; i < n; i++) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];

        if (onSegment(p, a, b))
            return 1;

        if (a.y <= p.y && b.y > p.y) {
            if (sgn(cross(b - a, p - a)) > 0)
                wn++;
        }
        else if (a.y > p.y && b.y <= p.y) {
            if (sgn(cross(b - a, p - a)) < 0)
                wn--;
        }
    }

    return wn == 0 ? 0 : 2;
}

---

总结

二维计算几何中最基础、最重要的两个运算是：

点积

主要用于：

• 夹角；
• 垂直；
• 投影。

叉积

主要用于：

• 判断方向；
• To-Left；
• 判断共线；
• 面积；
• 线段相交；
• 多边形相关问题。

把点积、叉积和 Point / Vector 基础结构熟练掌握后，后面的直线、线段和多边形问题都会容易很多。

__EOF__