Détection de collision cercle-rectangle (intersection)
https://stackoverflow.com/questions/401847
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment savoir si un cercle et un rectangle se coupent dans un espace euclidien 2D? (c'est-à-dire géométrie 2D classique)
La solution
Il n'y a que deux cas où le cercle coupe le rectangle:
- Le centre du cercle se trouve à l'intérieur du rectangle ou
- Un des bords du rectangle a un point dans le cercle.
Notez que cela n’exige pas que le rectangle soit parallèle à l’axe.
(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 "en dehors du cercle"), la seule façon pour le cercle de croiser le polygone est de le faire si se trouve complètement à l'intérieur du polygone.)
Avec cet aperçu, le fonctionnement suivant fonctionnera comme ci-dessous, où le cercle a le centre P et le rayon R , et le rectangle a les sommets A , B , C , D dans cet ordre (code pas 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 implémenté de plusieurs manières; l’une des méthodes générales point in polygone fonctionnera, mais pour un rectangle, vous pouvez simplement vérifier si cela travaux:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
Et intersectCircle () est facile à implémenter aussi: un moyen serait de vérifier si le pied de la perpendiculaire de P à la ligne est suffisamment proche et entre points de terminaison et vérifiez les points de terminaison sinon.
Ce qui est bien, c’est que la même idée ne fonctionne pas seulement pour les rectangles, mais aussi pour l’intersection d’un cercle avec un polygone simple & # 8212; ne doit même pas être convexe!
Autres conseils
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:
-
La première paire de lignes calcule les valeurs absolues des différences x et y entre le centre du cercle et le centre du rectangle. Cela réduit les quatre quadrants en un, 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 située exactement à un rayon des bords du rectangle. Le centre du cercle doit se situer dans cette bordure rouge pour que l'intersection se produise.
-
La deuxième paire de lignes élimine les cas faciles où le cercle est suffisamment éloigné du rectangle (dans un sens ou dans l'autre) pour qu'aucune intersection ne soit possible. Cela correspond à la zone verte de l'image.
-
La troisième paire de lignes gère les cas faciles où le cercle est suffisamment proche du rectangle (dans un sens ou dans l'autre) pour garantir une intersection. 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.
-
Les lignes restantes calculent le cas difficile où le cercle peut croiser le coin du rectangle. Pour résoudre le problème, 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 false pour tous les cercles dont le centre est dans la zone ombrée de rouge et vrai pour tous les cercles dont le centre se trouve à l'intérieur de la zone ombrée de blanc.
Voici une autre solution assez simple à mettre en œuvre (et assez rapide aussi). Toutes les intersections seront capturées, y compris lorsque la sphère sera 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);
Toute bibliothèque mathématique décente peut être réduite à 3 ou 4 lignes.
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 inférieure au rayon de votre sphère ([ distance ponctuelle ])
OU
le centre du cercle est à l'intérieur du rect
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] (two points of your line, ie the vertex points) P1 = [px,py] some point Distance d = abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)
centre du cercle à l'intérieur du rect:
Prenons un axe approximatif: s’il existe une projection sur une droite qui sépare le rectangle du point, ils ne se coupent pas
vous projetez le point sur des lignes parallèles aux côtés de votre rect et pouvez ensuite facilement déterminer s’ils se croisent. si elles ne se croisent pas sur les quatre projections, elles (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:
//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI
seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }: // the edges
D = edge[0] - edge[1]
innerProd = D * POI
Interval_min = min(D*edge[0],D*edge[1])
Interval_max = max(D*edge[0],D*edge[1])
if not ( Interval_min ≤ innerProd ≤ Interval_max )
seperated = true
break // end for loop
end if
end for
if (seperated is true)
return "no intersection"
else
return "intersection"
end if
cela ne suppose pas un rectangle aligné sur l'axe et est facilement extensible pour tester les intersections entre des ensembles convexes.
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 quadrature est également effectuée "manuellement". enregistrer des cycles d'horloge.
Voici mon code C pour résoudre une collision entre une sphère et une boîte non alignée. Cela repose sur quelques-unes de mes propres routines de bibliothèque, mais il 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;
}
En fait, c'est beaucoup plus simple. Vous n'avez besoin que de deux choses.
Tout d'abord, vous devez rechercher quatre distances orthogonales entre le centre du cercle et chaque ligne du rectangle. Ensuite, votre cercle ne coupe 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. Votre cercle ne sera donc pas à l'intérieur du rectangle si la distance est supérieure à la moitié de la longueur de la diagonale du rectangle.
Bonne chance!
La solution la plus simple que j'ai proposé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, l’axe des x pointant vers le bas.
Si vous voulez une solution au traitement des collisions entre un cercle en mouvement et un rectangle, c'est beaucoup plus compliqué et couvert dans une autre de mes réponses.
Pour visualiser, prenez le pavé numérique de votre clavier. Si la touche «5» représente votre rectangle, toutes les touches 1 à 9 représentent les 9 quadrants d’espace divisés par les lignes qui composent votre rectangle (5 étant l’intérieur.)
1) Si le centre du cercle se trouve dans le quadrant 5 (c'est-à-dire à l'intérieur du rectangle), les deux formes se coupent.
Cela étant dit, il y a deux cas possibles: a) Le cercle coupe 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 bords voisins du rectangle, il doit contenir le coin reliant ces deux bords. (Cela, ou son centre se situe dans le quadrant 5, que nous avons déjà couvert. Notez également que le cas où le cercle ne coupe que deux arêtes opposées du rectangle est également traité.)
2) Si l'un des coins A, B, C, D du rectangle se trouve à l'intérieur du cercle, les deux formes se coupent.
Le deuxième cas est plus délicat. Nous devrions noter que cela ne peut se produire que lorsque le centre du cercle est situé dans l’un des quadrants 2, 4, 6 ou 8. (En fait, si le centre se trouve 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 se trouve dans l'un des quadrants du "bord" et qu'il ne croise que le bord correspondant. 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 les droites perpendiculaires p (AB, P), p (BC, P), p (CD, P), p (DA, P) en passant par le centre du cercle. P. Pour chaque droite perpendiculaire, si l’intersection avec le bord original se trouve à l’intérieur du cercle, les deux formes se coupent.
Il existe un raccourci pour cette dernière étape. Si le centre du cercle est dans le quadrant 8 et que le bord AB est le bord supérieur, 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 intersections à quatre lignes et vérifier si elles se trouvent sur leurs arêtes correspondantes, ou trouver le quadrant P qui est à l'intérieur et vérifier l'intersection correspondante. Les deux devraient simplifier à la même équation booléenne. Méfiez-vous de ce que l'étape 2 ci-dessus n'exclut pas que P soit dans l'un des quadrants de «coin»; il a juste cherché une intersection.
Modifier: En fait, j’ai négligé le simple fait que le n ° 2 est un sous-dossier 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 bonne explication. Et en attendant, oubliez le point 2 ci-dessus à moins que vous ne souhaitiez un contrôle rapide mais redondant.
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 tout en haut).
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;
}
J'ai créé un cours 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;
}
}
Voici le code modifié à 100% qui fonctionne:
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
Voici un test rapide sur une ligne pour ceci:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
Il s'agit du cas aligné sur l'axe où rect_halves est un vecteur positif pointant du centre du rectangle à un coin. L'expression à l'intérieur de length () est un vecteur delta de centre au point le plus proche du rectangle. Cela fonctionne dans n'importe quelle dimension.
- Commencez par vérifier si le rectangle et le carré tangent au cercle se chevauchent (facile). S'ils ne se chevauchent pas, ils ne se heurtent pas.
- 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 minimale au carré entre les côtés du rectangle et le centre du cercle (peu dure). Si elle est inférieure au rayon carré, elles entrent en collision, sinon elles ne le font pas.
C’est efficace, car:
- Il vérifie d’abord le scénario le plus courant avec un algorithme bon marché et s’il est certain qu’ils ne se heurtent pas, il se termine.
- Ensuite, il vérifie le scénario suivant avec un algorithme peu coûteux (ne calculez pas la racine carrée, utilisez les valeurs au carré) et s’il est sûr qu’elles entrent en collision, il se termine.
- Ensuite, il exécute l'algorithme plus coûteux pour vérifier la collision avec les bordures du rectangle.
J'ai une méthode qui évite les coûteuses pythagore si pas nécessaire - c'est-à-dire. lorsque les limites du rectangle et du cercle ne se croisent pas.
Et ça va marcher pour les non-euclidiens aussi:
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 peut être remplacé par minY, maxY et identique 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 unnormedDist = dist * dist;pour le cercle
Voir le texte intégral BBox et Cercle code de mon projet GraphHopper .
Pour ceux qui doivent calculer la collision cercle / rectangle en coordonnées géographiques avec SQL,
C’est mon implémentation dans oracle 11 de algorithme suggéré par e.James .
En entrée, les coordonnées du cercle, le rayon du cercle en km et les coordonnées de deux sommets du rectangle sont obligatoires:
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;
Ça marche, je viens de le découvrir il y a une semaine et je viens tout juste 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)));
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
En supposant que vous ayez les quatre arêtes du rectangle, vérifiez la distance entre les arêtes et le centre du cercle; si son rayon est inférieur 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
Si le rectangle se croise avec le cercle, un ou plusieurs angles du rectangle doivent se trouver à l'intérieur du cercle. Supposons que les quatre points d'un rectangle sont A, B, C, D. au moins l'un d'entre eux devrait couper le cercle. Par conséquent, si la distance entre un point et le centre du cercle est inférieure au rayon du cercle, il devrait croiser 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
