如何在轴上投影多边形

Question

我正在学习分离轴定理，因为我正在制作一个简单的2D游戏，需要这种方法来检测两个多边形是否相交。

问题是，我的数学很差。

到目前为止，我明白了要想知道两个多边形是否相交，我需要执行以下步骤：

1.对于两个多边形的每条边创建一条垂线。 2.将每个多边形投影到新创建的每条线（轴）上。

如果第一个多边形的所有投影都与第二个多边形的所有投影重叠，则形状相交。否则，形状不相交。

我认为我理解了如何执行步骤1。但我不明白如何执行步骤2。

我该如何将多边形投影到轴上？请用我可以理解的语言解释这一点，因为我对数学的基本知识掌握得比较基础。虽然我学过一些数学概念，如点积和向量，但只是基础水平。所以你可以使用这些术语与我交流。

理论解释很好，但在代码中实现的示例（最好是Java）也会受到欢迎。

感谢您的帮助。非常感谢。

- user3150201

---

这是一个有用的教程：http://www.codezealot.org/archives/55 - gtgaxiola

点在多边形内算法可能会满足您的需求。您只需要知道是否有一个顶点在另一个多边形内即可。嗯...除非其中一个与一条线相交。 - Felix Castor

如果没有多边形完全包含在另一个多边形内的情况，你可能可以只检查一个多边形中的任何一条线段是否与另一个多边形中的任何一条线段相交。 - Cruncher

@Felix Castor 不是这样的。考虑顶点为（10，0）（10，10），（11，0）的三角形和顶点为（12，5），（12，6），（3，6）的三角形。它们相交，但没有一个角落在另一个三角形中。 - Daniel Martin

你是说可能存在这样一种情况，即一个矩形没有顶点在另一个矩形内，但它们确实相交。但是否可能存在这样一种情况，即两个矩形都没有顶点在彼此内部，但它们相交？ - user3150201

Answer 1

看一下两个向量的标量乘法：

(A ⋅ B) = |A| ⋅ |B| ⋅ cos(a);

• A, B 是向量。
• a 是 A, B 之间的夹角。

因此，如果要将 A 投影到 B 上并计算其大小，则结果为 C：

|C| = |A| ⋅ cos(a);
|C| = (A ⋅ B) / |B|;

如果您不熟悉公式或符号，那么：

|B| = sqrt((B.x)² + (B.y)² + (B.z)² + ...);
A ⋅ B = (A.x ⋅ B.x) + (A.y ⋅ B.y) + (A.z ⋅ B.z) + ...;

现在，只需将所有线条投影为向量，如下所示：

x0 = ((L0 - A0) ⋅ (A1 - A0)) / |(A1 - A0)|;
x1 = x0 + ((L1 - L0) ⋅ (A1 - A0)) / |(A1 - A0)|;

[注]

如果将轴向量(A1 - A0)设置为单位... |A| = 1，那么您可以忽略热量/ |(A1 - A0)|，这样可以大大提高速度。

- Spektre