碰撞检测 SAT算法 C++代码

SAT算法（Separating Axis Theorem）是一种常用的碰撞检测算法，可以用于检测凸多边形、圆形等物体之间的碰撞。以下是一个SAT算法的C++代码示例：

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Point {
    double x, y;

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

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

    double dot(const Point &p) const {
        return x * p.x + y * p.y;
    }

    double det(const Point &p) const {
        return x * p.y - y * p.x;
    }
};

struct Line {
    Point p;
    Point v;

    Line(Point p1 = Point(), Point p2 = Point()) : p(p1), v(p2 - p1) {}
};

struct Polygon {
    int n;
    vector<Point> p;

    Polygon(int n = 0) : n(n) {
        p.resize(n);
    }

    double area() const {
        double s = 0;
        for (int i = 0; i < n; ++i) {
            s += p[i].det(p[(i + 1) % n]);
        }
        return s / 2;
    }

    Point center() const {
        double cx = 0, cy = 0;
        for (int i = 0; i < n; ++i) {
            cx += p[i].x;
            cy += p[i].y;
        }
        return Point(cx / n, cy / n);
    }

    void normalize() {
        Point c = center();
        sort(p.begin(), p.end(), [&](const Point &a, const Point &b) {
            return atan2(a.y - c.y, a.x - c.x) < atan2(b.y - c.y, b.x - c.x);
        });
    }

    vector<Line> get_lines() const {
        vector<Line> lines(n);
        for (int i = 0; i < n; ++i) {
            lines[i] = Line(p[i], p[(i + 1) % n]);
        }
        return lines;
    }
};

bool overlap(const Line &l1, const Line &l2) {
    double c1 = (l2.p - l1.p).det(l1.v);
    double c2 = (l2.p + l2.v - l1.p).det(l1.v);
    if (c1 * c2 > 0) {
        return false;
    }
    c1 = (l1.p - l2.p).det(l2.v);
    c2 = (l1.p + l1.v - l2.p).det(l2.v);
    if (c1 * c2 > 0) {
        return false;
    }
    return true;
}

bool overlap(const Polygon &A, const Polygon &B) {
    auto lines1 = A.get_lines();
    auto lines2 = B.get_lines();
    for (auto &l1 : lines1) {
        for (auto &l2 : lines2) {
            if (!overlap(l1, l2)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    Polygon A(3);
    A.p[0] = Point(0, 0);
    A.p[1] = Point(1, 0);
    A.p[2] = Point(0, 1);
    Polygon B(3);
    B.p[0] = Point(1, 1);
    B.p[1] = Point(2, 1);
    B.p[2] = Point(1, 2);
    A.normalize();
    B.normalize();
    cout << (overlap(A, B) ? "Overlap" : "Not overlap") << endl;
    return 0;
}

上述代码定义了三个结构体：`Point`表示二维点，`Line`表示直线，`Polygon`表示多边形。其中，`Polygon`中的`get_lines()`函数可以返回多边形的每条边所对应的直线。

`overlap()`函数用于判断两个物体是否重叠，它通过遍历两个物体的每一条边，使用`overlap(const Line &l1, const Line &l2)`函数检查这两条边是否重叠。如果有任意一组边不重叠，则两个物体不重叠。