如何检测圆与同一平面中任何其他圆之间的交点？

Question

我正在寻找一种算法来检测一个圆是否与同一平面内的任何其他圆相交(假设一个平面中可能有多个圆).

我发现的一种方法是进行分离轴测试.它说:

如果您可以找到分隔两个对象的线,即一条线,使得对象的所有对象或点位于线的不同侧,则两个对象不相交.

但是,我不知道如何将此方法应用于我的案例.

有谁能够帮我？

Answer 1

当且仅当它们的中心之间的距离在它们的半径之和与它们之间的差异之间时,两个圆相交.给定两个圆(x0, y0, R0)和(x1, y1, R1),公式如下:

ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)

SQRT如果您的输入是整数,那么平方双方可以避免缓慢,并保持整数:

(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2

由于您只需要是/否测试,因此此检查比计算精确交叉点更快.

上述解决方案应该适用于"一个圈内另一个"的情况.

Answer 2

假设填充圆形交叉点(即:另一个圆圈在另一个内部是交叉点).

哪里:

• x0,y0,r0 =圆心0和圆心半径.
• x1,y1,r1 =圆心1的中心和半径.

码:

boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);

Answer 3

XNA/C# 解决方案

    class Circle
    {
        public Vector2 Center;
        public float Radius;

        public bool Intersects(Circle circle)
        {
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusSum = circle.Radius + Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusSum * radiusSum;
        }
        public bool Contains(Circle circle)
        {
            if (circle.Radius > Radius)
                return false;
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusD = Radius - circle.Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusD * radiusD;
        }
    }

请注意，即使一个圆圈在另一个圆圈内，方法 Circle.Intersects() 也会返回 true（将它们视为“填充”圆圈）。