java - 分离 Axis 定理

Question

我正在努力解决这个问题 - 我实际上已经找了一整天了!

我想我理解它背后的主要概念，但我正在努力弄清楚创建将形状投影到其上的 Axis 所需的数学？

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

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

Answer 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;
}