如何确定两个圆形扇形是否重叠？

Question

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

- wzb5210

---

你不需要“两个”角度来完全指定一个圆弧吗？起始角度和结束角度？ - paxdiablo

起始角度为(d-a/2)，结束角度为(d+a/2)。 - wzb5210

啊，好了。所以 d 是一个角度（线段的“中心”），而 a 是线段的“展开”。从描述来看，d 看起来是一个简单的顺时针/逆时针指示器。 - paxdiablo

最坏的情况是如果没有其他更好的方法：它们只有在一个完全包含另一个内部，或者它们的边缘相交时才相交。因此，您可以计算许多“点在部分中的成员资格”和“直线段和/或圆弧段之间的交点”。所有这些都很繁琐。 - Steve Jessop

如果我们能确定指定点应该移动到哪里才能进入扇形的函数，我们可以使用二分查找来确定两个扇形中是否存在公共点。我已经尝试了一段时间，但没有成功。也许三点行列式可能是一个好的方法。 - batbaatar

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)

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

如果是这样，你只需要检查一个点，就可以轻松找出那个点。它是沿着从 (x1,y1) 到 (x2,y2) 的直线上移动 r1 单位的点，或者看作是沿着那条直线的一定分数移动：

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

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

一旦您有了一些碰撞点，就可以使用更简单的方法来找出这些点是否在弧上，记住候选点需要在两个弧上才能发生碰撞，而不仅仅是一个。

- paxdiablo

---

是的，字符串比弧线更容易。不过，我仍然更喜欢在数学上证明它。非常感谢。 - wzb5210

这个答案适用于所有情况吗？例如，当一个扇区完全在另一个扇区内部时。或者当两个扇区的弧不相交，但是从它们的“锥顶”到“弧端点”的线段相交时。看起来这个答案取决于沿弧的碰撞点。扇区可以重叠而不会出现这种情况。 - Scott Lin

@Scott，我是从游戏视角出发，假设物体是分开的，然后相互碰撞。你说得对，这种方法无法检测到完全包含的情况。关于“只检测弧形碰撞”，我或许应该更清楚地表达，中心到边缘的线也应该被检查，而不仅仅是弧线。我会澄清这一点的。 - paxdiablo

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调用可能需要根据您的坐标系统进行一些微调。

编辑：刚刚意识到这个代码漏掉了一个重要的角落情况，即弧不是“指向”彼此但仍然重叠。将考虑这一点并返回...

- Mac

---

不确定这是否正确，但这个想法很好。谢谢！我会尝试从这个方向思考问题。 - wzb5210

在我的编辑基础上，我意识到我的方法可能根本不起作用。我有一种感觉，两个中心之间的线可能根本不相关 - 如果我想出了新的东西，我会回来告诉你，但否则请暂时忽略我的答案。 - Mac

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的答案。

- Basilio German

---

那对于整个圆来说是有效的，但不一定适用于圆弧。想象一下两个相距一单位的10单位圆。虽然圆本身会碰撞，但最外侧（最远离另一个圆半径的）的圆弧却不会碰撞。 - paxdiablo

但问题说明了圆弧段，并检查它们是否重叠。顺便说一下，你的答案有一个很好的实现。 - Basilio German

如果它们面向相反的方向，即使它们的中心点距离只有1个单位，它们也不能重叠。 - wzb5210

这个解决方案对于圆形是正确的，但对于扇形不正确，对吗？ - wzb5210

只有当该部门是一个完整的圆时，才返回true。 - Basilio German

圆形很容易。那扇形呢，不用整个圆形，行不行？ - wzb5210