java - 分离 Axis 定理

我正在努力解决这个问题，而我一直在寻找一整天！

我想我了解其背后的主要概念，但是我正在努力弄清楚我需要创建数学模型以将形状投影到其上的轴吗？

因此，如果我有一个矩形，则找出每个点，然后使用它们找到形状edge = v(n) - v(n-1)的一面并遍历所有面。

但是我不知道如何创建分离轴。

最佳答案

该定理不难理解：如果找到一条线，形状A的所有点都在一侧，形状B的所有点都在另一侧（点积为正或负），则该线将形状。

你想让我做什么？查找任意形状的分隔线？

我建议看一下投影几何，因为扩展到无穷大的多边形的两个顶点的边缘可以用两个顶点（x，y，1）的叉积表示。对于凸多边形，您可以简单地为所有边创建线，然后取其他多边形的所有顶点的点积来检查它们在哪一侧。如果一条边的所有点都在外面，则该边就是一条分隔线。

还请记住，通过使线归一化，您可以使用点积获得点到线的距离。该标志标识该点所在的一侧。

如果您的问题更加困难，请更详细地说明。也许您可以使用某种剪裁来快速解决它。

示例：射影几何

public double[] e2p(double x, double y) {
    return new double[] { x, y, 1 };
}

// standard vector maths
public double[] getCrossProduct(double[] u, double[] v) {
    return new double[] { u[1] * v[2] - u[2] * v[1],
            u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0] };
}

public double getDotProduct(double[] u, double[] v) {
    return u[0] * v[0] + u[1] * v[1] + u[2] * v[2];
}

// collision check
public boolean isCollision(List<Point2D> coordsA, List<Point2D> coordsB) {
    return !(isSeparate(pointsA, pointsB) || isSeparate(pointsB, pointsA));
}

// the following implementation expects the convex polygon's vertices to be in counter clockwise order
private boolean isSeparate(List<Point2D> coordsA, List<Point2D> coordsB) {
    edges: for (int i = 0; i < coordsA.size(); i++) {
        double[] u = e2p(coordsA.get(i).getX(), coordsA.get(i).getY());
        int ni = i + 1 < coordsA.size() ? i + 1 : 0;
        double[] v = e2p(coordsA.get(ni).getX(), coordsA.get(ni).getY());
        double[] pedge = getCrossProduct(u, v);
        for (Point2D p : coordsB) {
            double d = getDotProduct(pedge, e2p(p.getX(), p.getY()));
            if (d > -0.001) {
                continue edges;
            }
        }
        return true;
    }
    return false;
}