Wykrywanie kolizji koło-prostokąt (przecięcie)

Skąd mam wiedzieć, czy okrąg i prostokąt przecinają się w przestrzeni euklidesowej 2D? (tj. klasyczna geometria 2D)

Istnieją tylko dwa przypadki, w których okrąg przecina się z prostokątem:

• Albo środek okręgu leży wewnątrz prostokąta, albo
• Jedna z krawędzi prostokąta ma punkt na okręgu.

Zauważ, że nie wymaga to, aby prostokąt był równoległy do ​​osi.

(Można to zobaczyć na jeden sposób: jeśli żadna z krawędzi nie ma punktu na okręgu (jeśli wszystkie krawędzie są całkowicie „na zewnątrz” koła), wówczas jedynym sposobem, w jaki okrąg może przecinać wielokąt, jest całkowite jego położenie wewnątrz wielokąt.)

Z tego wglądu, coś jak poniżej będzie działać, gdzie okrąg ma środek Pi promień R, a prostokąt ma wierzchołki A, B, C, Dw tej kolejności (nie kompletny kod):

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)))

Jeśli piszesz jakąkolwiek geometrię, prawdopodobnie masz już w bibliotece powyższe funkcje. W przeciwnym razie pointInRectangle()można je wdrożyć na kilka sposobów; dowolny ogólny punkt w metodach wielokąta będzie działał, ale dla prostokąta możesz po prostu sprawdzić, czy to działa:

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

I intersectCircle()jest również łatwy do wdrożenia: jednym ze sposobów byłoby sprawdzenie, czy stopa prostopadłej Pdo linii jest wystarczająco blisko i między punktami końcowymi, a w przeciwnym razie sprawdź punkty końcowe.

Fajne jest to, że ten sam pomysł działa nie tylko dla prostokątów, ale także na przecięciu koła z dowolnym prostym wielokątem - nawet nie musi być wypukły!

Oto jak bym to zrobił:

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));
}

Oto jak to działa:

1. Pierwsza para linii oblicza bezwzględne wartości różnicy xiy między środkiem okręgu a środkiem prostokąta. To powoduje, że cztery ćwiartki dzielą się na jeden, dzięki czemu obliczenia nie muszą być wykonywane cztery razy. Obraz pokazuje obszar, w którym musi teraz leżeć środek okręgu. Zauważ, że pokazany jest tylko pojedynczy kwadrant. Prostokąt jest szarym obszarem, a czerwona ramka przedstawia obszar krytyczny, który znajduje się dokładnie jeden promień od krawędzi prostokąta. Środek koła musi znajdować się w obrębie tej czerwonej granicy, aby nastąpiło przecięcie.

2. Druga para linii eliminuje łatwe przypadki, w których okrąg jest wystarczająco daleko od prostokąta (w obu kierunkach), aby niemożliwe było przecięcie. Odpowiada to zielonemu obszarowi na obrazie.

3. Trzecia para linii obsługuje proste przypadki, w których okrąg jest wystarczająco blisko prostokąta (w dowolnym kierunku), aby zagwarantować przecięcie. Odpowiada to pomarańczowym i szarym sekcjom na obrazie. Zauważ, że ten krok musi być wykonany po kroku 2, aby logika miała sens.

4. Pozostałe linie obliczają trudny przypadek, w którym okrąg może przecinać róg prostokąta. Aby rozwiązać, oblicz odległość od środka koła i rogu, a następnie sprawdź, czy odległość nie jest większa niż promień koła. To obliczenie zwraca wartość false dla wszystkich kół, których środek znajduje się w obszarze zacieniowanym na czerwono, i zwraca wartość true dla wszystkich kół, których środek znajduje się w obszarze zacieniowanym na biało.

Oto kolejne rozwiązanie, które jest dość proste do wdrożenia (i również dość szybkie). Złapie wszystkie przecięcia, w tym gdy kula całkowicie wejdzie w prostokąt.

// 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);

Z każdą przyzwoitą biblioteką matematyczną, którą można skrócić do 3 lub 4 linii.

twoja kula i prostokąt przecinają IIF
odległość między środkiem okręgu a jednym wierzchołkiem twojej odbytnicy jest mniejsza niż promień twojej kuli
LUB
odległość między środkiem okręgu a jedną krawędzią twojej odbytnicy jest mniejsza niż promień twojej kuli ( [ odległość punkt-linia ])
LUB
środek okręgu znajduje się wewnątrz prostej odległości

punkt-punkt:

P1 = [x1, y1]
P2 = [x2, y2]
Odległość = sqrt (abs (x1 - x2) + abs (y1-y2))

odległość punkt-linia:

L1 = [x1, y1], L2 = [x2, y2] (dwa punkty linii, tj. Punkty wierzchołka)
P1 = [px, py] jakiś punkt

Odległość d = abs ((x2-x1) (y1-py) - (x1-px) (y2-y1)) / Odległość (L1, L2)

środek okręgu wewnątrz
prostokąta : podejdź do osi oddzielającej: jeśli istnieje rzut na linię oddzielającą prostokąt od punktu, nie przecinają się

rzutujesz punkt na linie równoległe do boków twojej odbytnicy i możesz łatwo ustalić, czy się przecinają. jeśli nie przecinają się na wszystkich 4 rzutach, nie mogą się przecinać (punkt i prostokąt).

potrzebujesz tylko produktu wewnętrznego (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)

Twój test wyglądałby tak:

// krawędzie prostokąta: TL (u góry po lewej), TR (u góry po prawej), BL (u dołu po lewej), BR (u dołu po prawej)
// punkt do przetestowania: POI

rozdzielone = fałsz
dla egde w {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}: // krawędzie
    D = krawędź [0] - krawędź [1]
    innerProd = D * POI
    Interwał_min = min (D * zbocze [0], D * zbocze [1])
    Interval_max = max (D * zbocze [0], D * zbocze [1])
    jeśli nie (Interval_min ≤ innerProd ≤ Interval_max) 
           rozdzielone = prawda
           break // end for loop 
    koniec jeśli
koniec dla
jeśli (oddzielne to prawda)    
      zwróć „brak skrzyżowania”
jeszcze 
      powrót „skrzyżowanie”
koniec jeśli

nie zakłada to prostokąta wyrównanego do osi i można go łatwo rozszerzyć do testowania przecięć między zestawami wypukłymi.

To najszybsze rozwiązanie:

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

Zwróć uwagę na kolejność wykonywania, a połowa szerokości / wysokości jest wstępnie obliczona. Również wykonywanie kwadratu odbywa się „ręcznie”, aby zapisać niektóre cykle zegara.

Najprostsze rozwiązanie, jakie wymyśliłem, jest dość proste.

Działa poprzez znalezienie punktu w prostokącie najbliższym okręgu, a następnie porównanie odległości.

Możesz to wszystko zrobić za pomocą kilku operacji, a nawet uniknąć funkcji 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;
}

I to wszystko! Powyższe rozwiązanie zakłada początek w lewym górnym rogu świata z osią x skierowaną w dół.

Jeśli chcesz rozwiązać kolizje między ruchomym okręgiem a prostokątem, jest to o wiele bardziej skomplikowane i omówione w innej mojej odpowiedzi.

W rzeczywistości jest to o wiele prostsze. Potrzebujesz tylko dwóch rzeczy.

Najpierw musisz znaleźć cztery ortogonalne odległości od środka okręgu do każdej linii prostokąta. Wówczas twój okrąg nie przecina prostokąta, jeśli trzy z nich są większe niż promień okręgu.

Po drugie, musisz znaleźć odległość między środkiem okręgu a środkiem prostokąta, wtedy koło nie będzie w środku prostokąta, jeśli odległość będzie większa niż połowa długości przekątnej prostokąta.

Powodzenia!

Oto mój kod C do rozwiązywania kolizji między kulą a nieosiowym wyrównanym polem. Opiera się na kilku moich własnych procedurach bibliotecznych, ale dla niektórych może się przydać. Używam go w grze i działa idealnie.

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

Aby zwizualizować, weź klawiaturę numeryczną klawiatury. Jeśli klawisz „5” reprezentuje prostokąt, wszystkie klawisze 1-9 reprezentują 9 kwadrantów przestrzeni podzielonych przez linie tworzące prostokąt (gdzie 5 to wnętrze).

1) Jeśli środek okręgu znajduje się w ćwiartce 5 (tj. Wewnątrz prostokąta), wówczas dwa kształty przecinają się.

Poza tym istnieją dwa możliwe przypadki: a) Okrąg przecina się z dwiema lub więcej sąsiadującymi krawędziami prostokąta. b) Okrąg przecina się z jedną krawędzią prostokąta.

Pierwszy przypadek jest prosty. Jeśli okrąg przecina się z dwiema sąsiadującymi krawędziami prostokąta, musi zawierać róg łączący te dwie krawędzie. (To lub jego środek leży w kwadrancie 5, który już omówiliśmy. Zauważ również, że przypadek, w którym koło przecina się tylko z dwiema przeciwległymi krawędziami prostokąta, jest również objęty.)

2) Jeśli którykolwiek z narożników A, B, C, D prostokąta leży wewnątrz koła, wówczas dwa kształty przecinają się.

Drugi przypadek jest trudniejszy. Należy zauważyć, że może się to zdarzyć tylko wtedy, gdy środek koła znajduje się w jednej z ćwiartek 2, 4, 6 lub 8. (W rzeczywistości, jeśli środek znajduje się w którejkolwiek z ćwiartek 1, 3, 7, 8 odpowiedni róg będzie najbliżej tego punktu).

Teraz mamy przypadek, że środek koła znajduje się w jednej z ćwiartek „krawędzi” i przecina on tylko odpowiednią krawędź. Następnie punkt na krawędzi, który jest najbliżej środka koła, musi leżeć wewnątrz koła.

3) Dla każdej linii AB, BC, CD, DA skonstruuj linie prostopadłe p (AB, P), p (BC, P), p (CD, P), p (DA, P) przez środek okręgu P. Dla każdą linię prostopadłą, jeśli przecięcie z oryginalną krawędzią leży wewnątrz koła, wówczas dwa kształty przecinają się.

Istnieje skrót do tego ostatniego kroku. Jeśli środek okręgu znajduje się w ćwiartce 8, a krawędź AB jest górną krawędzią, punkt przecięcia będzie miał współrzędną y A i B oraz współrzędną x środka P.

Możesz zbudować cztery przecięcia linii i sprawdzić, czy leżą na odpowiadających im krawędziach, lub dowiedzieć się, w którym kwadrancie P jest, i sprawdzić odpowiednie przecięcie. Oba powinny uprościć to samo równanie boolowskie. Uważaj, aby powyższy krok 2 nie wykluczył, że P znajduje się w jednej z „narożnych” ćwiartek; po prostu szukał skrzyżowania.

Edycja: Jak się okazuje, przeoczyłem prosty fakt, że nr 2 jest podtekstem nr 3 powyżej. W końcu rogi też są punktami na krawędziach. Świetne wyjaśnienie znajduje się w odpowiedzi @ ShreevatsaR poniżej. W międzyczasie zapomnij o punkcie 2 powyżej, chyba że chcesz szybkiego, ale zbędnego czeku.

Ta funkcja wykrywa kolizje (przecięcia) między okręgiem a prostokątem. W swojej odpowiedzi działa jak metoda e.James, ale ta wykrywa kolizje dla wszystkich kątów prostokąta (nie tylko w prawym górnym rogu).

UWAGA:

aRect.origin.x i aRect.origin.y są współrzędnymi lewego dolnego kąta prostokąta!

aCircle.x i aCircle.y są współrzędnymi Circle Center!

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

Mam metodę, która w razie potrzeby pozwala uniknąć drogich pitagoras. podczas ograniczania prostokątów i koła nie przecinają się.

I będzie działać również w przypadku euklidesa:

class Circle {
 // create the bounding box of the circle only once
 BBox bbox;

 public boolean intersect(BBox b) {
    // test top intersect
    if (lat > b.maxLat) {
        if (lon < b.minLon)
            return normDist(b.maxLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.maxLat, b.maxLon) <= normedDist;
        return b.maxLat - bbox.minLat > 0;
    }

    // test bottom intersect
    if (lat < b.minLat) {
        if (lon < b.minLon)
            return normDist(b.minLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.minLat, b.maxLon) <= normedDist;
        return bbox.maxLat - b.minLat > 0;
    }

    // test middle intersect
    if (lon < b.minLon)
        return bbox.maxLon - b.minLon > 0;
    if (lon > b.maxLon)
        return b.maxLon - bbox.minLon > 0;
    return true;
  }
}

• minLat, maxLat można zastąpić minY, maxY i to samo dla minLon, maxLon: zamień na minX, maxX
• normDist jest tylko nieco szybszą metodą niż pełne obliczanie odległości. Np bez pierwiastka kwadratowego w przestrzeni euklidesowej (lub bez wielu innych rzeczy dla haversine) dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Oczywiście, jeśli użyjesz tej metody normDist, musisz utworzyć normedDist = dist*dist;dla koła

Zobacz pełną bbox i Okrągła kod mojego GraphHopper projektu.

Stworzyłem zajęcia do pracy z kształtami, które mam nadzieję

public class Geomethry {
  public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;

    float rectCenterX = rectangleX + rectHalfWidth;
    float rectCenterY = rectangleY + rectHalfHeight;

    float deltax = Math.abs(rectCenterX - circleX);
    float deltay = Math.abs(rectCenterY - circleY);

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
        if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
}

public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;
    float rectHalfWidth2 = rectangleWidth2/2.0f;
    float rectHalfHeight2 = rectangleHeight2/2.0f;

    float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
    float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle
        if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
  } 
}

Oto zmodyfikowany kod działający w 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)));
}

Bassam Alugili

Oto szybki test jednowierszowy:

if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
  // They intersect.
}

Jest to przypadek wyrównany do osi, w którym rect_halveswektor dodatni wskazuje od środka prostokąta do rogu. Wyrażenie w środku length()jest wektorem delta od centernajbliższego punktu prostokąta. Działa to w dowolnym wymiarze.

• Najpierw sprawdź, czy prostokąt i kwadratowa styczna do koła nachodzą na siebie (łatwe). Jeśli się nie pokrywają, nie kolidują.
• Sprawdź, czy środek okręgu znajduje się wewnątrz prostokąta (łatwe). Jeśli jest w środku, zderzają się.
• Obliczyć minimalną kwadratową odległość od boków prostokąta do środka koła (trochę twardo). Jeśli jest niższy niż promień kwadratu, kolidują, inaczej nie.

Jest wydajny, ponieważ:

• Najpierw sprawdza najczęstszy scenariusz za pomocą taniego algorytmu, a gdy jest pewne, że się nie zderzają, kończy się.
• Następnie sprawdza następny najczęstszy scenariusz za pomocą taniego algorytmu (nie obliczaj pierwiastka kwadratowego, użyj kwadratowych wartości) i gdy jest pewne, że się zderzą, kończy się.
• Następnie wykonuje droższy algorytm, aby sprawdzić kolizję z prostokątami.

działało dla mnie (działa tylko wtedy, gdy kąt prostokąta wynosi 180)

function intersects(circle, rect) {
  let left = rect.x + rect.width > circle.x - circle.radius;
  let right = rect.x < circle.x + circle.radius;
  let top = rect.y < circle.y + circle.radius;
  let bottom = rect.y + rect.height > circle.y - circle.radius;
  return left && right && bottom && top;
}

Poprawiając nieco odpowiedź e.Jamesa:

double dx = abs(circle.x - rect.x) - rect.w / 2,
       dy = abs(circle.y - rect.y) - rect.h / 2;

if (dx > circle.r || dy > circle.r) { return false; }
if (dx <= 0 || dy <= 0) { return true; }

return (dx * dx + dy * dy <= circle.r * circle.r);

Odejmuje to rect.w / 2i rect.h / 2raz zamiast do trzech razy.

Dla tych, którzy muszą obliczyć kolizję koło / prostokąt we współrzędnych geograficznych z SQL,
jest to moja implementacja w oracle 11 algorytmu sugerowanego przez e.James .

Na wejściu wymaga współrzędnych okręgu, promienia okręgu w km i dwóch współrzędnych wierzchołka prostokąta:

CREATE OR REPLACE FUNCTION "DETECT_CIRC_RECT_COLLISION"
(
    circleCenterLat     IN NUMBER,      -- circle Center Latitude
    circleCenterLon     IN NUMBER,      -- circle Center Longitude
    circleRadius        IN NUMBER,      -- circle Radius in KM
    rectSWLat           IN NUMBER,      -- rectangle South West Latitude
    rectSWLon           IN NUMBER,      -- rectangle South West Longitude
    rectNELat           IN NUMBER,      -- rectangle North Est Latitude
    rectNELon           IN NUMBER       -- rectangle North Est Longitude
)
RETURN NUMBER
AS
    -- converts km to degrees (use 69 if miles)
    kmToDegreeConst     NUMBER := 111.045;

    -- Remaining rectangle vertices 
    rectNWLat   NUMBER;
    rectNWLon   NUMBER;
    rectSELat   NUMBER;
    rectSELon   NUMBER;

    rectHeight  NUMBER;
    rectWIdth   NUMBER;

    circleDistanceLat   NUMBER;
    circleDistanceLon   NUMBER;
    cornerDistanceSQ    NUMBER;

BEGIN
    -- Initialization of remaining rectangle vertices  
    rectNWLat := rectNELat;
    rectNWLon := rectSWLon;
    rectSELat := rectSWLat;
    rectSELon := rectNELon;

    -- Rectangle sides length calculation
    rectHeight := calc_distance(rectSWLat, rectSWLon, rectNWLat, rectNWLon);
    rectWidth := calc_distance(rectSWLat, rectSWLon, rectSELat, rectSELon);

    circleDistanceLat := abs( (circleCenterLat * kmToDegreeConst) - ((rectSWLat * kmToDegreeConst) + (rectHeight/2)) );
    circleDistanceLon := abs( (circleCenterLon * kmToDegreeConst) - ((rectSWLon * kmToDegreeConst) + (rectWidth/2)) );

    IF circleDistanceLon > ((rectWidth/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat > ((rectHeight/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLon <= (rectWidth/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat <= (rectHeight/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;


    cornerDistanceSQ := POWER(circleDistanceLon - (rectWidth/2), 2) + POWER(circleDistanceLat - (rectHeight/2), 2);

    IF cornerDistanceSQ <=  POWER(circleRadius, 2) THEN
        RETURN 0;  --  -1 => NO Collision ; 0 => Collision Detected
    ELSE
        RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
END;    

Działa, właśnie wymyśliłem to tydzień temu i dopiero teraz przetestowałem.

double theta = Math.atan2(cir.getX()-sqr.getX()*1.0,
                          cir.getY()-sqr.getY()*1.0); //radians of the angle
double dBox; //distance from box to edge of box in direction of the circle

if((theta >  Math.PI/4 && theta <  3*Math.PI / 4) ||
   (theta < -Math.PI/4 && theta > -3*Math.PI / 4)) {
    dBox = sqr.getS() / (2*Math.sin(theta));
} else {
    dBox = sqr.getS() / (2*Math.cos(theta));
}
boolean touching = (Math.abs(dBox) >=
                    Math.sqrt(Math.pow(sqr.getX()-cir.getX(), 2) +
                              Math.pow(sqr.getY()-cir.getY(), 2)));

def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
    if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
        return True
else:
    if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
        return True
return False

Zakładając, że masz cztery krawędzie prostokąta, sprawdź odległość od krawędzi do środka koła, jeśli jest mniejsza niż promień, wówczas kształty się przecinają.

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

Jeśli prostokąt przecina się z okręgiem, jeden lub więcej punktów narożnych prostokąta powinno znajdować się wewnątrz koła. Załóżmy, że cztery punkty prostokąta to A, B, C, D. przynajmniej jeden z nich powinien przecinać okrąg. więc jeśli odległość od jednego punktu do środka koła jest mniejsza niż promień koła, powinna przecinać się koło. Aby uzyskać odległość, możesz użyć twierdzenia Pitagorasa,

H^2 = A^2 + B^2

Ta technika ma pewne ograniczenia. Ale będzie działać lepiej dla twórców gier. szczególnie wykrywanie kolizji

To dobra aktualizacja do algorytmu Arvo