如何判断两个扇形是否重叠

Question

每个扇区可以表示为（x，y，r，a，d），其中x，y是位置，r是半径，d是方向，a是角度。给定两个圆形扇区的这些信息，如何确定它们是否相互重叠？有没有什么高效的算法来解决它？谢谢！

Answer 1

因为我们有圆形扇区，所以角度和方向不重要，如果你实时这样做。以下内容仅适用于整圈扇区，或者如果两个扇区相互指向。

您可以按照以下步骤操作：

1）求出每个扇区之间的距离，2）将两个半径减去该距离，3）如果结果为负数，则两个扇区之间发生了碰撞。否则，它是碰撞的距离。

例如，我们有两个扇区，半径均为 50 个单位。它们的中心点之间的距离为 80。减去 80-50-50 = -20，所以你知道发生了 20 个单位的碰撞。

否则，如果距离为 500，则 500-50-50 = 400，这是一个正值，现在您知道这两个扇区相距 400 个单位。

现在，如果圆太近，比如说，相隔1个单位，1-50-50=-99，这意味着它们几乎完全重叠。

对于您在注释中指定的真正分段圆形扇区，您应该使用paxdiablos或Macs答案。

Answer 2

有两个步骤。首先是计算出两个中心是否足够接近以允许碰撞，这可以通过比较它们之间的距离和它们的半径之和来完成:

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) > ((r1 + r2) * (r1 + r2)))
    // No collision.

然后，您需要检查中心之间的线是否落在由您的各种角度定义的弧线内：

float angle1to2 = Math.atan2(y2 - y1, x2 - x1);
if (angle1to2 < (d1 - a1/2) || angle1to2 > (d1 + a1/2))
    // No collision
float angle2to1 = angle1to2 + Math.PI;
if (angle2to1 < (d2 - a2/2) || angle2to1 > (d2 + a2/2))
    // No collision

如果您通过了这些检查而没有排除碰撞的可能性，那么您就成功地检测到了碰撞。

警告:这段代码根本没有经过测试。特别是，< code>atan2调用可能需要一些调整，具体取决于您的坐标系。

编辑：刚刚意识到这错过了一个重要的拐角案例，其中弧不是“指向”彼此，而是仍然重叠。将对此深思并返回。。。

Answer 3

我知道一种非常快速的方法来打折这种可能性，因为我以前曾将其用于圆圈碰撞。

计算出两个中心之间的距离，如果大于半径之和，就不会发生碰撞。为了提高效率，不要使用平方根，只需直接计算平方值：

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (r1 + r2) * (r1 + r2):
    # No chance of collision.

圆段的计算会有点困难。

您选择的方法取决于您需要它有多精确。如果你在做实际的数学计算，你可能需要高精度。但是，举例来说，如果你是为了像电脑游戏这样的东西，足够近可能就足够好了。

如果是这样的话，我会考虑将弧线转换为一系列直线（其数量可能取决于弧线的“扩散” - 你可能会用几条线来扩展一度弧度，但这对于 180 度不太有效）。

直线冲突检测是一种更广为人知的方法，尽管您必须处理比较数量可能会迅速增加的事实。

如果你不想使用线段，那么下面是要遵循的过程。它使用一种圆碰撞算法来找出完整圆的零点、一点或两点碰撞，然后检查这些点以查看它们是否在两个圆弧内。

首先，运行上面的检查以检测不可能发生碰撞的情况。如果圆之间不可能发生碰撞，那么圆弧也不会发生碰撞。

其次，检查圆是否有单个碰撞点。如果：

(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) == (r1 + r2) * (r1 + r2)

当然在合适的误差范围内。我们现在都应该知道，比较浮点数是否相等应该使用某种增量比较。

如果是这种情况，您有一个点要检查，您可以很容易地找到该点。它是沿着从（x1， y1）到（x2， y2）的直线上的点r1单位，或者，将其视为沿着该线移动一些分数：

(x1 + (x2-x1) * (r1+r2) / r1, y1 + (y2-y1) * (r1+r2) / r1)

否则，有两点需要检查，你可以用这个问题的答案来确定这两点是什么。

一旦你有了一些碰撞点，这是一个更简单的方法来确定这些点是否在一条弧上，记住候选点需要在两条弧上才能碰撞，而不仅仅是在一条上。