LeetCode 热题 100 精讲 | 计算几何篇：点积叉积 · 线段相交 · 凸包 · 多边形面积

计算几何篇介绍了四个基础模块：点积叉积、线段相交判断、凸包算法、多边形面积。这些工具是解决更复杂几何问题（如最近点对、旋转卡壳、半平面交等）的基石。面试中虽然直接考察计算几何的题目不多，但点积和叉积的应用（如判断点是否在矩形内、求点到直线的距离）偶尔会出现。掌握这些基础，遇到几何问题就能从容应对。下一篇将进入字符串匹配篇（KMP、Boyer-Moore、Rabin-Karp、AC 自动机），敬请期

木子墨516

100人浏览 · 2026-04-20 13:15:00

木子墨516 · 2026-04-20 13:15:00 发布

一、点积与叉积

📝 核心概念

计算几何的基础是向量运算。点积（Dot Product）和叉积（Cross Product）是两大基石。

点积：a·b = |a||b|cosθ，几何意义是一个向量在另一个向量上的投影长度乘以另一个向量的模。可用于判断两个向量的夹角：点积 > 0 为锐角，= 0 为直角，< 0 为钝角。公式：a·b = x1*x2 + y1*y2。

叉积：a×b = |a||b|sinθ，几何意义是由 a 和 b 构成的平行四边形的有向面积。二维叉积是标量，正值表示 b 在 a 的逆时针方向，负值表示顺时针方向。公式：a×b = x1*y2 - y1*x2。叉积在判断点在线段的哪一侧、判断线段是否相交等问题中至关重要。

💻 代码实现（C++）

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

typedef Point Vector;

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

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

📚 相关学习资源

文章：叉积和点积学习笔记（CSDN）—— 包含点积、叉积的几何意义表格、C++代码和三角形面积计算，是入门计算几何的好文章。
文章：计算几何 - all_for_god（博客园）—— 从向量定义、叉积几何意义到直线/线段的距离、垂足等完整讲解，适合系统学习。

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

二、判断线段是否相交

📝 核心概念

给定两条线段 AB 和 CD，判断它们是否相交。相交分为规范相交（交点在内部）和非规范相交（交点在端点）。常用方法：跨立实验。对于线段 AB 和 CD，需要满足两个条件：点 C 和 D 分别在 AB 的两侧（叉积 cross(A,B,C) 与 cross(A,B,D) 异号），同时点 A 和 B 分别在 CD 的两侧。还需要处理端点重合的情况。如果两条线段共线且投影重叠，也算相交。

💻 代码实现（C++）

bool onSegment(Point p, Point a, Point b) {
    // 判断点 p 是否在线段 ab 上（包含端点）
    return cross(a - p, b - p) == 0 && 
           min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    double d1 = cross(b - a, c - a);
    double d2 = cross(b - a, d - a);
    double d3 = cross(d - c, a - c);
    double d4 = cross(d - c, b - c);
    if (d1 * d2 < 0 && d3 * d4 < 0) return true;
    if (d1 == 0 && onSegment(c, a, b)) return true;
    if (d2 == 0 && onSegment(d, a, b)) return true;
    if (d3 == 0 && onSegment(a, c, d)) return true;
    if (d4 == 0 && onSegment(b, c, d)) return true;
    return false;
}

📚 相关学习资源

暂无

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

三、凸包算法（Andrew 算法）

📝 核心概念

凸包（Convex Hull）是包含所有点的最小凸多边形。Andrew 算法时间复杂度 O(n log n)，步骤：先按 x 坐标（然后 y）排序；分别构造下凸壳和上凸壳。从左到右扫描构造下凸壳，用栈维护，保证每三个连续点是逆时针转向（叉积为正）；然后从右到左扫描构造上凸壳。最后合并，注意首尾重复点。

💻 代码实现（C++）

vector<Point> convexHull(vector<Point>& pts) {
    int n = pts.size();
    if (n <= 1) return pts;
    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    vector<Point> hull;
    // 下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && 
               cross(hull.back() - hull[hull.size()-2], pts[i] - hull.back()) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    // 上凸壳
    int lowerSize = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lowerSize && 
               cross(hull.back() - hull[hull.size()-2], pts[i] - hull.back()) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back(); // 移除重复的起点
    return hull;
}

📚 相关学习资源

文章：Andrew算法（求凸包）（CSDN）—— 从排序、下凸包、上凸包到去重闭合，全流程配有图解和代码，新手友好。
文章：二维凸包——Andrew 算法学习笔记（CSDN）—— 用洛谷模板题讲解，包含“皮筋模型”比喻、凹多边形判断和完整的求凸包及周长代码。

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

四、计算多边形面积（鞋带公式）

📝 核心概念

给定多边形顶点按逆时针或顺时针顺序排列（不要求凸多边形），面积可以用鞋带公式（Shoelace formula）计算。公式：area = 1/2 * |Σ (x_i*y_{i+1} - x_{i+1}*y_i)|。这个公式本质上是叉积之和的一半。注意顶点要按顺序给出，最后一个点要回到第一个点。

💻 代码实现（C++）

double polygonArea(vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
    }
    return fabs(area) / 2.0;
}