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

192

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

aib
źródło
1
Czy prostokąt jest zawsze wyrównany z osiami, czy też można go obrócić o dowolny kąt?
e.James
11
@eJames: jak to ma znaczenie? Sprawdzasz prostokąt pod kątem przecięcia z okręgiem ; zawsze możesz przekształcić układ współrzędnych, tak aby prostokąt był równoległy do ​​osi bez zmiany koła :-)
ShreevatsaR
Powinieneś dodać to jako odpowiedź, obracając przez -Θ i wszystkie ...
aib
2
@ShreevatsaR: Ma to znaczenie bez względu na to, czy muszę martwić się tłumaczeniem koordynowanym, czy nie. @aib: Oh kochanie!
e.James

Odpowiedzi:

191

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.

Niektóre różne sposoby przecinania się koła i prostokąta

(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!

ShreevatsaR
źródło
25
Jeśli chodzi o wartość, naprawdę uważam, że ta odpowiedź jest lepsza niż moja. Dwa główne powody: 1: nie wymaga obrotu, jeśli prostokąt nie jest równoległy do ​​osi, oraz 2: koncepcja łatwo rozciąga się na wszystkie wielokąty.
e.James
2
@paniq: Cóż, oba mają stały czas. :-) Ale tak, jest to bardziej przydatne jako ogólne rozwiązanie, obejmujące prostokąty o dowolnej orientacji, a właściwie każdy prosty wielokąt.
ShreevatsaR
7
co z przypadkiem, w którym prostokąt jest całkowicie wewnątrz koła, ale środek koła nie znajduje się w tym prostokącie?
ericsoco
2
@ericsoco: Dobra obserwacja. :-) Wydaje mi się, że powinienem powiedzieć „przecina dysk” w „jednej z krawędzi prostokąta przecina koło”, ponieważ miałem na myśli to, że dzieli on punkt z samym okręgiem, niekoniecznie jego granicą. W każdym razie powyższy opis „sprawdź, czy stopa prostopadłej od P [środka okręgu] do linii jest wystarczająco blisko i między punktami końcowymi, i sprawdź punkty końcowe w przeciwnym razie” nadal będzie działać - np. Punkty końcowe leżą wewnątrz koła ( dysk).
ShreevatsaR
2
@ DexD.Hunter Jeśli środek okręgu znajduje się poza prostokątem, ale jego część znajduje się wewnątrz prostokąta, to koniecznie jedna z jego krawędzi przecina okrąg.
ShreevatsaR
289

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:

złudzenie

  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.

e.James
źródło
4
Bardzo dobrze! Uwagi: najwyraźniej tutaj rect.x / y znajduje się w prawym górnym rogu prostokąta. Możesz także wyeliminować kosztowny pierwiastek kwadratowy, porównując go z kwadratem promienia.
luqui,
2
O nie, mój zły. rect.x / y znajduje się w lewym dolnym rogu prostokąta. Napisałbym: circleDistance.x = abs (circle.x - (rect.x + rect.width / 2));
luqui,
2
@Tanner: Proszę bardzo. Brawo dla kopii zapasowych i OCD;)
e.James
11
tylko dla wyjaśnienia - ta odpowiedź dotyczy tylko prostokątów wyrównanych do osi. wynika to z przeczytania komentarzy do innych odpowiedzi, ale nie jest oczywiste z tej odpowiedzi + samych komentarzy. (świetna odpowiedź dla
prostokątów
3
Wspaniały! Ważne jest, aby czytelnicy wiedzieli, że tutaj uważam, że definicja odbicia to rect.xi rect.y są środkiem odbicia . W moim świecie xy rect jest góra / lewo od rect, a 0,0 to górna / lewej strony ekranu, więc użyłem:circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
Erco
123

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.

Cygon
źródło
3
Masz tam błąd, szukasz najbliższego z lewej i prawej, a nie z góry i z dołu, w przeciwnym razie cudowne rozwiązanie.
manveru
8
Najbardziej podoba mi się ta odpowiedź. Jest krótki, łatwy do zrozumienia i szybki.
John Kurlak,
2
Myślę, że twoje rozwiązanie zawodzi, jeśli prostokąt jest ukośny względem osi xi y.
Lew
3
@Leo Myślę, że nie jest trudno zmodyfikować ten algorytm, aby uwzględnić ten przypadek, należy po prostu zastosować transformację współrzędnych, w której początek znajduje się w środku prostokąta, a prostokąt nie jest już ukośny. Musisz zastosować transformację tylko do środka okręgu.
enobayram
1
Jest to w zasadzie taki sam, jak kod znaleziony na migapro.com/circle-and-rotated-rectangle-collision-detection, który również przeniosłem do Objective-C. Działa bardzo dobrze; to dobre rozwiązanie problemu.
PKCLsoft,
10

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.

użytkownik104676
źródło
1
Czy odległość między punktami nie powinna być oparta na kwadracie, a nie na abs?
Thomas
6

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.

intrepidis
źródło
3
Nie sądzę, że można twierdzić, że pięć testów / porównań w najdroższej ścieżce kodu jest „najszybszym rozwiązaniem” bez jakiegoś dowodu.
sam hocevar
1
Z mojego doświadczenia z tą metodą kolizja nie zdarza się przez większość czasu. Dlatego testy spowodują zakończenie wcześniej, zanim zostanie wykonana większość kodu.
intrepidis,
6

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.

ClickerMonkey
źródło
Nie wykryje to przecięcia, jeśli promień okręgu jest zbyt mały, a jego środek znajduje się w prostokącie!
Yoav
2
Czy możesz podać rzeczywiste dane wejściowe, które powodują, że to się nie udaje? Gdy okrąg jest w środku, lewa część testu wynosi 0,0. O ile promień nie jest zerowy, właściwa część testu powinna wynosić> 0,0
ClickerMonkey
Czy zadziała to również w przypadku obróconych prostokątów? jeśli nie, to proszę dać mi podpowiedź na ten temat .....
M Abdul Sami,
4

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!


źródło
3

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;
}
Madrayken
źródło
2

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.

aib
źródło
2

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;
}
Faraona
źródło
1

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.

Karussell
źródło
1

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;
  } 
}
pwipo
źródło
1

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

Bassam Alugili
źródło
1

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.

Tyler
źródło
1
  • 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.
David C.
źródło
1

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;
}
sandeep
źródło
hmmm ... Zagłosowałem, ale potem przetestowałem poprawnie i myślę, że to nie działa na przykład na rogach. Działa dla dwóch prostokątów.
Dan Zen
1

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.

Estid Felipe Lozano Reyes
źródło
0

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;    
fl4l
źródło
0

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)));
użytkownik3026859
źródło
Może działać dla Circle-Square, ale pytanie dotyczy Circle-Rectangle.
martineau,
0
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
Cassiano
źródło
-2

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
Dla Twojego dobra
źródło
Co z przypadkiem, w którym małe koło jest całkowicie otoczone dużym prostokątem? Z pewnością jest to skrzyżowanie i nie zdałoby testu w tej odpowiedzi.
Ken Paul
Ach tak, nie myślałem o tym. Możesz po prostu dodać więcej kontroli, np. Jeśli sqrt ((rectangleRight.x / 2 - circleCenter.x) ^ 2 + (rectangleBottom.y / 2 - circleCenter.y) ^ 2) <promień to przecinają się To będzie długie i wolne, ale z czubka mojej głowy jest to najlepsze, co mogę wymyślić.
ForYourOwnGood
Mogą przecinać się w dowolnym [jednym] punkcie na dowolnej krawędzi. Powinieneś również znaleźć odległości od środka krawędzi. (Och, nazywajcie swoje rogi „narożnikami” :)
aib
Wygląda na to, że wykrywa tylko, gdy narożnik znajduje się wewnątrz koła.
surowy
-2

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

Md. Ashraful Islam
źródło
Ta odpowiedź jest niezwykle nieprawidłowa za każdym razem, gdy prostokąt ma bok większy niż promień koła.
Paul K