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

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

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 для всех кругов, центр которых в белой заштрихованной области.

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

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

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

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

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

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

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

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

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

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

Редактирование: Как оказалось, я пропустил очевидный факт, что № 2 является подслучаем № 3 выше. В конце концов, углы также являются точками на краях. См. ответ @ShreevatsaR ниже для большого объяснения. И в это время, забудьте № 2 выше, если Вы не хотите быструю, но избыточную проверку.

Принятие Вас имеет четыре края прямоугольной проверки расстояние от краев до центра круга, если его меньше тогда радиус, то формы пересекаются.

if sqrt((rectangleRight.x - circleCenter.x)^2 +
        (rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleRight.x - circleCenter.x)^2 +
        (rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleLeft.x - circleCenter.x)^2 +
        (rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect

if sqrt((rectangleLeft.x - circleCenter.x)^2 +
        (rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect

ваша сфера и прямоугольник пересекают 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

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

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

// 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 строк.

Вот мой код на 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;
}

Вот модифицированный код, работающий на 100%:

public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle)
{
    var rectangleCenter = new PointF((rectangle.X +  rectangle.Width / 2),
                                     (rectangle.Y + rectangle.Height / 2));

    var w = rectangle.Width  / 2;
    var h = rectangle.Height / 2;

    var dx = Math.Abs(circle.X - rectangleCenter.X);
    var dy = Math.Abs(circle.Y - rectangleCenter.Y);

    if (dx > (radius + w) || dy > (radius + h)) return false;

    var circleDistance = new PointF
                             {
                                 X = Math.Abs(circle.X - rectangle.X - w),
                                 Y = Math.Abs(circle.Y - rectangle.Y - h)
                             };

    if (circleDistance.X <= (w))
    {
        return true;
    }

    if (circleDistance.Y <= (h))
    {
        return true;
    }

    var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) + 
                                    Math.Pow(circleDistance.Y - h, 2);

    return (cornerDistanceSq <= (Math.Pow(radius, 2)));
}

Бассам Алугили