圆到圆段碰撞 [英] Circle to Circle Segment Collision

问题描述

我正在努力寻找一种可靠的解决方案来检测圆和圆段之间的碰撞.想象一个游戏敌人的视野锥，圆圈代表感兴趣的对象.

I'm struggling to find a rock solid solution to detecting collisions between a circle and a circle segment. Imagine a Field of View cone for a game enemy, with the circles representing objects of interest.

底部的图表是我绘制的，试图找出一些可能的情况，但我相信还有更多.

The diagram at the bottom is something I drew to try and work out some possible cases, but i'm sure there are more.

我知道如何快速排除极端情况，我丢弃任何不与整个圆碰撞的目标，任何主圆的中心在目标圆内的情况都自动为真(图中的E).

I understand how to quickly exlude extreme cases, I discard any targets that don't collide with the entire circle, and any cases where the center of the main circle is within the target circle are automatically true (E in the diagram).

我正在努力寻找检查其余案例的好方法.我试过比较圆心和线段外线端点之间的距离，我试着计算出目标圆心与主圆心的角度，并确定它是否在线段内，但似乎两种方法都不能涵盖所有情况.

I'm struggling to find a good way to check the rest of the cases. I've tried comparing distances between circle centers and the end points of the segments outer lines, and i've tried working out the angle of the center of the target circle from the center of the main circle and determining whether that is within the segment, but neither way seems to catch all cases.

具体来说，如果目标圆靠近中心但不接触它(在下方 E 和 B 之间的某个位置)，或者如果线段比目标圆更窄(因此中心在线段内)，它似乎变得很时髦但两边都在它外面).

Specifically it seems to go funky if the target circle is close to the center but not touching it (somewhere between E and B below), or if the segment is narrower than the target circle (so that the center is within the segment but both edges are outside it).

有可靠的方法吗?

额外信息:段由位置 P、方向 O(其大小为圆半径)和视图大小 S 来描述.

Extra info: The segment is described by position P, orientation O (whose magnitude is the circle radius), and a view size, S.

迄今为止，我最成功的尝试是确定向量 ca1 和 ca2 的角度，并检查它们中的任何一个是否位于向量 a1 和 a2 的角度之间.如上所述，这适用于某些情况，但不适用于目标圆大于线段的情况.

My most successful attempt to date involved determining the angles of the vectors ca1 and ca2, and checking if either of them lies between the angles of vectors a1 and a2. This works for some cases as explained above, but not situations where the target circle is larger than the segment.

编辑 2在实施了下面的最佳建议后，仍然存在误报，我不确定如何最好地消除.请参阅下面的粉红色图表.右下角的圆圈报告为与线段发生碰撞，因为它的边界与半空间和主圆圈重叠.

Edit 2 After implementing the best suggestion from below, there is still a false positive which I am unsure how best to eliminate. See the pink diagram below. The circle in the lower right is reporting as colliding with the segment because it's bounds overlap both half spaces and the main circle.

在发现另一个边缘情况(第 4 张图片)之后，我决定采用一种方法，该方法结合了下面的两个最佳答案，并且似乎涵盖了所有基础.为了后面的人，我在这里描述一下.

After discovering another edge case (4th image), i've settled on an approach which combines the two top answers from below and seems to cover all bases. I'll describe it here for the sake of those who follow.

首先排除任何未能通过快速循环测试的内容.

First exclude anything that fails a quick circle-to-circle test.

然后测试圆和线段的两条外线之间的碰撞.如果它触及任何一个，则返回 true.

Then test for collision between the circle and the two outer lines of the segment. If it touches either, return true.

最后，使用圆心和两条外线(如下面的 Gareth 所述)进行几个点到半空间测试.如果它通过了它所在的两个，否则返回false.

Finally, do a couple of point-to-halfspace tests using the center of the circle and the two outer lines (as described by Gareth below). If it passes both of those it's in, otherwise return false.

推荐答案

A.检查它是否与整个圆圈相交.
B. 检查它是否与任何一条直线相交.
C. 如果不是，检查圆心之间的角度是否在线段的角度范围内(点积对此有好处).

A. Check if it is intersecting the whole cirlce.
B. Check if it is intersecting either of the straight segment lines.
C. If not, check if the angle between the circle centres lies in the angular range of the segment (dot product is good for this).

交叉点需要 A &&(B || C)

这篇关于圆到圆段碰撞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！