Как я могу обнаружить пересечения между кругом и любым другим кругом в той же плоскости?

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, даже если один круг находится внутри другого (обрабатывает их как "заполненные" круги).

Answer 4

Если расстояние между центрами двух окружностей не больше суммы их радиусов, но не меньше абсолютного значения разности радиусов, то сами круги пересекаются в некоторой точке.

Часть "по крайней мере, разница" применяется, если вы заботитесь только о самих кругах, а не об их внутренних областях. Если вас волнует, имеют ли какие-либо точки круги или области, которые они включают , то есть если один круг полностью внутри другого считается для вас «пересекающимся», то вы можете отбросить «по крайней мере, разница "чек.

Answer 5

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²
}

Answer 6

Я попробовал приведенную здесь формулу, которая является предполагаемым ответом, и все проголосовали, хотя она серьезно ошибочна.Я написал программу на 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;
    }

Goздесь для формулы пересечение двух окружностей

Используемая формула не является моей формулой, все заслуга Пола Бурка (апрель 1997)

 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 

Answer 7

Это решение в 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;
        }
    }