2D 平面上的多边形：计算精确的位移以解决重叠问题

Question

我正在 2D 平面上处理具有俄罗斯方块式重力的多边形。每个多边形可以位于 X 轴上或位于另一个多边形的顶部。如果一个多边形与任何其他多边形重叠，则需要沿 Y 轴移动以解决重叠问题。

换班前：

换班后：

目标是找到向上移动多边形所需的精确最小向量（X坐标保持不变），以便它不再与其他向量重叠，同时保持俄罗斯方块重力效果。

一种方法可能是在循环中增量移动多边形，直到没有重叠。然而，我担心这可能效率低下。另外，我已经有了线性插值的公式，但我不确定如何在这种情况下应用它们，或者是否有更好的方法。任何计算向量的见解或方法将不胜感激！

Answer 1

与许多不涉及旋转的多边形与多边形问题一样（参见 GJK 算法 的典型示例），这里的一个有用工具是 Minkowski sum。您不是确定解决一个多边形与另一个多边形之间的穿透的平移，而是找到“其他多边形”和关于原点反射的目标多边形的 MS，并找到该结果之外的点。 MS之外的任何点都是合法的翻译，它解决了原始问题的渗透。

你的例子：

现在我们只需从原点向上扫描，寻找不在 MS 内部的第一个点。该点是解决穿透问题的最佳向上平移。

两个凸多边形的 Minkowski 和计算起来很简单，因此只需将每个“其他”多边形视为一个单独的 MS 并找到位于它们所有之外的第一个点。这涉及到找到原点的嵌入深度（即原点在多少个MS内），找到与+Y射线相交的所有MS边缘，对这些交叉点进行排序，然后向上遍历它们，当您输入一个 MS，并在离开 MS 多边形时减去 1，直到嵌入深度第一次变为 0。这就是解决方案。在这里，嵌入深度从 1 开始，在

y=0.75

左右变为 2，在

y=2.9

左右回到 1，然后在

y=3.3

左右变为 0。