圆与圆段的碰撞

9
我很难找到一个确切的解决方案来检测圆与圆弧之间的碰撞。想象一个游戏敌人的视野锥形,圆表示感兴趣的对象。
底部的图表是我绘制的,试图找出一些可能的情况,但我确定还有更多。
我知道如何快速排除极端情况,丢弃任何与整个圆不发生碰撞的目标,以及主圆的中心在目标圆内部的任何情况均自动为真(图中的E)。
我很难找到一种好的方法来检查其余情况。我已经尝试比较圆心与线段外线的端点之间的距离,并尝试计算目标圆的中心相对于主圆的中心的角度,并确定是否在弧线段内,但两种方法似乎都无法捕获所有情况。
具体而言,如果目标圆靠近中心但没有接触它(在下面的E和B之间),或者如果片段比目标圆小(因此中心在片段内,但两侧都在片段外),则它似乎会出错。
有可靠的方法吗?
额外信息:该段由位置P、方向O(其大小是圆半径)和视图大小S描述。
迄今为止,我最成功的尝试涉及确定向量ca1和ca2的角度,并检查它们中的任何一个是否位于向量a1和a2的角度之间。这适用于上述某些情况,但不适用于目标圆大于片段的情况。
编辑2:在实施下面的最佳建议后,仍存在一种错误的正面情况,我不确定如何最好地消除它。见下面的粉色图表。右下角的圆报告与段碰撞,因为它的边界重叠了两个半空间和主圆。
最终编辑:
发现另一个边缘情况(第四张图片)后,我采用了一种方法,将下面的两个顶部答案结合起来,似乎覆盖了所有基础。我会在这里描述它,以便那些跟随的人。
首先排除失败快速圆形测试的任何内容。
然后测试圆形与片段的两条外线之间的碰撞。如果接触任一方,则返回true。
最后,使用圆形的中心和两条外线进行几个点对半空间测试(如Gareth所述)。如果通过这两个测试,则为真,否则返回false。
2个回答

5

A. 检查它是否与整个圆相交。
B. 检查它是否与直线段之一相交。
C. 如果没有相交,检查圆心之间的角度是否在该段的角度范围内(点积可用于此)。

相交需要 A && (B || C)


啊,我甚至没有想到把线段的两侧看作是直线。这听起来就像是我知道自己缺失的简单答案 :) - beeglebug

4
一个圆弧(中心角小于180度)是三个图形的交集:一个圆和两个半平面:
所以一个图形只有在它与这三个图形都相交时才与圆弧相交。圆/圆相交很容易(比较它们的中心之间的距离与它们的半径之和)。对于圆/半平面相交,用p · nk(其中p是要测试的点,n是垂直于定义半平面的线的单位向量,k是常数)来表示半平面。然后,如果x · nk + r,则以中心x和半径r的圆与半平面相交。
(如果需要处理中心角大于180度的圆弧,则将其分成两个中心角小于180度的圆弧。如果我正确理解您的问题描述,您不需要这样做,因为您的视野始终小于180度,但值得一提。)
编辑后添加:正如beeglebug指出的那样,一个圆可以与所有三个图形相交而不与它们的交集相交。糟糕。但我认为只有当圆在片段的中心后面时(如下图所示),这种情况才会发生,并且在这种情况下,我们可以使用凸形状的分离轴测试。
分离轴定理表明,如果存在一条直线,使得一个图形完全落在直线的一侧,而另一个图形完全落在另一侧,则两个凸形状将不相交。
如果在这种情况下存在任何分离轴,则垂直于圆心和片段中心之间的线的轴是分离轴(如图所示)。
让片段的中心位于原点,圆的中心为x,半径为r,两个半平面具有(向外)法线n₁n₂。如果 x · n₁ > 0 and x · n₂ > 0
则圆“在”片段后面,并且如果 |x| > r 则该轴将其与片段分开。

A circle failing to intersect a circular segment, with an axis shown separating them, with points, normals and radius marked


对不起,可能我太笨了,但是“k是一个常数”是什么意思? - beeglebug
如果n是垂直于一条直线的向量,那么如果你在该直线上选择任意一点p,则p·n(其中·是点积)始终相同-因此我在我的写作中称其为常数k。(如果您需要几何解释,则k是该直线到原点的垂直距离。)方程p·n=k然后定义了该直线:它对于线上的任何点都成立,并且对于远离该直线的点则不成立。 - Gareth Rees
由于半平面是由沿其边缘的线定义的,因此每个半平面也都有一个方程式:如果该线的方程式为p · n = k,则该半平面的方程式为p · nk。(或者对于另一个半平面为≥)。如果您正在编写视频游戏,那么了解一些向量几何知识是非常值得的! - Gareth Rees
非常感谢你的帮助,Gareth。我已经实现了你建议的方法,但遇到了另一个问题。紧挨在线段后面的圆可能会返回 true,因为它的外边缘穿过了两个半空间,但没有穿过线段本身。我添加了另一个图表来说明这个错误的结果。 - beeglebug
哎呀,有点尴尬。让我再试一次。 - Gareth Rees
发现了一个更特殊的情况(见上文),但最终找到了可行的解决方案。非常感谢您的帮助,我在这个过程中学到了很多有用的东西! :) - beeglebug

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接