Kreis-Rechteck collision detection (Schnitt)

Question

Wie kann ich feststellen, ob ein Kreis und ein Rechteck schneiden sich in 2D-euklidischen Raum?(d.h.klassische 2D-geometrie)

Answer 1

Es gibt nur zwei Fälle, wenn der Kreis schneidet Rechteck:

• Entweder der Kreis Zentrum liegt innerhalb des Rechtecks, oder
• Die Kanten des Rechtecks hat einen Punkt in den Kreis.

Beachten Sie, dass dies bedeutet nicht, dass das Rechteck an axis-parallel.

(Eine Möglichkeit, dies zu sehen:wenn keine der Kanten einen Punkt im Kreis (wenn alle Kanten sind komplett "außerhalb" der Kreis), dann besteht der einzige Weg, der Kreis kann noch intersect-polygon ist, wenn es liegt vollständig innerhalb des Polygons.)

Mit diesem Einblick etwas wie das folgende funktionieren wird, wo sich der Kreis hat den Mittelpunkt P und radius R, und der Rechteck-Eckpunkte A, B, C, D in dieser Reihenfolge (nicht vollständige code):

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

Wenn Sie schreiben, die geometrie, die Sie wahrscheinlich haben die oben genannten Funktionen in Ihrer Bibliothek bereits.Andernfalls pointInRectangle() umgesetzt werden kann in mehrere Möglichkeiten:jede von der Allgemeinen Punkt in polygon Methoden funktionieren, aber für ein Rechteck können Sie einfach prüfen, ob dies funktioniert:

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

Und intersectCircle() ist leicht zu implementieren, zu:eine Möglichkeit wäre zu überprüfen, ob der Fuß der senkrechten aus P die Linie ist nahe genug, und zwischen den Endpunkten, und überprüfen Sie die Endpunkte anders.

Die Coole Sache ist, dass die gleichen Idee funktioniert nicht nur Rechtecke, sondern für den Schnittpunkt eines Kreises mit einer beliebigen einfaches polygon — noch nicht konvex sein!

Answer 2

Hier ist, wie ich es tun würde:

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

Hier ist, wie es funktioniert:

1. Die ersten paar Zeilen berechnen Sie die absoluten Werte der x-und y-Differenz zwischen dem Mittelpunkt des Kreises und dem Mittelpunkt des Rechtecks.Dieses stürzt die vier Quadranten nach unten in einem, so dass die Berechnungen nicht durchgeführt werden müssen, vier mal.Das Bild zeigt den Bereich, in dem der Mittelpunkt des Kreises muss nun liegen.Beachten Sie, dass nur die einzelnen Quadranten angezeigt wird.Das Rechteck ist die Grau Bereich, und die roten Umrisse der kritische Bereich und das ist genau einem radius entfernt von den Kanten des Rechtecks.Der Mittelpunkt des Kreises innerhalb dieser roten Umrandung für die Kreuzung zu kommen.

2. Das zweite paar Linien, beseitigen Sie den einfachen Fällen, in denen der Kreis ist weit genug Weg von dem Rechteck (in jede Richtung), dass keine Kreuzung möglich ist.Dies entspricht der grüne Bereich im Bild.

3. Das Dritte paar Zeilen behandeln die einfachen Fälle, in denen der Kreis ist nahe genug, um das Rechteck (in beide Richtungen), die eine Kreuzung ist garantiert.Dies entspricht der orange und Grau Abschnitte in die Bild.Beachten Sie, dass dieser Schritt muss getan werden, nachdem Sie Schritt 2 für die Logik, Sinn zu machen.

4. Die restlichen Zeilen berechnen den schwierigen Fall, in dem der Kreis kann schneiden Sie die Ecke des Rechtecks.Zu lösen, berechnen der Abstand von der Mitte des Kreises und die Ecke, und dann stellen Sie sicher, dass der Abstand nicht mehr als der radius der Kreis.Diese Berechnung gibt false zurück, für alle Kreise, deren Zentrum innerhalb der rot schattierte Bereich und gibt true zurück, für alle Kreise, deren Zentrum ist in die weiß hinterlegten Bereich.

Answer 3

Hier ist eine andere Lösung, die ziemlich einfach zu implementieren ist (und ziemlich schnell, auch). Es werden alle Kreuzungen fangen, auch wenn die Kugel vollständig das Rechteck eingetreten ist.

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

Mit jeder anständigen Mathematik-Bibliothek, die auf 3 oder 4 Zeilen verkürzt werden kann.

Answer 4

Ihre Kugel und rect intersect IIF
der Abstand zwischen dem Kreiszentrum und einer Ecke Ihres rect ist kleiner als der Radius des Kugel
OR
der Abstand zwischen dem Kreiszentrum und einen Rand Ihres rect ist kleiner als der Radius des Kugel ([

Dies ist die schnellste Lösung:

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

Man beachte die Reihenfolge der Ausführung und die Hälfte der Breite / Höhe vorge berechnet. Auch ist die Quadratur „von Hand“ zu tun, einige Taktzyklen zu speichern.

Hier ist mein C-Code eine Kollision zwischen einer Kugel und einer Nicht-Achse ausgerichtet Box für die Lösung. Es stützt sich auf ein paar meiner eigenen Bibliotheksroutinen, aber es kann einige nützlich erweisen. Ich bin es in einem Spiel mit und es funktioniert perfekt.

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

Eigentlich ist dies sehr einfach ist.Du brauchst nur zwei Dinge.

Erste, Sie brauchen, zu finden, vier orthogonal Entfernungen von der Kreis-Center, um jede Zeile des Rechtecks.Dann ist Ihr Kreis wird nicht schneiden Sie das Rechteck, wenn drei von Ihnen sind größer als der Kreisradius.

Zweite, müssen Sie den Abstand zwischen kreismitte und den Rechteck-Mittelpunkt, dann umkreisen Sie werden nicht innerhalb des Rechtecks, wenn der Abstand größer ist als eine Hälfte des Rechtecks diagonal Länge.

Viel Glück!

Die einfachste Lösung, die ich habe kommen mit ist ziemlich einfach.

Es funktioniert durch den Punkt im Rechteck am nächsten zu dem Kreis zu finden, dann den Abstand zu vergleichen.

Sie können mit ein paar Operationen all dies tun, und sogar die Funktion sqrt vermeiden.

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

Und das ist es! Die obige Lösung nimmt einen Ursprung in der oberen linken Ecke der Welt mit der x-Achse nach unten zeigt.

Wenn Sie eine Lösung zur Handhabung von Kollisionen zwischen einem sich bewegenden Kreis und Rechteck wollen, ist es viel komplizierter und bedeckt in einer anderen Antwort von mir.

Zu visualisieren, nehmen Sie Ihre Tastatur numpad.Wenn die Taste '5' steht für Ihre Rechteck ist, dann werden alle Tasten 1-9 stellen die 9 Quadranten der Raum geteilt durch die Linien, aus denen sich das Rechteck (mit 5 innen.)

1) Wenn in der Mitte des Kreises ist in quadrant 5 (d.h.innerhalb des Rechtecks), dann die beiden Formen schneiden.

Mit diesem aus dem Weg, gibt es zwei mögliche Fälle:a) Der Kreis schneidet mit zwei oder mehr benachbarten Kanten des Rechtecks.b) Der Kreis schneidet mit einer Kante des Rechtecks.

Der erste Fall ist einfach.Wenn der Kreis schneidet mit zwei benachbarten Kanten des Rechtecks, Sie müssen enthalten die Ecke Verbindung dieser beiden Kanten.(Das, oder sein Zentrum liegt in quadrant 5, die wir bereits zurückgelegt haben.Beachten Sie auch, dass der Fall, wo sich der Kreis schneidet mit nur zwei gegnerischen die Kanten des Rechtecks wird abgedeckt.)

2) Wenn eine der Ecken A, B, C, D des Rechtecks liegen in den Kreis, dann die beiden Formen schneiden.

Der zweite Fall ist komplizierter.Wir sollten beachten, dass es kann nur passieren, wenn der Mitte des Kreises, liegt in einem der Quadranten 2, 4, 6 oder 8.(In der Tat, wenn das center ist auf einem der Quadranten 1, 3, 7, 8, die entsprechende Ecke wird der nächstgelegene Punkt an ihn.)

Jetzt haben wir den Fall, dass der Mitte des Kreises ist in einem der 'edge' Quadranten, und es schneidet nur mit der entsprechenden Kante.Dann den Punkt auf der Kante, die ist am nächsten an der Mitte des Kreises liegen müssen innerhalb des Kreises.

3) Für jede Zeile AB, BC, CD, DA, konstruieren, die senkrechten Linien p(AB,P), p(BC,P), p(CD,P), p(DA,P) über der Mitte des Kreises P.Für jede senkrechte Linie, wenn der Schnittpunkt mit der original-edge liegt in den Kreis, dann die beiden Formen schneiden.

Es ist eine Abkürzung für diesen letzten Schritt.Wenn der Mitte des Kreises ist in quadrant 8-und die Kante AB ist AB der Oberkante, der Schnittpunkt wird die y-Koordinate von A und B, und der x-Koordinate des center P.

Sie können bauen die vier line-Kreuzungen und prüfen Sie, ob Sie liegen auf den entsprechenden Kanten, oder finden Sie heraus, welchem Quadranten P-in-und check den entsprechenden Schnittpunkt.Beide vereinfachen sollte auf die gleiche Boolesche Gleichung.Vorsichtig sein, dass der Schritt 2 oben nicht die Regel P wird in einer der 'Ecke' Quadranten;es sah nur für eine Kreuzung.

Edit:Wie es sich herausstellt, habe ich übersehen die einfache Tatsache, dass die #2 ist ein subcase #3 oben.Nachdem alle, die Ecken sind auch Punkte auf den Kanten.Siehe @ShreevatsaR Antwort unten für eine Super Erklärung.Und in der Zwischenzeit vergessen #2 oben, es sei denn, Sie möchten eine schnelle, aber redundant check.

Diese Funktion erkennt Kollisionen (Kreuzungen) zwischen Kreis und Rechteck.Er funktioniert wie e.James Methode in seiner Antwort, aber diese Kollisionen für alle Winkel des Rechtecks (nicht nur rechts oben in der Ecke).

HINWEIS:

aRect.Herkunft.x und aRect.Herkunft.y sind die Koordinaten der linken unteren Winkel des Rechtecks!

aCircle.x und aCircle.y sind die Koordinaten der kreismitte!

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

Ich habe Klasse für die Arbeit mit Formen Hoffnung genießen Sie

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

Hier ist das modfied Code Funktion 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

Hier ist ein schneller One-Line-Test für diese:

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

Dies ist die Achse ausgerichtet Fall, in dem rect_halves ein positiver Vektor aus dem Rechteck Mitte zeigt auf eine Ecke. Der Ausdruck innerhalb length() ist ein Deltavektor von center zu einem nächstgelegenen Punkt im Rechteck. Dies funktioniert in jeder Dimension.

• Prüfen Sie zunächst, ob das Rechteck und das Quadrat Tangente an den Kreis überlappt (leicht).Wenn Sie nicht überlappt, Sie tun nicht kollidieren.
• Überprüfen Sie, ob der circle ' s center ist innerhalb des Rechtecks (leicht).Wenn es drin ist, kollidieren.
• Berechnen Sie die minimale Quadrat der Entfernung von der Rechteck-Seiten zu der Mitte des Kreises (wenig schwer).Wenn es ist niedriger als der quadrierte radius, dann stoßen Sie zusammen, sonst nicht.

Es ist effizient, weil:

• Zuerst prüft es das häufigste Szenario mit einem Billig-Algorithmus, und wenn es Sie sicher, Sie tun nicht kollidieren, endet es.
• Dann überprüft er die nächste häufigste Szenario mit einem Billig-Algorithmus (nicht berechnen, square root, verwenden Sie die Quadrat-Werte), und wenn es Sie sicher, dass Sie kollidieren es endet.
• Dann führt er die teurer Algorithmus, um zu überprüfen Kollision mit dem Rechteck Grenzen.

Ich habe eine Methode, die verhindert, das teure pythagoras, wenn nicht sogar notwendig - ie.wenn die bounding-Boxen der das Rechteck und den Kreis nicht schneiden.

Und es wird funktionieren für nicht-euklidischen zu:

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, können ersetzt werden mit minY,maxY und das gleiche gilt für Produktnamen mit der Kennzeichnung, maxLon:ersetzen Sie es mit minX, maxX
• NORMVERT ist nur eine etwas schnellere Methode, dann die volle Distanz-Berechnung.E. g.ohne die Quadrat-Wurzel im euklidischen Raum (oder ohne eine Menge anderer Sachen für die haversine): dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon.Natürlich, wenn Sie verwenden, dass NORMVERT Methode, die Sie tun müssen, erstellen Sie eine normedDist = dist*dist; für den Kreis

Sie finden die vollständige BBox und Kreis mein code GraphHopper Projekt.

Für diejenigen, haben Kreis / Rechteck Kollision in geographischen Koordinaten mit SQL,
berechnen dies ist meine Implementierung in Oracle 11 von e.James Algorithmus vorgeschlagen.

In Eingabe erfordert es Kreiskoordinaten, Kreisradius in km und zwei Scheitelkoordinaten des Rechtecks:

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;    

Works, gerade diese rechnete vor einer Woche aus, und gerade jetzt haben, um es zu testen.

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

Vorausgesetzt, Sie haben die vier Kanten des Rechtecks überprüfen Sie den Abstand von den Rändern zur Mitte des Kreises, wenn Ihr weniger als den radius, dann die Formen schneiden.

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

Wenn das Rechteck schneidet den Kreis, eine oder mehrere Eckpunkte des Rechtecks sollte drin sein in den Kreis.Angenommen, ein Rechteck ist, sind vier Punkte A,B,C,D.mindestens einer von Ihnen sollte schneiden Sie den Kreis.so, wenn die Distanz von einem Punkt zum Mittelpunkt des Kreises ist kleiner als der radius des Kreises, Sie sollten schneiden Sie den Kreis.Um die Entfernung, die Sie können verwenden Sie den Satz des Pythagoras,

H^2 = A^2 + B^2

Diese Technik hat einige Grenzen.Aber es wird besser funktionieren, für die Spiel-Entwickler.besonders collision detection

Es ist ein gutes update zu Arvo-Algorithmus

Answer 5

Answer 6

Answer 7

Dies ist die schnellste Lösung:

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

Man beachte die Reihenfolge der Ausführung und die Hälfte der Breite / Höhe vorge berechnet. Auch ist die Quadratur „von Hand“ zu tun, einige Taktzyklen zu speichern.

Answer 8

Hier ist mein C-Code eine Kollision zwischen einer Kugel und einer Nicht-Achse ausgerichtet Box für die Lösung. Es stützt sich auf ein paar meiner eigenen Bibliotheksroutinen, aber es kann einige nützlich erweisen. Ich bin es in einem Spiel mit und es funktioniert perfekt.

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

Eigentlich ist dies sehr einfach ist.Du brauchst nur zwei Dinge.

Erste, Sie brauchen, zu finden, vier orthogonal Entfernungen von der Kreis-Center, um jede Zeile des Rechtecks.Dann ist Ihr Kreis wird nicht schneiden Sie das Rechteck, wenn drei von Ihnen sind größer als der Kreisradius.

Zweite, müssen Sie den Abstand zwischen kreismitte und den Rechteck-Mittelpunkt, dann umkreisen Sie werden nicht innerhalb des Rechtecks, wenn der Abstand größer ist als eine Hälfte des Rechtecks diagonal Länge.

Viel Glück!

Answer 9

Hier ist mein C-Code eine Kollision zwischen einer Kugel und einer Nicht-Achse ausgerichtet Box für die Lösung. Es stützt sich auf ein paar meiner eigenen Bibliotheksroutinen, aber es kann einige nützlich erweisen. Ich bin es in einem Spiel mit und es funktioniert perfekt.

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

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

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

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

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

        CREATE_VECTOR(push_vector);         

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

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

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

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

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

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

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

Answer 10

Eigentlich ist dies sehr einfach ist.Du brauchst nur zwei Dinge.

Erste, Sie brauchen, zu finden, vier orthogonal Entfernungen von der Kreis-Center, um jede Zeile des Rechtecks.Dann ist Ihr Kreis wird nicht schneiden Sie das Rechteck, wenn drei von Ihnen sind größer als der Kreisradius.

Zweite, müssen Sie den Abstand zwischen kreismitte und den Rechteck-Mittelpunkt, dann umkreisen Sie werden nicht innerhalb des Rechtecks, wenn der Abstand größer ist als eine Hälfte des Rechtecks diagonal Länge.

Viel Glück!

Answer 11

Die einfachste Lösung, die ich habe kommen mit ist ziemlich einfach.

Es funktioniert durch den Punkt im Rechteck am nächsten zu dem Kreis zu finden, dann den Abstand zu vergleichen.

Sie können mit ein paar Operationen all dies tun, und sogar die Funktion sqrt vermeiden.

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

Und das ist es! Die obige Lösung nimmt einen Ursprung in der oberen linken Ecke der Welt mit der x-Achse nach unten zeigt.

Wenn Sie eine Lösung zur Handhabung von Kollisionen zwischen einem sich bewegenden Kreis und Rechteck wollen, ist es viel komplizierter und bedeckt in einer anderen Antwort von mir.

Answer 12

Answer 13

Die einfachste Lösung, die ich habe kommen mit ist ziemlich einfach.

Es funktioniert durch den Punkt im Rechteck am nächsten zu dem Kreis zu finden, dann den Abstand zu vergleichen.

Sie können mit ein paar Operationen all dies tun, und sogar die Funktion sqrt vermeiden.

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

Und das ist es! Die obige Lösung nimmt einen Ursprung in der oberen linken Ecke der Welt mit der x-Achse nach unten zeigt.

Answer 14

Wenn Sie eine Lösung zur Handhabung von Kollisionen zwischen einem sich bewegenden Kreis und Rechteck wollen, ist es viel komplizierter und bedeckt

Answer 15

Zu visualisieren, nehmen Sie Ihre Tastatur numpad.Wenn die Taste '5' steht für Ihre Rechteck ist, dann werden alle Tasten 1-9 stellen die 9 Quadranten der Raum geteilt durch die Linien, aus denen sich das Rechteck (mit 5 innen.)

1) Wenn in der Mitte des Kreises ist in quadrant 5 (d.h.innerhalb des Rechtecks), dann die beiden Formen schneiden.

Mit diesem aus dem Weg, gibt es zwei mögliche Fälle:a) Der Kreis schneidet mit zwei oder mehr benachbarten Kanten des Rechtecks.b) Der Kreis schneidet mit einer Kante des Rechtecks.

Der erste Fall ist einfach.Wenn der Kreis schneidet mit zwei benachbarten Kanten des Rechtecks, Sie müssen enthalten die Ecke Verbindung dieser beiden Kanten.(Das, oder sein Zentrum liegt in quadrant 5, die wir bereits zurückgelegt haben.Beachten Sie auch, dass der Fall, wo sich der Kreis schneidet mit nur zwei gegnerischen die Kanten des Rechtecks wird abgedeckt.)

2) Wenn eine der Ecken A, B, C, D des Rechtecks liegen in den Kreis, dann die beiden Formen schneiden.

Der zweite Fall ist komplizierter.Wir sollten beachten, dass es kann nur passieren, wenn der Mitte des Kreises, liegt in einem der Quadranten 2, 4, 6 oder 8.(In der Tat, wenn das center ist auf einem der Quadranten 1, 3, 7, 8, die entsprechende Ecke wird der nächstgelegene Punkt an ihn.)

Jetzt haben wir den Fall, dass der Mitte des Kreises ist in einem der 'edge' Quadranten, und es schneidet nur mit der entsprechenden Kante.Dann den Punkt auf der Kante, die ist am nächsten an der Mitte des Kreises liegen müssen innerhalb des Kreises.

3) Für jede Zeile AB, BC, CD, DA, konstruieren, die senkrechten Linien p(AB,P), p(BC,P), p(CD,P), p(DA,P) über der Mitte des Kreises P.Für jede senkrechte Linie, wenn der Schnittpunkt mit der original-edge liegt in den Kreis, dann die beiden Formen schneiden.

Es ist eine Abkürzung für diesen letzten Schritt.Wenn der Mitte des Kreises ist in quadrant 8-und die Kante AB ist AB der Oberkante, der Schnittpunkt wird die y-Koordinate von A und B, und der x-Koordinate des center P.

Sie können bauen die vier line-Kreuzungen und prüfen Sie, ob Sie liegen auf den entsprechenden Kanten, oder finden Sie heraus, welchem Quadranten P-in-und check den entsprechenden Schnittpunkt.Beide vereinfachen sollte auf die gleiche Boolesche Gleichung.Vorsichtig sein, dass der Schritt 2 oben nicht die Regel P wird in einer der 'Ecke' Quadranten;es sah nur für eine Kreuzung.

Edit:Wie es sich herausstellt, habe ich übersehen die einfache Tatsache, dass die #2 ist ein subcase #3 oben.Nachdem alle, die Ecken sind auch Punkte auf den Kanten.Siehe @ShreevatsaR Antwort unten für eine Super Erklärung.Und in der Zwischenzeit vergessen #2 oben, es sei denn, Sie möchten eine schnelle, aber redundant check.

Answer 16

Diese Funktion erkennt Kollisionen (Kreuzungen) zwischen Kreis und Rechteck.Er funktioniert wie e.James Methode in seiner Antwort, aber diese Kollisionen für alle Winkel des Rechtecks (nicht nur rechts oben in der Ecke).

HINWEIS:

aRect.Herkunft.x und aRect.Herkunft.y sind die Koordinaten der linken unteren Winkel des Rechtecks!

aCircle.x und aCircle.y sind die Koordinaten der kreismitte!

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

Answer 17

Ich habe Klasse für die Arbeit mit Formen Hoffnung genießen Sie

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

Answer 18

Hier ist das modfied Code Funktion 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

Answer 19

Hier ist ein schneller One-Line-Test für diese:

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

Dies ist die Achse ausgerichtet Fall, in dem rect_halves ein positiver Vektor aus dem Rechteck Mitte zeigt auf eine Ecke. Der Ausdruck innerhalb length() ist ein Deltavektor von center zu einem nächstgelegenen Punkt im Rechteck. Dies funktioniert in jeder Dimension.

Answer 20

• Prüfen Sie zunächst, ob das Rechteck und das Quadrat Tangente an den Kreis überlappt (leicht).Wenn Sie nicht überlappt, Sie tun nicht kollidieren.
• Überprüfen Sie, ob der circle ' s center ist innerhalb des Rechtecks (leicht).Wenn es drin ist, kollidieren.
• Berechnen Sie die minimale Quadrat der Entfernung von der Rechteck-Seiten zu der Mitte des Kreises (wenig schwer).Wenn es ist niedriger als der quadrierte radius, dann stoßen Sie zusammen, sonst nicht.

Es ist effizient, weil:

• Zuerst prüft es das häufigste Szenario mit einem Billig-Algorithmus, und wenn es Sie sicher, Sie tun nicht kollidieren, endet es.
• Dann überprüft er die nächste häufigste Szenario mit einem Billig-Algorithmus (nicht berechnen, square root, verwenden Sie die Quadrat-Werte), und wenn es Sie sicher, dass Sie kollidieren es endet.
• Dann führt er die teurer Algorithmus, um zu überprüfen Kollision mit dem Rechteck Grenzen.

Answer 21

Ich habe eine Methode, die verhindert, das teure pythagoras, wenn nicht sogar notwendig - ie.wenn die bounding-Boxen der das Rechteck und den Kreis nicht schneiden.

Und es wird funktionieren für nicht-euklidischen zu:

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, können ersetzt werden mit minY,maxY und das gleiche gilt für Produktnamen mit der Kennzeichnung, maxLon:ersetzen Sie es mit minX, maxX
• NORMVERT ist nur eine etwas schnellere Methode, dann die volle Distanz-Berechnung.E. g.ohne die Quadrat-Wurzel im euklidischen Raum (oder ohne eine Menge anderer Sachen für die haversine): dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon.Natürlich, wenn Sie verwenden, dass NORMVERT Methode, die Sie tun müssen, erstellen Sie eine normedDist = dist*dist; für den Kreis

Sie finden die vollständige BBox und Kreis mein code GraphHopper Projekt.

Answer 22

Für diejenigen, haben Kreis / Rechteck Kollision in geographischen Koordinaten mit SQL,
berechnen dies ist meine Implementierung in Oracle 11 von e.James Algorithmus vorgeschlagen.

In Eingabe erfordert es Kreiskoordinaten, Kreisradius in km und zwei Scheitelkoordinaten des Rechtecks:

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;    

Answer 23

Works, gerade diese rechnete vor einer Woche aus, und gerade jetzt haben, um es zu testen.

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

Answer 24

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

Answer 25

Vorausgesetzt, Sie haben die vier Kanten des Rechtecks überprüfen Sie den Abstand von den Rändern zur Mitte des Kreises, wenn Ihr weniger als den radius, dann die Formen schneiden.

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

Answer 26

Wenn das Rechteck schneidet den Kreis, eine oder mehrere Eckpunkte des Rechtecks sollte drin sein in den Kreis.Angenommen, ein Rechteck ist, sind vier Punkte A,B,C,D.mindestens einer von Ihnen sollte schneiden Sie den Kreis.so, wenn die Distanz von einem Punkt zum Mittelpunkt des Kreises ist kleiner als der radius des Kreises, Sie sollten schneiden Sie den Kreis.Um die Entfernung, die Sie können verwenden Sie den Satz des Pythagoras,

H^2 = A^2 + B^2

Diese Technik hat einige Grenzen.Aber es wird besser funktionieren, für die Spiel-Entwickler.besonders collision detection

Es ist ein gutes update zu Arvo-Algorithmus