8

我刚刚使用 SAT 实现了碰撞检测，这篇文章作为我的实现的参考。检测按预期工作，但我需要知道两个矩形在哪里发生碰撞。

我需要十字路口的中心 更多示例

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

我所掌握的关于矩形的信息是代表它们的四个点upper right、upper left、lower right和lower left坐标。我试图找到一种算法，可以给我这些点的交集。

我只需要在上面放一张图片。就像两辆车相撞一样，所以我在碰撞中心的顶部放了一张图片。有任何想法吗？

4

4 回答 4

3

您需要使用线对线相交方程/算法对框的边界进行相交。

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

一旦你有了交叉点，你可能会对这些点的平均值或给定特定方向的中心感到满意。中间的问题有点含糊。

编辑：除此之外，您还需要确定两个矩形中的任何一个的角是否在另一个内部（这应该很容易解决，即使是从交叉点）。在计算“平均”中心点时，这应该与交叉点一起添加。

于 2012-10-02T21:32:06.957 回答
3

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

创建以下函数：

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.

然后：

在此处输入图像描述

你也可以对 Y 做同样的事情。这是这种方法的一个说明性示例：

在此处输入图像描述

于 2012-10-03T16:53:51.930 回答
2

这很棘手，因为不规则多边形没有定义的中心。由于您的多边形（在矩形的情况下）保证是凸的，因此您可能会找到包含碰撞的多边形的角（可以包括原始形状的角或边缘的交叉点）并将它们平均得到 . .. 某物。它可能会模糊地接近您期望的“中心”位置，并且对于正多边形它可能会完全匹配，但它是否意味着数学上的任何东西有点不同。

我一直在数学上摆弄并提出以下问题，它解决了点出现和消失时的平滑度问题（当碰撞框的移动导致矩形变为三角形时会发生这种情况，反之亦然）。如果没有这些额外的东西，添加和删除角点会导致质心跳跃。

来，拿这个fooplot。

该图显示了 2 个矩形，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)

对于提供的示例，差异不是很明显，但如果 4gon 更接近 3gon，则会有很大的偏差。

于 2012-10-02T21:29:36.180 回答
0

如果您不需要知道该区域的实际坐标，您可以制作两个CALayer框架为矩形的 s，并使用一个来遮盖另一个。然后，如果您在被遮罩的图像中设置图像，它将仅显示在它们重叠的区域中。

于 2012-10-02T21:31:58.630 回答