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，圆弧的“展开”——你对于 1 度的弧度，可以使用几条线来解决问题，但对于 180 度的弧度来说效果不太好)。

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

---

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

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

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

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

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

如果是这样的话，你有一个点要检查，你可以很容易地找出那个点。它是沿着从 (x1,y1) 到 (x2,y2) 的直线上的点 r1 单位，或者，将其视为移动沿着这条线的一些分数:

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

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

一旦你有了一些碰撞点，它就是一个 much simpler method找出这些点是否在一条弧上，请记住，候选点需要在两条弧上才能发生碰撞，而不仅仅是在一条弧上。