C++计算几何算法实战指南（从零开始掌握计算几何核心技巧）

准备工作：定义基本数据结构

在开始写算法前，我们需要定义点（Point）和向量（Vector）的基本结构。以下是我们将使用的C++结构体：

#include <iostream>#include <cmath>using namespace std;const double EPS = 1e-9; // 浮点数精度误差容忍值struct Point {    double x, y;        Point() : x(0), y(0) {}    Point(double x, double y) : x(x), y(y) {}        // 向量加法    Point operator + (const Point& p) const {        return Point(x + p.x, y + p.y);    }        // 向量减法    Point operator - (const Point& p) const {        return Point(x - p.x, y - p.y);    }        // 数乘    Point operator * (double k) const {        return Point(x * k, y * k);    }};

核心工具：叉积（Cross Product）

叉积是C++几何编程中最常用的工具之一。给定两个向量 a 和 b，它们的叉积为 a.x * b.y - a.y * b.x。叉积的正负可以判断两个向量的相对方向（顺时针或逆时针）。

// 计算叉积double cross(const Point& a, const Point& b) {    return a.x * b.y - a.y * b.x;}// 判断点c是否在向量ab的左侧（逆时针方向）bool isLeft(const Point& a, const Point& b, const Point& c) {    return cross(b - a, c - a) > EPS;}

实战案例：判断点是否在线段上

这是一个经典问题。我们可以通过两个条件判断：

1. 点P、A、B三点共线（叉积为0）
2. 点P在A和B的包围盒内（即x和y坐标都在A和B之间）

// 判断点p是否在线段ab上bool onSegment(Point a, Point b, Point p) {    // 首先检查是否共线    if (fabs(cross(b - a, p - a)) > EPS)         return false;        // 检查p是否在a和b的包围盒内    double minX = min(a.x, b.x), maxX = max(a.x, b.x);    double minY = min(a.y, b.y), maxY = max(a.y, b.y);        return (p.x >= minX - EPS && p.x <= maxX + EPS &&            p.y >= minY - EPS && p.y <= maxY + EPS);}

完整示例：运行测试

下面是一个完整的可运行程序，演示如何使用上述函数：

int main() {    Point A(0, 0), B(4, 4), P(2, 2);        if (onSegment(A, B, P)) {        cout << "点P在线段AB上" << endl;    } else {        cout << "点P不在线段AB上" << endl;    }        Point Q(5, 5);    if (isLeft(A, B, Q)) {        cout << "点Q在AB左侧" << endl;    } else {        cout << "点Q不在AB左侧" << endl;    }        return 0;}

小结与进阶建议

通过本教程，你已经掌握了小白学计算几何的第一步！我们学习了如何定义点、使用叉积、判断点是否在线段上等基础操作。下一步你可以尝试实现：

• 两线段是否相交
• 多边形面积计算
• 凸包算法（如Graham扫描）

记住，计算几何的关键在于理解几何关系并将其转化为代数运算。多练习、多画图，你会越来越熟练！