mathematics - learn math




如何檢測圓與同一平面中任何其他圓之間的交點? (5)

Java中的這個解決方案使用了上面描述的數學表達式:

/**
     * 
     * @param values
     *            { x0, y0, r0, x1, y1, r1 }
     * @return true if circles is intersected
     * 
     *         Check if circle is intersect to another circle
     */
    public static boolean isCircleIntersect(double... values) {
        /*
         * check using mathematical relation: ABS(R0-R1) <=
         * SQRT((x0-x1)^2+(y0-y1)^2) <= (R0+R1)
         */
        if (values.length == 6) {
            /* get values from first circle */
            double x0 = values[0];
            double y0 = values[1];
            double r0 = values[2];
            /* get values from second circle */
            double x1 = values[3];
            double y1 = values[4];
            double r1 = values[5];
            /* returun result */
            return (Math.abs(r0 - r1) <= Math.sqrt(Math.pow((x0 - x1), 2)
                    + Math.pow((y0 - y1), 2)))
                    && (Math.sqrt(Math.pow((x0 - x1), 2)
                            + Math.pow((y0 - y1), 2)) <= (r0 + r1));
        } else {
            /* return default result */
            return false;
        }
    }

我正在尋找一種算法來檢測圓是否與同一平面中的任何其他圓相交(假設平面中可能有多個圓)。

我發現的一種方法是進行分離軸測試。 它說:

如果您可以找到分隔兩個對象的線,即一條線,使得對象的所有對像或點位於線的不同側,則兩個對像不相交。

但是,我不知道如何將這種方法應用到我的案例中。

有誰能夠幫助我?


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,即使一個圓圈在另一個圓圈內(將它們視為“已填充”圓圈)。


假設填充圓形交叉點(即:另一個圓圈是另一個交叉點)。

哪裡:

  • x0,y0,r0 =中心和圓的半徑0。
  • x1,y1,r1 =中心和圓的半徑1。

碼:

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

如果兩個圓的中心之間的距離最多是它們的半徑之和,但至少是半徑之差的絕對值,那麼圓圈本身在某一點相交。

如果你只關心圈子本身而不關心它們的內部區域,那麼“至少差異”部分適用。 如果你關心它們所包圍的圓圈或區域是否共享任何點 - 也就是說,如果一個圓圈完全位於另一個圓圈內並且與你“交叉” - 那麼你可以放棄“至少差異”檢查。


當且僅當它們的中心之間的距離在它們的半徑之和與它們之間的差異之間時,兩個圓相交。 給定兩個圓(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

由於您只需要是/否測試,因此此檢查比計算精確交叉點更快。

上述解決方案甚至應該適用於“一個圈內另一個”的情況。





circle