您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ 計算幾何基礎庫：點、線段類封裝與核心幾何運算

編輯：關於C++

計算幾何是算法競賽與圖形應用的基礎。本文提供一個輕量級 C++ 幾何庫框架，封裝 Point、PartLine（線段），實現距離、叉積、相交判斷、旋轉、最近點、鏡像等核心運算，代碼結構清晰，可直接擴展。

核心類設計

Point：點/向量

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

    // 向量運算
    Point operator+(const Point& o) const { return Point(x+o.x, y+o.y); }
    Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); }
    Point operator*(double k) const { return Point(x*k, y*k); }
    Point operator/(double k) const { return Point(x/k, y/k); }

    // 模長與歸一化
    double len() const { return hypot(x, y); }
    Point unit() const { double l = len(); return l>0 ? Point(x/l, y/l) : Point(0,0); }

    // 內積、叉積
    double dot(const Point& o) const { return x*o.x + y*o.y; }
    double cross(const Point& o) const { return x*o.y - y*o.x; }

    // 距離、角度
    double dist(const Point& o) const { return (*this - o).len(); }
    double angle(const Point& o) const { return atan2(cross(o), dot(o)); }

    // 旋轉（逆時針 rad 弧度）
    Point rotate(double rad) const {
        return Point(x*cos(rad) - y*sin(rad), x*sin(rad) + y*cos(rad));
    }

    bool operator==(const Point& o) const {
        return fabs(x-o.x) < 1e-9 && fabs(y-o.y) < 1e-9;
    }
};

PartLine：線段

struct PartLine {
    Point a, b; // 端點
    PartLine() {}
    PartLine(Point a, Point b) : a(a), b(b) {}

    Point vec() const { return b - a; } // 方向向量
    double len() const { return a.dist(b); }

    // 點到線段距離（有向，帶符號）
    double signedDist(const Point& p) const {
        return vec().cross(p - a) / len();
    }

    // 判斷兩線段真相交（不含端點共線重疊）
    bool intersectProper(const PartLine& o) const {
        double d1 = vec().cross(o.a - a);
        double d2 = vec().cross(o.b - a);
        double d3 = o.vec().cross(a - o.a);
        double d4 = o.vec().cross(b - o.a);
        return d1*d2 < 0 && d3*d4 < 0; // 嚴格異號
    }

    // 判斷一般相交（含端點接觸、共線重疊）
    bool intersect(const PartLine& o) const {
        // 快速排斥
        if (max(a.x, b.x) < min(o.a.x, o.b.x) - 1e-9) return false;
        if (max(o.a.x, o.b.x) < min(a.x, b.x) - 1e-9) return false;
        if (max(a.y, b.y) < min(o.a.y, o.b.y) - 1e-9) return false;
        if (max(o.a.y, o.b.y) < min(a.y, b.y) - 1e-9) return false;
        // 跨立實驗
        double d1 = vec().cross(o.a - a);
        double d2 = vec().cross(o.b - a);
        double d3 = o.vec().cross(a - o.a);
        double d4 = o.vec().cross(b - o.a);
        if (d1*d2 < -1e-9 && d3*d4 < -1e-9) return true; // 真相交
        // 端點在線段上
        if (fabs(d1) < 1e-9 && onSegment(o.a)) return true;
        if (fabs(d2) < 1e-9 && onSegment(o.b)) return true;
        if (fabs(d3) < 1e-9 && o.onSegment(a)) return true;
        if (fabs(d4) < 1e-9 && o.onSegment(b)) return true;
        return false;
    }

    bool onSegment(const Point& p) const {
        return fabs(vec().cross(p - a)) < 1e-9 &&
               (p - a).dot(p - b) < 1e-9;
    }

    // 線段旋轉（繞 a 或 b）
    PartLine rotateA(double rad) const {
        return PartLine(a, a + vec().rotate(rad));
    }
    PartLine rotateB(double rad) const {
        return PartLine(b + (a - b).rotate(rad), b);
    }

    // 最近點（線段上到點 p 最近的點）
    Point nearestPoint(const Point& p) const {
        Point v = vec();
        double t = v.dot(p - a) / v.dot(v);
        if (t < 0) return a;
        if (t > 1) return b;
        return a + v * t;
    }

    // 交點（假設真相交）
    Point intersection(const PartLine& o) const {
        Point v1 = vec(), v2 = o.vec();
        double t = (o.a - a).cross(v2) / v1.cross(v2);
        return a + v1 * t;
    }
};

常用幾何判斷函數

// 點在線段上
bool onSegment(Point a, Point b, Point p) {
    return fabs((b-a).cross(p-a)) < 1e-9 && (p-a).dot(p-b) < 1e-9;
}

// 多邊形面積（鞋帶公式）
double polygonArea(const vector<Point>& poly) {
    double s = 0;
    for (int i = 0, n = poly.size(); i < n; ++i)
        s += poly[i].cross(poly[(i+1)%n]);
    return fabs(s) / 2;
}

// 凸包（Andrew 算法 O(n log n)）
vector<Point> convexHull(vector<Point> p) {
    sort(p.begin(), p.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    int n = p.size(), k = 0;
    vector<Point> h(2*n);
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && (h[k-1]-h[k-2]).cross(p[i]-h[k-1]) <= 0) --k;
        h[k++] = p[i];
    }
    for (int i = n-2, t = k+1; i >= 0; --i) {
        while (k >= t && (h[k-1]-h[k-2]).cross(p[i]-h[k-1]) <= 0) --k;
        h[k++] = p[i];
    }
    h.resize(k-1);
    return h;
}