java - 如何判断两个圆形扇区是否相互重叠

Question

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

Answer 1

我知道一种非常快速的方法来降低这种可能性，因为我以前用它来进行圆形碰撞。

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

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

为圆段计算会有点困难。

---

您选择的方法取决于您需要的准确度。如果你正在做实际的数学，你可能需要高精度。但是，例如，如果您正在为计算机游戏之类的东西这样做，那么足够接近可能就足够了。

如果是这种情况，我会考虑将弧线转换为一系列直线（其中的数量可能取决于a弧线的“扩展” - 你可能会用几条线来逃避一个弧度的传播，但对于 180 度来说效果不太好）。

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

---

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

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

其次，检查圆圈是否有一个碰撞点。如果是这样的话：

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

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

如果是这种情况，您有一点要检查，您可以很容易地找出那一点。它是沿从to orr1的直线上的点单位，将其视为沿该线移动一些分数：(x1,y1)(x2,y2)

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

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

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

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

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

警告：此代码根本没有经过测试。特别是，atan2调用可能需要根据您的坐标系进行一些调整。

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

Answer 3

由于我们有圆形扇区，因此如果您实时执行此操作，角度和方向并不重要。以下仅适用于全圆扇区，或者如果两个扇区相互指向。

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

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

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

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

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

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