Wykrywanie kolizji okrąg-prostokąt (przecięcie)

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 x i y między środkiem okręgu a środkiem prostokąta. To zwija cztery ćwiartki w jeden, tak, że obliczenia nie muszą być wykonywane cztery razy. Obraz pokazuje obszar, w którym środek okręgu musi teraz leżeć. Zauważ, że wyświetlany jest tylko pojedynczy kwadrant. Na prostokąt jest szarym obszarem, a czerwona ramka przedstawia obszar krytyczny, który znajduje się dokładnie o jeden promień od krawędzi prostokąta. Środek okręgu musi znajdować się w tej czerwonej obwódce, aby doszło do przecięcia.

2. Druga para linii eliminuje proste przypadki, w których okrąg znajduje się na tyle daleko od prostokąta (w obu kierunkach), że nie ma możliwości przecięcia. Odpowiada to zielonemu obszarowi na obrazku.

3. Trzecia para linie obsługują proste przypadki, w których okrąg jest na tyle blisko prostokąta (w obu kierunkach), że przecięcie jest gwarantowane. Odpowiada to pomarańczowym i szarym sekcjom na obrazku. 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ć narożnik prostokąta. Aby rozwiązać, Oblicz odległość od środka okręgu i rogu, a następnie zweryfikuj że odległość nie jest większa niż promień okręgu. To obliczenie zwraca false dla wszystkich okręgów, których środek znajduje się w obszarze cieniowanym na czerwono i zwraca true dla wszystkich okręgów, których środek znajduje się w obszarze cieniowanym na biało.

Oto kolejne rozwiązanie, które jest dość proste do wdrożenia (i dość szybkie, zbyt). Wychwytuje wszystkie przecięcia, w tym gdy sfera w pełni weszła 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ą porządną biblioteką matematyczną, którą można skrócić do 3 lub 4 linijek.

Twoja SFERA I rect intersect IIF
odległość między środkiem okręgu a jednym wierzchołkiem twojego rect jest mniejsza niż promień Twojej sfery
Lub
odległość między środkiem okręgu a jedną krawędzią twojego rect jest mniejsza niż promień Twojej sfery ([odległość punktu-linii ])
Lub
środek koła znajduje się wewnątrz rect

odległość punktu-punktu:

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

Odległość punktu-linii:

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)

koło centrum wewnątrz rect:
weźmy oś oddzielającą: jeśli istnieje rzut na linię oddzielającą prostokąt od punktu, nie przecinają się one

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

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

Twój test będzie wygląda tak:

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

Nie zakłada prostokąta wyrównanego do osi i jest łatwo rozszerzalny do testowania przecięć między zbiorami wypukłymi.

Jest 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ść wykonania, a połowa szerokości / wysokości jest wstępnie obliczona. Również kwadrat jest wykonywany "ręcznie", aby zapisać niektóre cykle zegara.

Właściwie, to jest 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. Wtedy twój okrąg nie będzie przecinał prostokąta, jeśli dowolne 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 okrąg nie będzie wewnątrz prostokąta, jeśli odległość jest większa niż połowa długość przekątnej prostokąta.

Powodzenia!

Oto Mój kod C do rozwiązania kolizji między kulą a nieosiowym wyrównanym polem. Opiera się na kilku moich własnych procedurach bibliotecznych, ale może okazać się przydatny dla niektórych. 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 wizualizować, weź klawiaturę numpad. Jeśli klawisz " 5 " reprezentuje twój prostokąt, to wszystkie klawisze 1-9 reprezentują 9 ćwiartek przestrzeni podzielonych przez linie, które tworzą twój prostokąt(z 5 jest wewnątrz.)

1) jeśli środek okręgu jest w kwadrancie 5 (tj. wewnątrz prostokąta), to dwa kształty przecinają się.

W związku z tym istnieją dwa możliwe przypadki: a) okrąg przecina się z dwoma lub więcej sąsiednimi krawędziami prostokąta. b) koło przecina się z jedną krawędzią prostokąta.

Pierwszy przypadek jest prosty. Jeśli okrąg przecina się z dwoma sąsiednimi krawędziami prostokąta, musi zawierać narożnik łączący te dwie krawędzie. (To lub jego centrum leży w kwadrancie 5, który już omówiliśmy. Należy również zauważyć, że przypadek, w którym okrąg przecina się tylko z dwoma przeciwstawnymi krawędziami prostokąta, jest również zakryty.)

2) Jeśli któryś z narożników A, B, C, D prostokąta leży wewnątrz okręgu, to te dwa kształty się przecinają.

Drugi przypadek jest trudniejszy. Należy zauważyć, że może się to zdarzyć tylko wtedy, gdy środek okręgu leży w jednym z ćwiartek 2, 4, 6 lub 8. (W rzeczywistości, jeśli środek znajduje się na którymkolwiek z ćwiartek 1, 3, 7, 8, odpowiedni róg będzie najbliżej niego.)

Teraz mamy przypadek, że środek okręgu znajduje się w jednej z ćwiartek 'krawędzi' i przecina się tylko z odpowiadającą mu krawędzią. Następnie punkt na krawędzi, który jest najbliżej środek okręgu, musi leżeć wewnątrz okręgu.

3) dla każdej linii AB, BC, CD, DA, narysuj prostopadłe linie p(AB,P), p(BC,P), P(CD,P), P(DA,P) przez środek okręgu P. dla każdej linii prostopadłej, jeśli przecięcie z oryginalną krawędzią leży wewnątrz okręgu, to dwa kształty przecinają się.

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

Możesz skonstruować cztery przecięcia linii i sprawdzić, czy leżą one na odpowiednich krawędziach, lub dowiedzieć się, który kwadrant P jest w i sprawdzić odpowiednie przecięcie. Oba powinny uprościć do tego samego równania logicznego. Uważaj, że krok 2 powyżej nie wykluczył, że p jest w jednym z "narożnych" ćwiartek; po prostu szukał skrzyżowania.

Edit: jak się okazuje, przeoczyłem prosty fakt, że #2 jest podklasą #3 powyżej. Przecież rogi też są punktami na krawędziach. Zobacz odpowiedź @ShreevatsaR poniżej, aby uzyskać świetne Wyjaśnienie. A w międzyczasie zapomnij o # 2 powyżej, chyba że chcesz szybkiego, ale zbędnego sprawdzenia.

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

Uwaga:

/ align = "left" / pochodzenie.x i apochodzenie.y to współrzędne lewego dolnego kąta prostokąta!

/ align = "left" / x i aCircle.y są współrzędnymi środka okręgu!

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

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

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

Możesz zrobić to wszystko 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 potrzebujesz rozwiązania do obsługi kolizji między poruszającym się okręgiem i prostokąt, jest o wiele bardziej skomplikowany i pokryty w innej mojej odpowiedzi.

Stworzyłem klasę do pracy z kształtami hope you enjoy

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

Tutaj Kod modfowany w 100% działa:

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

Oto szybki test jednowierszowy:

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

Jest to przypadek wyrównany do osi, gdzie rect_halves jest dodatnim wektorem skierowanym od środka prostokąta do rogu. Wyrażenie wewnątrz length() jest wektorem delty od center do najbliższego punktu prostokąta. To działa w każdym wymiarze.

• Najpierw sprawdź, czy prostokąt i kwadrat styczny do okręgu nakładają się na siebie (łatwo). Jeśli nie nakładają się, nie kolidują.
• Sprawdź, czy środek okręgu znajduje się wewnątrz prostokąta (easy). Jeśli jest w środku, zderzają się.
• Oblicz minimalną odległość kwadratową od boków prostokąta do środka okręgu (trochę twardy). Jeśli jest mniejsza niż promień kwadratowy, to zderzają się, inaczej nie.

• First it sprawdza najczęstszy scenariusz za pomocą taniego algorytmu i gdy jest pewien, że nie kolidują, kończy się.
• następnie sprawdza następny najczęstszy scenariusz za pomocą taniego algorytmu (nie obliczaj pierwiastka kwadratowego, używaj wartości kwadratu) i gdy jest pewne, że kolidują, kończy się.
• następnie wykonuje droższy algorytm sprawdzania kolizji z granicami prostokąta.

Mam metodę, która pozwala uniknąć kosztownego Pitagorasa, jeśli nie jest to konieczne - tj. gdy obwiednie prostokąta i okręgu nie przecinają się.

I będzie działać również dla nie-euklidesowych:

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że być zastąpiony przez minY, maxY i to samo dla minLon, maxLon: zastąp go minX, maxX
• normDist jest tylko nieco szybszą metodą niż obliczanie pełnej 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żywasz tej metody normDist, musisz utworzyć normedDist = dist*dist; dla okręgu

Zobacz pełny BBox i Circle kod mojego projektu GraphHopper .

Dla tych, którzy muszą obliczyć kolizję Okręgu / prostokąta we współrzędnych geograficznych z SQL,
to jest moja implementacja w oracle 11 e.James zasugerował algorytm .

W input wymaga współrzędnych okręgu, promienia okręgu w km oraz dwóch współrzędnych wierzchołków 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, wymyśliłem to tydzień temu, a teraz muszę to przetestować.

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

Zakładając, że masz cztery krawędzie prostokąta sprawdź odległość od krawędzi do środka okręgu, jeśli jest mniejszy niż promień, wtedy kształty przecinają się.

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 okręgu. Załóżmy, że cztery punkty prostokąta to A, B, C, D. przynajmniej jeden z nich powinien przecinać okrąg. jeśli więc odległość od jednego punktu do środka okręgu jest mniejsza niż promień okręgu, powinien on przecinać okrąg. Aby uzyskać odległość można użyć twierdzenia Pitagorasa,

H^2 = A^2 + B^2