Обнаружение столкновения окружности с прямоугольником (пересечение)

Question

Как определить, пересекаются ли круг и прямоугольник в евклидовом пространстве 2D? (т.е. классическая 2D геометрия)

Answer 1

Вот как бы я это сделал:

bool intersects(CircleType circle, RectType rect)
{
    circleDistance.x = abs(circle.x - rect.x);
    circleDistance.y = abs(circle.y - rect.y);

    if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
    if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }

    if (circleDistance.x <= (rect.width/2)) { return true; } 
    if (circleDistance.y <= (rect.height/2)) { return true; }

    cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
                         (circleDistance.y - rect.height/2)^2;

    return (cornerDistance_sq <= (circle.r^2));
}

Вот как это работает:

1. Первая пара линий вычисляет абсолютные значения разности x и y между центром круга и центром прямоугольника. Это объединяет четыре квадранта в один, так что вычисления не нужно выполнять четыре раза. На рисунке показана область, в которой теперь должен находиться центр круга. Обратите внимание, что отображается только один квадрант. Прямоугольник - это серая область, а красная граница очерчивает критическую область, которая находится ровно в одном радиусе от краев прямоугольника. Центр круга должен находиться внутри этой красной границы, чтобы произошло пересечение.

2. Вторая пара линий исключает простые случаи, когда круг находится достаточно далеко от прямоугольника (в любом направлении), и пересечение невозможно. Это соответствует зеленой области на изображении.

3. Третья пара линий обрабатывает простые случаи, когда окружность достаточно близка к прямоугольнику (в любом направлении), чтобы пересечение гарантировалось. Это соответствует оранжевой и серой полосам на изображении. Обратите внимание, что этот шаг должен быть выполнен после шага 2, чтобы логика имела смысл.

4. Оставшиеся строки рассчитывают сложный случай, когда круг может пересекать угол прямоугольника. Чтобы решить, вычислите расстояние от центра круга и угла, а затем убедитесь, что расстояние не превышает радиус круга. Это вычисление возвращает значение false для всех кругов, центр которых находится внутри красной заштрихованной области, и значение true для всех кругов, центр которых находится внутри белой заштрихованной области.

Answer 2

Есть только два случая, когда круг пересекается с прямоугольником:

• Либо центр круга находится внутри прямоугольника, либо
• Один из краев прямоугольника имеет точку в круге.

Обратите внимание, что для этого не требуется, чтобы прямоугольник был параллельным оси.

(Один из способов убедиться в этом: если ни одно из ребер не имеет точки в окружности (если все ребра находятся полностью «вне» окружности), то единственный путь, которым окружность может пересечь многоугольник, - это если он лежит полностью внутри многоугольника.)

При таком понимании будет работать нечто подобное следующему: круг имеет центр P и радиус R, а прямоугольник имеет вершины A, B, C, D в этом заказ (не полный код):

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() может быть реализовано несколькими способами; любой из общих точек в полигоне будет работать, но для прямоугольника вы можете просто проверить, работает ли он:

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

И intersectCircle() также легко реализовать: одним из способов было бы проверить, достаточно ли близко подошва перпендикуляра от P к линии и между конечными точками, и проверить конечные точки в противном случае.

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

Answer 3

Вот еще одно решение, которое довольно просто реализовать (и тоже довольно быстро). Он поймает все пересечения, в том числе, когда сфера полностью вошла в прямоугольник.

// clamp(value, min, max) - limits value to the range min..max

// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);

// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

С любой приличной математической библиотекой, которую можно сократить до 3 или 4 строк.

Answer 4

ваша сфера и прямоугольник пересекаются IIF
расстояние между центром круга и одной вершиной вашей прямой меньше радиуса вашей сферы
ИЛИ
расстояние между центром круга и одним краем вашей прямоугольника меньше радиуса вашей сферы ([ расстояние между точками ])
ИЛИ
центр круга находится внутри прямоугольника

расстояние точка-точка:

P1 = [x1,y1]
P2 = [x2,y2]
Distance = sqrt(abs(x1 - x2)+abs(y1-y2))

расстояние между точками:

L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points)
P1 = [px,py] some point

Distance d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

центр круга внутри прямоугольника:
Возьмите разделительную ось: если существует проекция на линию, отделяющую прямоугольник от точки, они не пересекаются

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

вам просто нужен внутренний продукт (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)

ваш тест будет выглядеть так:

//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI

seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // the edges
    D = edge[0] - edge[1]
    innerProd =  D * POI
    Interval_min = min(D*edge[0],D*edge[1])
    Interval_max = max(D*edge[0],D*edge[1])
    if not (  Interval_min ≤ innerProd ≤  Interval_max ) 
           seperated = true
           break  // end for loop 
    end if
end for
if (seperated is true)    
      return "no intersection"
else 
      return "intersection"
end if

это не предполагает выравнивания по оси прямоугольника и легко расширяется для проверки пересечений между выпуклыми наборами.

Answer 5

Это самое быстрое решение:

public static boolean intersect(Rectangle r, Circle c)
{
    float cx = Math.abs(c.x - r.x - r.halfWidth);
    float xDist = r.halfWidth + c.radius;
    if (cx > xDist)
        return false;
    float cy = Math.abs(c.y - r.y - r.halfHeight);
    float yDist = r.halfHeight + c.radius;
    if (cy > yDist)
        return false;
    if (cx <= r.halfWidth || cy <= r.halfHeight)
        return true;
    float xCornerDist = cx - r.halfWidth;
    float yCornerDist = cy - r.halfHeight;
    float xCornerDistSq = xCornerDist * xCornerDist;
    float yCornerDistSq = yCornerDist * yCornerDist;
    float maxCornerDistSq = c.radius * c.radius;
    return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}

Обратите внимание на порядок выполнения, и половина ширины / высоты предварительно вычисляется. Также возведение в квадрат выполняется «вручную» для сохранения некоторых тактов.

Answer 6

Самое простое решение, которое я придумал, довольно простое.

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

Вы можете сделать все это с помощью нескольких операций и даже избежать использования функции sqrt.

public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
   float closestX = (cx < left ? left : (cx > right ? right : cx));
   float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
   float dx = closestX - cx;
   float dy = closestY - cy;

   return ( dx * dx + dy * dy ) <= radius * radius;
}

И это все! Приведенное выше решение предполагает начало координат в верхнем левом углу мира с осью X, направленной вниз.

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

Answer 7

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

float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
    float diff = 99999;

    SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
    rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB

    float x_clamped_within_rectangle = relative_position_of_circle.x;
    float y_clamped_within_rectangle = relative_position_of_circle.y;
    LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
    LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);

    // Calculate the distance between the circle's center and this closest point
    float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
    float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;

    // If the distance is less than the circle's radius, an intersection occurs
    float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
    float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
    float radius_sq = SQUARE(self->physicsRadius);
    if(distance_sq_x + distance_sq_y < radius_sq)   
    {
        float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
        float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;

        CREATE_VECTOR(push_vector);         

        // If we're at one of the corners of this object, treat this as a circular/circular collision
        if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
        {
            SVector edges;
            if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
            if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;   

            push_vector = relative_position_of_circle;
            moveVectorByInverseVector2D(&push_vector, &edges);

            // We now have the vector from the corner of the rect to the point.
            float delta_length = getVector2DMagnitude(&push_vector);
            float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance

            // Normalise the vector
            push_vector.x /= delta_length;
            push_vector.y /= delta_length;
            scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
            push_vector.z = 0;
        }
        else // Nope - just bouncing against one of the edges
        {
            if(relative_position_of_circle.x > 0) // Ball is to the right
                push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
            else
                push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);

            if(relative_position_of_circle.y > 0) // Ball is above
                push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
            else
                push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);

            if(fabs(push_vector.x) < fabs(push_vector.y))
                push_vector.y = 0;
            else
                push_vector.x = 0;
        }

        diff = 0; // Cheat, since we don't do anything with the value anyway
        rotateVector2DBy(&push_vector, actor->axis.angleZ);
        SVector *from = &self->worldPosition;       
        moveVectorBy2D(from, push_vector.x, push_vector.y);
    }   
    return diff;
}

Answer 8

На самом деле, это намного проще. Вам нужны только две вещи.

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

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

Удачи!

Answer 9

Для визуализации возьмите цифровую клавиатуру. Если клавиша '5' представляет ваш прямоугольник, то все клавиши 1-9 представляют 9 квадрантов пространства, разделенных линиями, составляющими ваш прямоугольник (с 5 внутри).

1) Если центр круга находится в квадранте 5 (т.е. внутри прямоугольника), то две фигуры пересекаются.

Учитывая все вышесказанное, возможны два случая: а) Круг пересекается с двумя или более соседними краями прямоугольника. б) круг пересекается с одним краем прямоугольника.

Первый случай прост. Если круг пересекается с двумя соседними краями прямоугольника, он должен содержать угол, соединяющий эти два ребра. (Это, или его центр лежит в квадранте 5, который мы уже рассмотрели. Также обратите внимание, что случай, когда круг пересекается только с двумя противоположными краями прямоугольника, также покрыт.)

2) Если любой из углов A, B, C, D прямоугольника находится внутри круга, то две фигуры пересекаются.

Второй случай сложнее. Следует отметить, что это может произойти только тогда, когда центр круга находится в одном из квадрантов 2, 4, 6 или 8. (Фактически, если центр находится в каком-либо из квадрантов 1, 3, 7, 8, соответствующий угол будет ближайшей к нему точкой.)

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

3) Для каждой линии AB, BC, CD, DA постройте перпендикулярные линии p (AB, P), p (BC, P), p (CD, P), p (DA, P) через центр круга. P. Если для каждой перпендикулярной линии пересечение с исходным ребром находится внутри круга, то эти две фигуры пересекаются.

Существует ярлык для этого последнего шага. Если центр круга находится в квадранте 8, а ребро AB - это верхнее ребро, точка пересечения будет иметь координату Y от A и B и координату X от центра P.

Вы можете построить четыре пересечения линий и проверить, лежат ли они на соответствующих ребрах, или выяснить, в каком квадранте P находится, и проверить соответствующее пересечение. Оба должны упростить до одного и того же логического уравнения. Остерегайтесь того, что вышеприведенный шаг 2 не исключает, что P находится в одном из «угловых» квадрантов; он просто искал пересечение.

Edit: Оказывается, я упустил из виду тот простой факт, что # 2 является подслучае # 3 выше. Ведь углы тоже являются точками по краям. Посмотрите ответ @ ShreevatsaR ниже для хорошего объяснения. А пока, забудьте про № 2 выше, если вы не хотите быстрой, но избыточной проверки.

Answer 10

Эта функция обнаруживает столкновения (пересечения) между Кругом и Прямоугольником. В своем ответе он работает как метод e.James, но этот обнаруживает столкновения для всех углов прямоугольника (не только для правого угла).

ПРИМЕЧАНИЕ:

aRect.origin.x и aRect.origin.y - это координаты нижнего левого угла прямоугольника!

aCircle.x и aCircle.y - это координаты центра круга!

static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {

    float testX = aCircle.x;
    float testY = aCircle.y;

    if (testX < aRect.origin.x)
        testX = aRect.origin.x;
    if (testX > (aRect.origin.x + aRect.size.width))
        testX = (aRect.origin.x + aRect.size.width);
    if (testY < aRect.origin.y)
        testY = aRect.origin.y;
    if (testY > (aRect.origin.y + aRect.size.height))
        testY = (aRect.origin.y + aRect.size.height);

    return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}