每个扇区可以表示为(x,y,r,a,d),其中x,y是位置,r是半径,d是方向,a是角度.鉴于这两个圆形扇区的信息,如何确定它们是否相互重叠?
有没有任何有效的算法来解决它?谢谢!
有没有任何有效的算法来解决它?谢谢!
解决方法
我知道一个非常快速的方法来折扣的可能性,因为我以前用于圆圈碰撞.
找出两个中心之间的距离,然后,如果大于半径的总和,就不会发生碰撞.为了效率,不要使用平方根,只需直接在平方值上工作:
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)
否则,有两点要检查,你可以使用一个像this one这样的问题的答案来确定这两点.
一旦你有一些碰撞点,这是一个much simpler method,找出这些点是否在一个弧上,请记住,候选点将需要在两个弧上,以使它们相互冲突,而不仅仅是一个.