首页 文章

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

提问于
浏览
33

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

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

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

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

有谁能够帮我?

7 回答

  • 4

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

    哪里:

    • x0,y0,r0 =圆心0和圆心半径 .

    • x1,y1,r1 =中心和圆的半径1 .

    码:

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

    当且仅当它们的中心之间的距离在它们的半径之和与它们之间的差异之间时,两个圆相交 . 鉴于两个圆 (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
    

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

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

  • -1

    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,即使一个圆圈在另一个圆圈内(将它们视为“已填充”圆圈) .

  • 2

    如果两个圆的中心之间的距离最多是它们的半径之和,但至少是半径之差的绝对值,那么圆圈本身在某一点相交 .

    如果你只关心圈子本身而不是它们的内部区域,则适用"at least the difference"部分 . 如果您关心圈子或它们所包围的区域是否共享任何点 - 也就是说,如果一个圈子完全位于另一个圈子内,那么您可以放弃"at least the difference"检查 .

  • 0

    我尝试了这里给出的公式,这是一个假定的答案,每个人都投票了,虽然它有严重的缺陷 . 我在JavaFX中编写了一个程序,允许用户通过更改每个圆圈centerX,centerY和Radius值来测试两个圆是否相交,这个公式绝对不起作用,除了一种方式......我无法弄清楚为什么但是当我移动圆圈2靠近圆圈1它的工作原理但是当我将圆圈1移动到圆圈2附近的另一侧时它不起作用..... ?????这有点奇怪......认为需要以相反的方式测试公式,所以尝试了它并且它不起作用

    if (Math.abs(circle1Radius - circle2Radius) <=
                Math.sqrt(Math.pow((circle1X - circle2X), 2)
                + Math.pow((circle1Y - circle2Y), 2)) &&
                Math.sqrt(Math.pow((circle1X - circle2X), 2)
                + Math.pow((circle1X - circle2Y), 2)) <=
                (circle1Radius + circle2Radius)} {
        return true;
    } else {
        return false;
    }
    

    这有效:

    // dx and dy are the vertical and horizontal distances
        double dx = circle2X - circle1X;
        double dy = circle2Y - circle1Y;
    
        // Determine the straight-line distance between centers.
        double d = Math.sqrt((dy * dy) + (dx * dx));
    
        // Check Intersections
        if (d > (circle1Radius + circle2Radius)) {
            // No Solution. Circles do not intersect
            return false;
        } else if (d < Math.abs(circle1Radius - circle2Radius)) {
            // No Solution. one circle is contained in the other
            return false;
        } else {
            return true;
        }
    

    去这里找公式Intersection of two circles

    使用的公式不是我的公式所有功劳都归功于Paul Bourke(1997年4月)

    First calculate the distance d between the center of the circles. d = ||P1 - P0||.
    
        If d > r0 + r1 then there are no solutions, the circles are separate.
    
        If d < |r0 - r1| then there are no solutions because one circle is contained within the other.
    
        If d = 0 and r0 = r1 then the circles are coincident and there are an infinite number of solutions.
    
    Considering the two triangles P0P2P3 and P1P2P3 we can write
    
    a2 + h2 = r02 and b2 + h2 = r12
    
    Using d = a + b we can solve for a,
    
    a = (r02 - r12 + d2 ) / (2 d)
    
    It can be readily shown that this reduces to r0 when the two circles touch at one point, ie: d = r0 + r1
    
    Solve for h by substituting a into the first equation, h2 = r02 - a2
    So
    
    P2 = P0 + a ( P1 - P0 ) / d
    
    And finally, P3 = (x3,y3) in terms of P0 = (x0,y0), P1 = (x1,y1) and P2 = (x2,y2), is
    
    x3 = x2 +- h ( y1 - y0 ) / d
    
    y3 = y2 -+ h ( x1 - x0 ) / d
    
  • 62

    Swift 4 解决方案:

    struct Circle {
        let radius: CGFloat
        let position: CGPoint
    }
    
    func circlesIntersect(circleA: Circle, circleB: Circle) -> Bool {
        let Δr² = pow(circleA.radius - circleB.radius, 2)
        let Δx² = pow(circleA.position.x - circleB.position.x, 2)
        let Δy² = pow(circleA.position.y - circleB.position.y, 2)
        let ΣΔx²Δy² = Δx² + Δy²
        let Σr² = pow(circleA.radius + circleB.radius, 2)
        return Δr² <= ΣΔx²Δy² && ΣΔx²Δy² <= Σr²
    }
    
  • 6

    Java中的This solution使用了上面描述的数学表达式:

    /**
         * 
         * @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;
            }
        }
    

相关问题