Détection de collision cercle-rectangle (intersection)

192

Comment savoir si un cercle et un rectangle se croisent dans un espace euclidien 2D? (c'est-à-dire géométrie 2D classique)

aib
la source
1
Le rectangle est-il toujours aligné sur les axes ou peut-il être tourné d'un angle arbitraire?
e.James
11
@eJames: qu'est-ce que c'est important? Vous vérifiez le rectangle pour l'intersection avec un cercle ; vous pouvez toujours transformer votre système de coordonnées pour que le rectangle soit parallèle à l'axe sans changement dans le cercle :-)
ShreevatsaR
Vous devriez ajouter cela comme réponse, en tournant à travers -Θ et tout ...
aib
2
@ShreevatsaR: Cela compte si je dois m'inquiéter ou non de cette traduction coordonnée. @aib: Oh mon Dieu!
e.James

Réponses:

192

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

  • Soit le centre du cercle se trouve à l'intérieur du rectangle, soit
  • L'un des bords du rectangle a un point dans le cercle.

Notez que cela ne nécessite pas que le rectangle soit parallèle à l'axe.

Différentes façons dont un cercle et un rectangle peuvent se croiser

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

Avec cette idée, quelque chose comme ce qui suit fonctionnera, où le cercle a le centre Pet le rayon R, et le rectangle a sommets A, B, C, Ddans cet ordre (code non complet):

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

Si vous écrivez une géométrie, vous avez probablement déjà les fonctions ci-dessus dans votre bibliothèque. Sinon, pointInRectangle()peut être mis en œuvre de plusieurs manières; n'importe quel point général des méthodes polygonales fonctionnera, mais pour un rectangle, vous pouvez simplement vérifier si cela fonctionne:

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

Et intersectCircle()c'est facile à mettre en œuvre aussi: une façon serait de vérifier si le pied de la perpendiculaire de Pà la ligne est suffisamment proche et entre les extrémités, et de vérifier les extrémités autrement.

Ce qui est cool, c'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 - n'a même pas besoin d'être convexe!

ShreevatsaR
la source
25
Pour ce que ça vaut, je pense vraiment que cette réponse est meilleure que la mienne. Deux raisons principales: 1: il ne nécessite pas de rotation si le rectangle n'est pas parallèle à l'axe, et, 2: le concept s'étend facilement à tous les polygones.
e.James
2
@paniq: Eh bien, les deux sont à temps constant. :-) Mais oui, c'est plus utile comme solution générale, couvrant des rectangles avec n'importe quelle orientation, et en fait n'importe quel polygone simple.
ShreevatsaR
7
qu'en est-il du cas où le rectangle est complètement à l'intérieur du cercle, mais le centre du cercle n'est pas dans le rectangle?
ericsoco
2
@ericsoco: Bonne observation. :-) J'imagine que j'aurais dû dire "intersecte le disque" dans "l'un des bords du rectangle coupe le cercle", parce que je voulais dire qu'il partage un point avec le cercle lui-même, pas nécessairement la limite du cercle. Quoi qu'il en soit, la description ci-dessus, "vérifiez si le pied de la perpendiculaire de P [le centre du cercle] à la ligne est suffisamment proche et entre les extrémités, et vérifiez les extrémités sinon" fonctionnera toujours - par exemple, les extrémités se trouvent à l'intérieur du cercle ( disque).
ShreevatsaR
2
@ DexD.Hunter Si le centre du cercle est à l'extérieur du rectangle, mais qu'une partie de celui-ci se trouve à l'intérieur du rectangle, alors nécessairement l'un des bords du rectangle coupe le cercle.
ShreevatsaR
289

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 ça fonctionne:

illusion

  1. La première paire de lignes calcule les valeurs absolues de la différence x et 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 affiché. Le rectangle est la zone grise et la bordure rouge délimite la zone critique qui est exactement à un rayon des bords du rectangle. Le centre du cercle doit être à l'intérieur de cette bordure rouge pour que l'intersection se produise.

  2. La deuxième paire de lignes élimine les cas faciles où le cercle est suffisamment éloigné du rectangle (dans les deux sens) pour qu'aucune intersection ne soit possible. Cela correspond à la zone verte de l'image.

  3. La troisième paire de lignes gère les cas faciles où le cercle est suffisamment proche du rectangle (dans les deux sens) pour qu'une intersection soit garantie. Cela correspond aux sections orange et grise de l'image. Notez que cette étape doit être effectué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 croiser le coin du rectangle. Pour résoudre, 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 rouge et renvoie vrai pour tous les cercles dont le centre se trouve dans la zone ombrée blanche.

e.James
la source
4
Très agréable! Notes: apparemment ici, rect.x / y est dans le coin supérieur droit du rectangle. Vous pouvez également éliminer la racine carrée coûteuse, en comparant plutôt avec le carré du rayon.
luqui
2
Oh non, mon mal. rect.x / y est en bas à gauche du rectangle. J'aurais écrit: circleDistance.x = abs (circle.x - (rect.x + rect.width / 2));
luqui
2
@Tanner: On y va. Hourra pour les sauvegardes et le TOC;)
e.James
11
juste pour clarifier - cette réponse s'applique uniquement aux rectangles alignés sur l'axe. c'est clair à la lecture des commentaires sur d'autres réponses mais pas évident à partir de cette réponse + commentaires seuls. (excellente réponse pour les rects alignés sur l'axe!)
ericsoco
3
Génial! Il est important que les lecteurs sachent qu'ici je crois que la définition d'un rect est rect.x et rect.y sont le centre du rect. Dans mon monde, le xy d'un rect est en haut / à gauche de rect, et 0,0 en haut / à gauche de l'écran, j'ai donc utilisé:circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
erco
123

Voici une autre solution assez simple à mettre en œuvre (et assez rapide aussi). Il capturera toutes les intersections, y compris lorsque la sphère est complètement entrée dans le rectangle.

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

Avec n'importe quelle bibliothèque mathématique décente, cela peut être raccourci à 3 ou 4 lignes.

Cygone
la source
3
Vous avez un bug là-dedans, vous recherchez le plus procheY avec Gauche et Droite, pas Haut et Bas, sinon belle solution.
manveru
8
J'aime bien cette réponse. C'est court, facile à comprendre et rapide.
John Kurlak
2
Je pense que votre solution échoue si le rectangle est oblique par rapport aux axes x et y.
Leo
3
@Leo Je pense qu'il n'est pas difficile de modifier cet algorithme pour s'adapter à ce cas, il faut simplement appliquer une transformation de coordonnées où l'origine est au centre du rectangle et le rectangle n'est plus oblique. Vous devez appliquer la transformation au centre du cercle uniquement.
enobayram
1
C'est fondamentalement le même que le code trouvé sur migapro.com/circle-and-rotated-rectangle-collision-detection que j'ai également porté sur Objective-C. Fonctionne très bien; c'est une belle solution au problème.
PKCLsoft
10

votre sphère et votre rect se croisent IIF
la distance entre le centre du cercle et un sommet de votre rect est plus petite que le rayon de votre sphère
OU
la distance entre le centre du cercle et un bord de votre rect est plus petite que le rayon de votre sphère ( [ distance point-ligne ])
OU
le centre du cercle est à l'intérieur de la

distance point-point rect :

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 droite, c'est-à-dire les points de sommet)
P1 = [px, py] un certain point

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


centre du cercle à l'intérieur du rect:
prenez une approche d'axes séparés: s'il existe une projection sur une ligne qui sépare le rectangle du point, ils ne se croisent pas

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

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

votre test ressemblerait à ça:

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

séparé = faux
par exemple dans {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}: // les arêtes
    D = arête [0] - arête [1]
    innerProd = D * POI
    Interval_min = min (D * bord [0], D * bord [1])
    Interval_max = max (D * bord [0], D * bord [1])
    sinon (Interval_min ≤ innerProd ≤ Interval_max) 
           séparé = vrai
           break // fin pour la boucle 
    fin si
fin pour
si (séparé est vrai)    
      retourne "pas d'intersection"
autre 
      retourne "intersection"
fin si

cela ne suppose pas un rectangle aligné sur l'axe et est facilement extensible pour tester les intersections entre des ensembles convexes.

utilisateur104676
la source
1
La distance point à point ne devrait-elle pas utiliser un carré, pas un abs?
Thomas
6

C'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. La mise au carré est également effectuée "manuellement" pour enregistrer certains cycles d'horloge.

intrépidis
la source
3
Je ne pense pas que vous puissiez prétendre que cinq tests / comparaisons dans le chemin de code le plus cher sont la «solution la plus rapide» sans preuve.
sam hocevar
1
D'après mon expérience avec cette méthode, les collisions ne se produisent pas la plupart du temps. Par conséquent, les tests provoqueront une sortie avant que la plupart du code ne soit exécuté.
intrepidis
6

La solution la plus simple que j'ai trouvée est assez simple.

Cela fonctionne en trouvant le point dans le rectangle le plus proche du cercle, puis en comparant la distance.

Vous pouvez faire tout cela avec quelques opérations, et même éviter la fonction 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;
}

Et c'est tout! La solution ci-dessus suppose une origine dans le coin supérieur gauche du monde avec l'axe des x pointant vers le bas.

Si vous voulez une solution pour gérer les collisions entre un cercle et un rectangle en mouvement, c'est beaucoup plus compliqué et couvert dans une autre de mes réponses.

ClickerMonkey
la source
Cela échouera à détecter les intersections si le rayon du cercle est trop petit et que son centre est à l'intérieur du rectangle!
Yoav
2
Pouvez-vous fournir une entrée réelle qui fait échouer cet échec? Lorsque le cercle est à l'intérieur, la partie gauche du test est de 0,0. À moins que le rayon ne soit égal à zéro, la partie droite du test doit être> 0,0
ClickerMonkey
Cela fonctionnera-t-il aussi pour les rectangles pivotés? sinon, donnez-moi un indice à ce sujet .....
M Abdul Sami
4

En fait, c'est beaucoup plus simple. Vous n'avez besoin que de deux choses.

Tout d'abord, vous devez trouver quatre distances orthogonales entre le centre du cercle et chaque ligne du rectangle. Ensuite, votre cercle ne coupera pas le rectangle si trois d'entre eux sont plus grands que le rayon du cercle.

Deuxièmement, vous devez trouver la distance entre le centre du cercle et le centre du rectangle, puis votre cercle ne sera pas à l'intérieur du rectangle si la distance est supérieure à la moitié de la longueur diagonale du rectangle.

Bonne chance!


la source
3

Voici mon code C pour résoudre une collision entre une sphère et une boîte non alignée sur l'axe. Il repose sur quelques-unes de mes propres routines de bibliothèque, mais cela peut s'avérer utile pour certains. Je l'utilise dans un jeu et cela fonctionne parfaitement.

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
la source
2

Pour visualiser, prenez le pavé numérique de votre clavier. Si la touche «5» représente votre rectangle, alors toutes les touches 1 à 9 représentent les 9 quadrants de l'espace divisés par les lignes qui composent votre rectangle (5 étant l'intérieur.)

1) Si le centre du cercle est dans le quadrant 5 (c'est-à-dire à l'intérieur du rectangle), les deux formes se croisent.

Avec cela à l'écart, il y a deux cas possibles: a) Le cercle croise deux ou plusieurs arêtes voisines du rectangle. b) Le cercle coupe un bord du rectangle.

Le premier cas est simple. Si le cercle coupe deux arêtes voisines du rectangle, il doit contenir le coin reliant ces deux arêtes. (Cela, ou son centre se trouve dans le quadrant 5, que nous avons déjà couvert. Notez également que le cas où le cercle coupe avec seulement deux opposés bords du rectangle est également couvert.)

2) Si l'un des coins A, B, C, D du rectangle se trouve à l'intérieur du cercle, les deux formes se croisent.

Le deuxième cas est plus délicat. Nous devons noter que cela ne peut se produire que lorsque le centre du cercle se trouve dans l'un des quadrants 2, 4, 6 ou 8. (En fait, si le centre est sur l'un des quadrants 1, 3, 7, 8, le le coin correspondant en sera le point le plus proche.)

Nous avons maintenant le cas où le centre du cercle est dans l'un des quadrants «arête», et il ne croise que l'arête correspondante. Ensuite, le point du bord le plus proche du centre du cercle doit se trouver à l'intérieur du cercle.

3) Pour chaque ligne AB, BC, CD, DA, construisez des droites perpendiculaires p (AB, P), p (BC, P), p (CD, P), p (DA, P) passant par le centre du cercle P. Pour chaque ligne perpendiculaire, si l'intersection avec l'arête d'origine se trouve à l'intérieur du cercle, les deux formes se croisent.

Il existe un raccourci pour cette dernière étape. Si le centre du cercle est dans le quadrant 8 et que l'arête AB est l'arête supérieure, le point d'intersection aura la coordonnée y de A et B, et la coordonnée x du centre P.

Vous pouvez construire les quatre intersections de lignes et vérifier si elles se trouvent sur leurs arêtes correspondantes, ou trouver dans quel quadrant P se trouve et vérifier l'intersection correspondante. Les deux devraient se simplifier à la même équation booléenne. Méfiez-vous du fait que l'étape 2 ci-dessus n'exclut pas que P se trouve dans l'un des quadrants de «coin»; il a juste cherché une intersection.

Edit: En fin de compte, j'ai négligé le simple fait que le n ° 2 est un sous-cas du n ° 3 ci-dessus. Après tout, les coins sont aussi des points sur les bords. Voir la réponse de @ ShreevatsaR ci-dessous pour une excellente explication. Et en attendant, oubliez le n ° 2 ci-dessus, sauf si vous voulez une vérification rapide mais redondante.

aib
la source
2

Cette fonction détecte les collisions (intersections) entre Circle et Rectangle. Il fonctionne comme la méthode e.James dans sa réponse, mais celle-ci détecte les collisions pour tous les angles du rectangle (pas seulement le coin droit).

REMARQUE:

aRect.origin.x et aRect.origin.y sont les coordonnées de l'angle inférieur gauche du rectangle!

aCircle.x et aCircle.y sont les coordonnées de 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
la source
1

J'ai une méthode qui évite le pythagore coûteux si ce n'est pas nécessaire - c'est à dire. lorsque les boîtes englobantes du rectangle et du cercle ne se croisent pas.

Et cela fonctionnera aussi pour les non-euclidiens:

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 peuvent être remplacés par minY, maxY et pareil pour minLon, maxLon: remplacez-le par minX, maxX
  • normDist est une méthode un peu plus rapide que le calcul de la distance totale. Par exemple , sans la racine carrée dans l' espace euclidien (ou sans beaucoup d'autres choses pour Haversine): dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Bien sûr, si vous utilisez cette méthode normDist, vous devrez créer un normedDist = dist*dist;pour le cercle

Voir le code complet BBox et Circle de mon projet GraphHopper .

Karussell
la source
1

J'ai créé une classe pour travailler avec des formes j'espère que vous apprécierez

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
la source
1

Voici le code modifié fonctionnant à 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
la source
1

Voici un test rapide en une ligne pour cela:

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

Il s'agit du cas aligné sur l'axe où se rect_halvestrouve un vecteur positif pointant du milieu du rectangle vers un coin. L'expression à l'intérieur length()est un vecteur delta allant centerdu point le plus proche du rectangle. Cela fonctionne dans toutes les dimensions.

Tyler
la source
1
  • Vérifiez d'abord si le rectangle et le carré tangent au cercle se chevauchent (facile). S'ils ne se chevauchent pas, ils n'entrent pas en collision.
  • Vérifiez si le centre du cercle est à l'intérieur du rectangle (facile). Si c'est à l'intérieur, ils entrent en collision.
  • Calculez la distance quadratique minimale entre les côtés du rectangle et le centre du cercle (peu difficile). S'il est inférieur au rayon carré, alors ils entrent en collision, sinon ils ne le font pas.

C'est efficace, car:

  • Tout d'abord, il vérifie le scénario le plus courant avec un algorithme bon marché et lorsqu'il est sûr qu'ils ne se heurtent pas, il se termine.
  • Ensuite, il vérifie le scénario suivant le plus courant avec un algorithme bon marché (ne calculez pas la racine carrée, utilisez les valeurs au carré) et lorsqu'il est sûr qu'ils entrent en collision, il se termine.
  • Ensuite, il exécute l'algorithme le plus coûteux pour vérifier la collision avec les bordures du rectangle.
David C.
la source
1

a fonctionné pour moi (ne fonctionne que lorsque l'angle du rectangle est de 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
la source
hmmm ... J'ai voté pour cela mais ensuite testé correctement et je pense que cela ne fonctionne pas sur les coins par exemple. Cela fonctionnerait pour deux rectangles.
Dan Zen
1

Améliorer un peu la réponse de e.James :

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

Cela soustrait rect.w / 2et rect.h / 2une fois au lieu de jusqu'à trois fois.

Estid Felipe Lozano Reyes
la source
Je soupçonne fortement que la plupart des compilateurs modernes optimiseraient (ou du moins pourraient) automatiquement optimiser les calculs redondants pour vous.
martineau le
0

Pour ceux qui doivent calculer la collision Cercle / Rectangle dans les coordonnées géographiques avec SQL, voici
mon implémentation dans l'oracle 11 de l' algorithme suggéré par e.James .

En entrée, il nécessite les coordonnées du cercle, le rayon du cercle en km et les coordonnées de deux sommets du rectangle:

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
la source
0

Works, je viens de comprendre cela il y a une semaine, et je viens de le tester.

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)));
user3026859
la source
Cela pourrait fonctionner pour Circle-Square, mais la question concerne 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
la source
-2

En supposant que vous ayez les quatre bords du rectangle, vérifiez la distance entre les bords et le centre du cercle, si elle est inférieure au rayon, les formes se croisent.

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
Pour votre propre bien
la source
Qu'en est-il du cas où un petit cercle est entièrement entouré d'un grand rectangle? C'est sûrement une intersection, et échouerait le test dans cette réponse.
Ken Paul
Ah oui, je n'y ai pas pensé. Vous pouvez simplement ajouter plus de vérifications comme si sqrt ((rectangleRight.x / 2 - circleCenter.x) ^ 2 + (rectangleBottom.y / 2 - circleCenter.y) ^ 2) <radius alors ils se croisent Ce sera long et lent, mais du haut de ma tête c'est le mieux que je puisse trouver.
ForYourOwnGood
Ils peuvent se croiser sur n'importe quel [un seul] point sur n'importe laquelle des arêtes. Vous devriez également trouver les distances centre-bord. (Oh, et appelez vos coins "coins" :)
aib
Cela semble détecter uniquement lorsqu'un coin est à l'intérieur du cercle.
Stark
-2

Si le rectangle croise le cercle, un ou plusieurs points d'angle du rectangle doivent être à l'intérieur du cercle. Supposons que les quatre points d'un rectangle soient A, B, C, D. au moins l'un d'entre eux doit couper le cercle. donc si la distance entre un point et le centre du cercle est inférieure au rayon du cercle, elle doit couper le cercle. Pour obtenir la distance, vous pouvez utiliser le théorème de Pythagore,

H^2 = A^2 + B^2

Cette technique a quelques limites. Mais cela fonctionnera mieux pour les développeurs de jeux. en particulier la détection de collision

C'est une bonne mise à jour de l'algorithme d'Arvo

Md. Ashraful Islam
la source
Cette réponse est incroyablement fausse chaque fois que le rectangle a un côté plus grand que le rayon du cercle.
Paul K