圆-矩形碰撞检测(相交) [英] Circle-Rectangle collision detection (intersection)

问题描述

如何判断圆形和矩形在二维欧几里得空间中是否相交?(即经典的二维几何)

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)

推荐答案

圆与矩形相交只有两种情况:

There are only two cases when the circle intersects with the rectangle:

• 圆的中心位于矩形内，或者
• 矩形的一条边在圆中有一个点.

请注意，这并不要求矩形是轴平行的.

Note that this does not require the rectangle to be axis-parallel.

(看这个的一种方法:如果没有一条边在圆中有一个点(如果所有边都完全在圆外部")，那么圆仍然可以与多边形相交的唯一方法是它是否位于完全在多边形内.)

(One way to see this: if none of the edges has a point in the circle (if all the edges are completely "outside" the circle), then the only way the circle can still intersect the polygon is if it lies completely inside the polygon.)

有了这种洞察力，类似下面的东西就可以工作了，圆的中心是 P，半径是 R，矩形的顶点是 A、B、C、D 按顺序排列(不完整的代码):

With that insight, something like the following will work, where the circle has centre P and radius R, and the rectangle has vertices A, B, C, D in that order (not complete code):

def intersect(Circle(P, R), Rectangle(A, B, C, D)):
    S = Circle(P, R)
    return (pointInRectangle(P, Rectangle(A, B, C, D)) or
            intersectCircle(S, (A, B)) or
            intersectCircle(S, (B, C)) or
            intersectCircle(S, (C, D)) or
            intersectCircle(S, (D, A)))

如果您正在编写任何几何图形，您的库中可能已经有上述函数.否则，pointInRectangle() 可以通过多种方式实现；任何一般 point in polygon 方法都可以使用，但对于矩形，您可以检查这是否作品:

If you're writing any geometry you probably have the above functions in your library already. Otherwise, pointInRectangle() can be implemented in several ways; any of the general point in polygon methods will work, but for a rectangle you can just check whether this works:

0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD

而且 intersectCircle() 也很容易实现:一种方法是检查从 P 到直线的垂线的底脚是否足够近并且在端点，否则检查端点.

And intersectCircle() is easy to implement too: one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints, and check the endpoints otherwise.

很酷的是 same 的想法不仅适用于矩形，而且适用于圆与任何 简单多边形 — 甚至不必是凸的！

The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon — doesn't even have to be convex!

这篇关于圆-矩形碰撞检测(相交)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！