Detección de colisión círculo-rectángulo (intersección)
https://stackoverflow.com/questions/401847
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo puedo saber si un círculo y un rectángulo se intersecan en el espacio euclidiano 2D? (es decir, geometría 2D clásica)
Solución
Solo hay dos casos cuando el círculo se interseca con el rectángulo:
- El centro del círculo se encuentra dentro del rectángulo, o
- Uno de los bordes del rectángulo tiene un punto en el círculo.
Tenga en cuenta que esto no requiere que el rectángulo sea paralelo al eje.
(Una forma de ver esto: si ninguno de los bordes tiene un punto en el círculo (si todos los bordes están completamente fuera del círculo), la única manera en que el círculo todavía puede intersecar es el polígono si se encuentra completamente dentro del polígono.)
Con esa información, funcionará algo como lo siguiente, donde el círculo tiene el centro P y el radio R , y el rectángulo tiene vértices A , B , C , D en ese orden (no es el código completo):
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 está escribiendo cualquier geometría, probablemente ya tenga las funciones anteriores en su biblioteca. De lo contrario, pointInRectangle () se puede implementar de varias maneras; cualquiera de los métodos generales del punto en el polígono funcionará, pero para un rectángulo solo puede verificar si esto trabajos:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
Y intersectCircle () también es fácil de implementar: una forma sería verificar si el pie del perpendicular de P a la línea está lo suficientemente cerca y entre el puntos finales, y verifique los puntos finales de otra manera.
Lo bueno es que la idea misma no solo funciona para rectángulos, sino para la intersección de un círculo con cualquier polígono simple - ¡ni siquiera tiene que ser convexo!
Otros consejos
Así es como lo haría:
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));
}
Así es como funciona:
-
El primer par de líneas calcula los valores absolutos de la diferencia x e y entre el centro del círculo y el centro del rectángulo. Esto colapsa los cuatro cuadrantes en uno, de modo que los cálculos no tienen que hacerse cuatro veces. La imagen muestra el área en la que ahora debe estar el centro del círculo. Tenga en cuenta que solo se muestra el cuadrante único. El rectángulo es el área gris, y el borde rojo esboza el área crítica que está exactamente a un radio de los bordes del rectángulo. El centro del círculo debe estar dentro de este borde rojo para que se produzca la intersección.
-
El segundo par de líneas elimina los casos fáciles donde el círculo está lo suficientemente alejado del rectángulo (en cualquier dirección) para que no sea posible una intersección. Esto corresponde al área verde en la imagen.
-
El tercer par de líneas maneja los casos fáciles donde el círculo está lo suficientemente cerca del rectángulo (en cualquier dirección) para garantizar una intersección. Esto corresponde a las secciones naranja y gris de la imagen. Tenga en cuenta que este paso debe realizarse después del paso 2 para que la lógica tenga sentido.
-
Las líneas restantes calculan el caso difícil en el que el círculo puede cruzar la esquina del rectángulo. Para resolver, calcula la distancia desde el centro del círculo y la esquina, y luego verifica que la distancia no sea mayor que el radio del círculo. Este cálculo devuelve falso para todos los círculos cuyo centro está dentro del área sombreada en rojo y devuelve verdadero para todos los círculos cuyo centro está dentro del área sombreada en blanco.
Aquí hay otra solución que es bastante simple de implementar (y también bastante rápida). Atrapará todas las intersecciones, incluso cuando la esfera haya ingresado por completo en el rectángulo.
// 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);
Con cualquier biblioteca matemática decente, se puede reducir a 3 o 4 líneas.
tu esfera y rect se intersecan IIF
la distancia entre el centro del círculo y un vértice de tu rect es menor que el radio de tu esfera
O
la distancia entre el centro del círculo y un borde de su rect es menor que el radio de su esfera ([ distancia punto-línea ])
O
el centro del circulo esta dentro del rect
distancia punto-punto:
P1 = [x1,y1] P2 = [x2,y2] Distance = sqrt(abs(x1 - x2)+abs(y1-y2))
distancia punto-línea:
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)
círculo centro interior rect:
tomar un enfoque de eje separado: si existe una proyección en una línea que separa el rectángulo del punto, no se intersecan
proyecta el punto en líneas paralelas a los lados de su rect y luego puede determinar fácilmente si se intersecan. si no se intersectan en las 4 proyecciones, ellos (el punto y el rectángulo) no pueden intersecar.
solo necesitas el producto interno (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)
tu prueba se vería así:
//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
esto no supone un rectángulo alineado con el eje y es fácilmente extensible para probar intersecciones entre conjuntos convexos.
Esta es la solución más rápida:
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;
}
Tenga en cuenta el orden de ejecución, y la mitad del ancho / alto se calcula previamente. También la cuadratura se realiza " manualmente " para guardar algunos ciclos de reloj.
Aquí está mi código C para resolver una colisión entre una esfera y una caja no alineada con el eje. Se basa en un par de mis propias rutinas de biblioteca, pero puede ser útil para algunos. Lo estoy usando en un juego y funciona perfectamente.
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 realidad, esto es mucho más simple. Sólo necesitas dos cosas.
Primero, debes encontrar cuatro distancias ortogonales desde el centro del círculo hasta cada línea del rectángulo. Entonces su círculo no entrecruzará el rectángulo si alguno de ellos es mayor que el radio del círculo.
Segundo, necesitas encontrar la distancia entre el centro del círculo y el centro del rectángulo, entonces el círculo no estará dentro del rectángulo si la distancia es mayor que la mitad de la longitud diagonal del rectángulo.
¡Buena suerte!
La solución más simple que he encontrado es bastante sencilla.
Funciona encontrando el punto en el rectángulo más cercano al círculo y luego comparando la distancia.
Puedes hacer todo esto con unas pocas operaciones, e incluso evitar la función 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;
}
Y eso es todo! La solución anterior asume un origen en la parte superior izquierda del mundo con el eje x apuntando hacia abajo.
Si desea una solución para manejar las colisiones entre un círculo y un rectángulo en movimiento, es mucho más complicado y cubierto en otra respuesta mía.
Para visualizar, toma el teclado numérico de tu teclado. Si la tecla '5' representa su rectángulo, entonces todas las teclas 1-9 representan los 9 cuadrantes de espacio divididos por las líneas que forman su rectángulo (siendo 5 el interior).
1) Si el centro del círculo está en el cuadrante 5 (es decir, dentro del rectángulo), las dos formas se intersecan.
Con eso fuera del camino, hay dos casos posibles: a) El círculo se interseca con dos o más bordes adyacentes del rectángulo. b) El círculo se interseca con un borde del rectángulo.
El primer caso es simple. Si el círculo se interseca con dos bordes adyacentes del rectángulo, debe contener la esquina que conecta esos dos bordes. (Eso, o su centro se encuentra en el cuadrante 5, que ya hemos cubierto. También tenga en cuenta que el caso en el que el círculo se interseca con solo dos bordes opuestos del rectángulo también se cubre.)
2) Si alguna de las esquinas A, B, C, D del rectángulo se encuentra dentro del círculo, entonces las dos formas se intersecan.
El segundo caso es más complicado. Debemos tomar nota de que solo puede suceder cuando el centro del círculo se encuentra en uno de los cuadrantes 2, 4, 6 u 8. (De hecho, si el centro está en cualquiera de los cuadrantes 1, 3, 7, 8, la esquina correspondiente será el punto más cercano a él.)
Ahora tenemos el caso de que el centro del círculo está en uno de los cuadrantes de "borde", y solo se interseca con el borde correspondiente. Luego, el punto en el borde que está más cerca del centro del círculo, debe estar dentro del círculo.
3) Para cada línea AB, BC, CD, DA, construya las líneas perpendiculares p (AB, P), p (BC, P), p (CD, P), p (DA, P) a través del centro del círculo P. Para cada línea perpendicular, si la intersección con el borde original se encuentra dentro del círculo, entonces las dos formas se intersectan.
Hay un atajo para este último paso. Si el centro del círculo está en el cuadrante 8 y el borde AB es el borde superior, el punto de intersección tendrá la coordenada y de A y B, y la coordenada x del centro P.
Puede construir las cuatro intersecciones de línea y verificar si están ubicadas en sus bordes correspondientes, o averiguar en qué cuadrante P se encuentra y verificar la intersección correspondiente. Ambos deben simplificar a la misma ecuación booleana. Tenga cuidado de que el paso 2 anterior no excluya que P esté en uno de los cuadrantes de la 'esquina'; Sólo buscó una intersección.
Edit: Resulta que, he pasado por alto el simple hecho de que el # 2 es un subcaso del # 3 anterior. Después de todo, las esquinas también son puntos en los bordes. Vea la respuesta de @ ShreevatsaR a continuación para una gran explicación. Y mientras tanto, olvídate del número 2 anterior, a menos que quieras un control rápido pero redundante.
Esta función detecta colisiones (intersecciones) entre Círculo y Rectángulo. Trabaja como el método e.James en su respuesta, pero este detecta colisiones para todos los ángulos del rectángulo (no solo en la esquina derecha).
NOTA:
aRect.origin.x y aRect.origin.y son coordenadas del ángulo inferior izquierdo del rectángulo.
aCircle.x y aCircle.y son coordenadas 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;
}
He creado la clase para trabajar con formas espero que disfrutes
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;
}
}
Aquí está el código modificado 100% funcionando:
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
Aquí hay una prueba rápida de una línea para esto:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
Este es el caso de eje alineado donde rect_halves es un vector positivo que apunta desde el centro del rectángulo hasta una esquina. La expresión dentro de length () es un vector delta desde center a un punto más cercano en el rectángulo. Esto funciona en cualquier dimensión.
- Primero, compruebe si el rectángulo y el cuadrado tangente al círculo se superponen (fácil). Si no se superponen, no chocan.
- Verifique si el centro del círculo está dentro del rectángulo (fácil). Si está dentro, chocan.
- Calcule la distancia cuadrada mínima desde los lados del rectángulo hasta el centro del círculo (poco difícil). Si es más bajo que el radio al cuadrado, entonces chocan, de lo contrario no lo hacen.
Es eficiente, porque:
- Primero comprueba el escenario más común con un algoritmo barato y cuando está seguro de que no chocan, termina.
- Luego comprueba el siguiente escenario más común con un algoritmo barato (no calcule la raíz cuadrada, use los valores cuadrados) y cuando esté seguro de que colisionen, se terminará.
- Luego ejecuta el algoritmo más costoso para verificar la colisión con los bordes del rectángulo.
Tengo un método que evita las costosas pitagoras si no es necesario, es decir. cuando los recuadros delimitadores del rectángulo y el círculo no se intersecan.
Y también funcionará para no euclidianos:
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 se puede reemplazar con minY, maxY y lo mismo para minLon, maxLon: reemplazarlo con minX, maxX
- normDist es un método un poco más rápido que el cálculo de la distancia total. P.ej. sin la raíz cuadrada en el espacio euclidiano (o sin muchas otras cosas para haversine):
dLat = (lat-circleY); dLon = (lon-circleX); normed = dLat * dLat + dLon * dLon. Por supuesto, si utiliza ese método normDist, deberá crear unnormedDist = dist * dist;para el círculo
Consulte el BBox y Círculo código de mi GraphHopper .
Para aquellos que tienen que calcular la colisión Círculo / Rectángulo en Coordenadas Geográficas con SQL,
esta es mi implementación en Oracle 11 de algoritmo sugerido por e.James .
En la entrada requiere coordenadas de círculo, radio de círculo en km y dos coordenadas de vértices del rectángulo:
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;
Funciona, solo resolví esto hace una semana, y ahora tengo que probarlo.
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
Suponiendo que tenga los cuatro bordes del rectángulo, compruebe la distancia desde los bordes hasta el centro del círculo, si es menor que el radio, entonces las formas se intersecan.
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 el rectángulo se interseca con el círculo, uno o más puntos de esquina del rectángulo deben estar dentro del círculo. Supongamos que los cuatro puntos de un rectángulo son A, B, C, D. al menos uno de ellos debe cruzar el círculo. por lo tanto, si la distancia desde un punto hasta el centro del círculo es menor que el radio del círculo, debe intersecar el círculo. Para obtener la distancia, puede utilizar el teorema de Pitágoras,
H^2 = A^2 + B^2
Esta técnica tiene algunos límites. Pero funcionará mejor para los desarrolladores de juegos. especialmente la detección de colisiones
Es una buena actualización para el algoritmo de Arvo
