Détection de collision cercle-rectangle (intersection)

Question

Comment puis-je savoir si un cercle et un rectangle s'intersectent dans l'espace euclidien 2D ? (c'est-à-dire en géométrie 2D classique)

Answer 1

Voici comment je le ferais :

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

Voici comment cela fonctionne :

1. Les deux premières lignes calculent les valeurs absolues de la différence en x et en y entre le centre du cercle et le centre du rectangle. Cela réduit les quatre quadrants en un seul, de sorte que les calculs ne doivent pas être effectués quatre fois. L'image montre la zone dans laquelle le centre du cercle doit maintenant se trouver. Notez que seul le quadrant unique est montré. Le rectangle est la zone grise, et la bordure rouge délimite la zone critique qui est exactement à une distance d'un rayon des bords du rectangle. Le centre du cercle doit se trouver à l'intérieur de cette bordure rouge pour que l'intersection se produise.

2. Les deux lignes suivantes éliminent les cas simples où le cercle est suffisamment éloigné du rectangle (dans n'importe quelle direction) pour qu'aucune intersection ne soit possible. Cela correspond à la zone verte dans l'image.

3. Les deux lignes suivantes traitent les cas simples où le cercle est suffisamment proche du rectangle (dans n'importe quelle direction) pour qu'une intersection soit garantie. Cela correspond aux sections orange et grise dans l'image. Notez que cette étape doit être réalisée après l'étape 2 pour que la logique ait un sens.

4. Les lignes restantes calculent le cas difficile où le cercle peut intersecter le coin du rectangle. Pour résoudre cela, calculez la distance entre le centre du cercle et le coin, puis vérifiez que la distance n'est pas supérieure au rayon du cercle. Ce calcul renvoie faux pour tous les cercles dont le centre se trouve dans la zone ombrée en rouge et renvoie vrai pour tous les cercles dont le centre se trouve dans la zone ombrée en blanc.

Answer 2

Il n'y a que deux cas où le cercle coupe le rectangle :

• Soit le centre du cercle se trouve à l'intérieur du rectangle, ou
• Une des arêtes du rectangle a un point dans le cercle.

Remarquez que cela ne nécessite pas que le rectangle soit aligné sur les axes.

(Une façon de voir ceci : si aucune des arêtes n'a un point dans le cercle (si toutes les arêtes sont complètement "à l'extérieur" du cercle), alors le seul moyen pour le cercle de croiser encore le polygone est s'il se trouve entièrement à l'intérieur du polygone.)

Avec cette idée en tête, quelque chose comme ce qui suit fonctionnera, où le cercle a pour centre P et pour rayon R, et le rectangle a pour sommets A, B, C, D dans cet ordre (non code complet) :

def intersect(Cercle(P, R), Rectangle(A, B, C, D)):
    S = Cercle(P, R)
    return (pointDansRectangle(P, Rectangle(A, B, C, D)) or
            intersecterCercle(S, (A, B)) or
            intersecterCercle(S, (B, C)) or
            intersecterCercle(S, (C, D)) or
            intersecterCercle(S, (D, A)))

Si vous écrivez de la géométrie, vous avez probablement déjà ces fonctions ci-dessus dans votre bibliothèque. Sinon, pointDansRectangle() peut être implémenté de plusieurs manières ; n'importe quelle méthode générale de point dans un polygone fonctionnera, mais pour un rectangle vous pouvez simplement vérifier si cela fonctionne :

0 ≤ AP·AB ≤ AB·AB et 0 ≤ AP·AD ≤ AD·AD

Et intersecterCercle() est également facile à implémenter : une façon serait de vérifier si le pied de la perpendiculaire de P à la ligne est assez proche et entre les points d'extrémité, et de vérifier les points d'extrémité sinon.

La chose cool est que la même idée fonctionne non seulement pour les rectangles mais pour l'intersection d'un cercle avec n'importe quel polygone simple — pas besoin d'être convexe !

Answer 3

Voici une autre solution assez simple à mettre en œuvre (et assez rapide aussi). Elle détectera toutes les intersections, y compris lorsque la sphère est entièrement entrée dans le rectangle.

// clamp(value, min, max) - limite la valeur à la plage min..max

// Trouver le point le plus proche du cercle dans le rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);

// Calculer la distance entre le centre du cercle et ce point le plus proche
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// Si la distance est inférieure au rayon du cercle, une intersection se produit
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

Avec une bibliothèque mathématique décente, cela peut être réduit à 3 ou 4 lignes.

Answer 4

Votre sphère et votre rectangle s'intersectent SI
la distance entre le centre du cercle et un sommet de votre rectangle est plus petite que le rayon de votre sphère
OU
la distance entre le centre du cercle et un bord de votre rectangle est plus petite que le rayon de votre sphère ([distance point-ligne ])
OU
le centre du cercle est à l'intérieur du rectangle

distance point-point:

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

distance point-ligne:

L1 = \[x1,y1\],L2 = \[x2,y2\] (deux points de votre ligne, c'est-à-dire les points de sommet)
P1 = \[px,py\] un point

Distance d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

centre du cercle à l'intérieur du rectangle:
utilisez une approche par axes de séparation: s'il existe une projection sur une ligne qui sépare le rectangle du point, ils ne s'intersectent pas

vous projetez le point sur des lignes parallèles aux côtés de votre rectangle et pouvez alors facilement déterminer s'ils s'intersectent. s'ils ne s'intersectent pas sur les 4 projections, ils (le point et le rectangle) ne peuvent pas s'intersecter.

vous avez juste besoin du produit scalaire ( x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 )

votre test ressemblerait à cela:

//bords du rectangle: TL (en haut à gauche), TR (en haut à droite), BL (en bas à gauche), BR (en bas à droite)
//point à tester: POI

séparé = false
pour bord dans { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // les bords
    D = bord\[0\] - bord\[1\]
    produitInterne =  D \* POI
    Interval\_min = min(D\*bord\[0\],D\*bord\[1\])
    Interval\_max = max(D\*bord\[0\],D\*bord\[1\])
    si non (  Interval\_min ≤ produitInterne ≤  Interval\_max ) 
           séparé = true
           break  // fin de la boucle for 
    fin si
fin pour
si (séparé est vrai)    
      return "pas d'intersection"
sinon 
      return "intersection"
fin si

cela ne suppose pas un rectangle aligné sur les axes et est facilement adaptable pour tester les intersections entre ensembles convexes.

Answer 5

Ceci est la solution la plus rapide :

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

Notez l'ordre d'exécution, et la moitié de la largeur/hauteur est précalculée. De plus, les carrés sont calculés "manuellement" pour économiser quelques cycles d'horloge.