如何找到两个矩形的碰撞中心？这些矩形可以旋转。

Question

如何找到两个矩形的碰撞中心？这些矩形可以旋转。

algorithmmathpolygon

8

我刚刚使用SAT实现了碰撞检测，并参考了这篇文章。检测的效果符合预期，但我需要知道两个矩形的碰撞位置。

我需要找到交点的中心（上面图片中的黑点，但我没有交叉区域）。我找到了一些相关文章，但它们都涉及避免重叠或某种速度，我不需要这些。

我拥有关于矩形的四个点的信息，它们表示矩形的右上角、左上角、右下角和左下角坐标。我正在尝试找到一个算法，可以给出这些点的交点。

我只需要在它之上放一张图片，比如两辆车相撞，所以我要把一张图片放到碰撞中心。有什么想法吗？

- Felipe Cypriano

1

获取交点的一种可能方法是构造闵可夫斯基差异并查看点（0,0）。这适用于任意多边形，但对于您的问题可能过于复杂。请查看此[页面+交互式示例]（http://physics2d.com/content/gjk-algorithm）。（特别是闵可夫斯基差异部分。）很抱歉我现在时间不充裕，无法提供具体帮助。 - TaZ

如果我理解正确的话，闵可夫斯基差（或GJK算法）将告诉我多边形是否发生了碰撞。它在哪里告诉我碰撞点呢？ - Felipe Cypriano

4个回答

3

你需要使用线到线交点公式/算法对框的边界进行交集运算。

http://en.wikipedia.org/wiki/Line-line_intersection

一旦您找到相交点，可能会满足于这些点的平均值或者在特定方向上给出的中心点。问题中关于中心点的描述有些含糊不清。

编辑：此外，您还需要确定两个矩形的任何一个角是否位于另一个矩形内部（即使从相交处计算，也应该很容易确定）。在计算“平均”中心点时，应将此添加到相交点中。

- ceorron

2

这个有点棘手，因为不规则多边形没有定义的中心点。对于矩形这样的凸多边形，您可能可以找到组成碰撞的多边形的角落（可以包括原始形状的角落或边缘的交点），并对它们取平均值以得到...某些东西。它可能会大致接近您期望的“中心”位置，并且对于正规多边形，它可能完全匹配，但它是否在数学上有意义是一个有点不同的故事。

我一直在进行数学推导，得出以下结论，解决了当点消失和出现时（当碰撞框的移动导致矩形变成三角形或反之亦然时）平滑性问题。如果没有这个额外的部分，添加和删除角落将导致重心跳跃。

这里，拿着这个fooplot。

这段文字描述了两个矩形，一个红色的R和一个蓝色的B。它们的交集形成了一个绿色的区域G。通过以下方法计算出了未加权和加权中心（均为紫色）。

(0.225, -0.45):   Average of corners of G
(0.2077, -0.473): Average of weighted corners of G

一个多边形的加权角被定义为角度的正弦加权的角坐标。

这个多边形有两个90度的角，一个59.03度的角和一个120.96度的角。(两个非直角角度的正弦值相同，sin(Ɵ) = 0.8574929...)

因此，加权中心的坐标是：

( (sin(Ɵ) * (0.3 + 0.6) + 1 - 1)   / (2 + 2 * sin(Ɵ)),  // x
  (sin(Ɵ) * (1.3 - 1.6) + 0 - 1.5) / (2 + 2 * sin(Ɵ)) ) // y
= (0.2077, -0.473)

通过提供的例子，差别并不是很明显，但如果4边形更接近一个三角形，就会有显著的偏差。

- Wug

我理解他是在要求整个区域，而不仅仅是中心点。如果是这种情况，第一幅图就会误导人。 - Zev Eisenberg

1

我需要找到交叉点的中心，即上面图像中的黑点。 - Wug

啊，那样的话我误解了问题。 - Zev Eisenberg

实际上我需要中心点（或接近中心点的点），但我没有交集区域。目前我只有每个矩形的四个点，并且我知道它们是否相撞。 - Felipe Cypriano

进行一些数学计算以确定交点，然后进行一些逻辑推理以确定您获得的点中哪些是相交区域的边界。 - Wug

这就是我想要做的。我并没有说你的回答是错误的，我只是在澄清我所处的阶段。我认为这里的每个回答都在帮助我找到达成目标的方法。 - Felipe Cypriano

0

如果您不需要知道区域的实际坐标，可以创建两个CALayer，它们的框架是矩形，并使用一个来遮罩另一个。然后，如果您在被遮罩的图层中设置图像，则它只会显示在它们重叠的区域。

- Zev Eisenberg

有没有办法确定重叠区域的中心，以便告诉CALayer在哪里放置图像？ - Phssthpok

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- daniloquio · Accepted Answer

还有另一种方法：通过抽样点找到碰撞区域的质心。

创建以下函数：

bool IsPointInsideRectangle(Rectangle r, Point p);

将搜索矩形定义为：

TopLeft = (MIN(x), MAX(y))
TopRight = (MAX(x), MAX(y))
LowerLeft = (MIN(x), MIN(y))
LowerRight = (MAX(x), MIN(y))

x和y分别是两个矩形的坐标。

现在，您需要定义一步来将搜索区域划分为网格。我建议您使用AVG（W，H）/ 2，其中W和H是搜索区域的宽度和高度。

然后，您可以在网格点上进行迭代，查找每个点是否在碰撞区域内：

IsPointInsideRectangle(rectangle1, point) AND IsPointInsideRectangle(rectangle2, point)

定义：

Xi : the ith partition of the mesh in X axis.
CXi: the count of mesh points that are inside the collision area for Xi.

然后：

enter image description here

当然，您也可以使用同样的方法处理 Y。以下是这种方法的一个示例：

enter image description here