geometry - rectangulos - Detección de colisiones rectangulares en círculo(intersección)
funcion de colision en java (19)
Aquí está el código modificado funcionando al 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
¿Cómo puedo saber si un círculo y un rectángulo se cruzan en el espacio Euclidiano 2D? (es decir, geometría 2D clásica)
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;
}
Aquí hay otra solución que es bastante simple de implementar (y bastante rápido, también). Atrapará todas las intersecciones, incluso cuando la esfera haya entrado completamente 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 de matemáticas decente, puede acortarse a 3 o 4 líneas.
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 alineado con el eje donde rect_halves es un vector positivo que apunta desde el rectángulo medio a una esquina. La expresión dentro de length() es un vector delta desde el center hasta un punto más cercano en el rectángulo. Esto funciona en cualquier dimensión.
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 xey entre el centro del círculo y el centro del rectángulo. Esto colapsará 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 individual. El rectángulo es el área gris, y el borde rojo delinea 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 lejos del rectángulo (en cualquier dirección) que no es posible la 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) que se garantiza una intersección. Esto corresponde a las secciones naranja y gris en 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 donde el círculo puede intersecarse con la esquina del rectángulo. Para resolver, calcule la distancia desde el centro del círculo y la esquina, y luego verifique que la distancia no sea mayor que el radio del círculo. Este cálculo devuelve falso para todos los círculos cuyo centro se encuentre dentro del área sombreada roja y devuelve verdadero para todos los círculos cuyo centro se encuentre dentro del área sombreada en blanco.
Creé clase para el trabajo 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;
}
}
En realidad, esto es mucho más simple. Solo necesitas dos cosas.
Primero, necesita encontrar cuatro distancias ortogonales desde el centro del círculo hasta cada línea del rectángulo. Entonces su círculo no intersectará el rectángulo si tres de ellos son más grandes que el radio del círculo.
En segundo lugar, debe encontrar la distancia entre el centro del círculo y el centro del rectángulo, luego su 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!
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 de la anchura / altura está precalculada. También la cuadratura se hace "manualmente" para guardar algunos ciclos de reloj.
Esta función detecta colisiones (intersecciones) entre Círculo y Rectángulo. Él trabaja como el método e.James en su respuesta, pero este detecta colisiones para todos los ángulos de rectángulo (no solo en la esquina superior 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 del 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;
}
Funciona, acaba de descubrir 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)));
La solución más simple que he encontrado es bastante sencilla.
Funciona al encontrar el punto en el rectángulo más cercano al círculo, luego comparando la distancia.
Puede 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! La solución anterior asume un origen en la parte superior izquierda del mundo con el eje x apuntando hacia abajo.
Si quieres una solución para manejar las colisiones entre un círculo móvil y un rectángulo, es mucho más complicado y está cubierto por otra respuesta mía.
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 el oráculo 11 del algoritmo sugerido por James .
En la entrada, requiere coordenadas de círculo, radio de círculo en km y dos vértices en las coordenadas 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;
Para visualizar, toma el teclado numérico de tu teclado. Si la clave ''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), entonces las dos formas se cruzan.
Con eso fuera del camino, hay dos posibles casos: a) El círculo se cruza con dos o más bordes vecinos del rectángulo. b) El círculo se cruza con un borde del rectángulo.
El primer caso es simple. Si el círculo se cruza con dos bordes vecinos 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 donde el círculo se cruza con solo dos bordes opuestos del rectángulo está cubierto también).
2) Si cualquiera de las esquinas A, B, C, D del rectángulo se encuentra dentro del círculo, entonces las dos formas se cruzan.
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, el la esquina correspondiente será el punto más cercano a ella).
Ahora tenemos el caso de que el centro del círculo está en uno de los cuadrantes ''del borde'', y solo se cruza con el borde correspondiente. Entonces, 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, construye 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 cruzan.
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íneas y verificar si se encuentran en sus bordes correspondientes, o descubrir en qué cuadrante P se encuentra y verificar la intersección correspondiente. Ambos deberían simplificarse a la misma ecuación booleana. Tenga cuidado de que el paso 2 anterior no descarta que P esté en uno de los cuadrantes de "esquina"; solo buscó una intersección.
Editar: Como resultado, he pasado por alto el hecho simple de que el n. ° 2 es un subcampo del n. ° 3 anterior. Después de todo, las esquinas también son puntos en los bordes. Ver la respuesta de @ ShreevatsaR a continuación para una gran explicación. Y mientras tanto, olvídate del # 2 anterior a menos que quieras un control rápido pero redundante.
Solo hay dos casos cuando el círculo se cruza con el rectángulo:
- O bien 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), entonces la única forma en que el círculo puede cruzarse con el polígono es si se encuentra completamente dentro del círculo. polígono.)
Con esa idea, algo como lo siguiente funcionará, donde el círculo tiene el centro P y el radio R , y el rectángulo tiene los vértices A , B , C , D en ese orden (no 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 puntos generales en los métodos de polígonos funcionará, pero para un rectángulo puede simplemente verificar si esto funciona:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
Y intersectCircle() es fácil de implementar: una forma sería verificar si el pie de la perpendicular de P a la línea está lo suficientemente cerca y entre los puntos finales, y verificar los puntos finales en caso contrario.
Lo bueno es que la misma idea funciona no solo para los rectángulos sino también para la intersección de un círculo con cualquier polígono simple , ¡ni siquiera tiene que ser convexo!
Suponiendo que tiene 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 intersectan.
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
Tengo un método que evita los costosos Pitágoras si no es necesario, es decir. cuando los cuadros de límite del rectángulo y el círculo no se cruzan.
Y funcionará también para los 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 pueden reemplazar con minY, maxY e igual para minLon, maxLon: reemplázalo con minX, maxX
- normDist es un método un poco más rápido que el cálculo completo de distancia. Por ejemplo, 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*dLondLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLondLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Por supuesto, si usa el método normDist, deberá crear unnormedDist = dist*dist;para el círculo
Ver el código completo de BBox y Circle de mi proyecto GraphHopper .
tu esfera y tu intersección 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 tu rect es menor que el radio de tu esfera ([ distancia de la línea de puntos ])
O
el centro del círculo está dentro del rect
distancia del punto-punto:
P1 = [x1,y1] P2 = [x2,y2] Distance = sqrt(abs(x1 - x2)+abs(y1-y2))
distancia entre puntos:
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)
centro del círculo dentro de rect:
tomar un enfoque de eje separador: si existe una proyección en una línea que separa el rectángulo del punto, no se cruzan
proyecta el punto en líneas paralelas a los lados de su rect y luego puede determinar fácilmente si se cruzan. si no se cruzan en las 4 proyecciones, ellos (el punto y el rectángulo) no se pueden cruzar.
solo necesitas el producto interno (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)
su 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 al eje y es fácilmente extensible para probar intersecciones entre conjuntos convexos.
If the rectangle intersects to the circle, one or more corner points of the rectangle should be inside in the circle. Suppose a rectangle''s four points are A,B,C,D. at least one of them should intersect the circle. so if the distance from one point to the center of the circle is less than the radius of the circle it should intersect the circle. To get the distance you can use the Pythagorean theorem,
H^2 = A^2 + B^2
This technique has some limits. But it will work better for the game developers. especially collision detection
It is a good update to Arvo''s Algorithm
- Primero compruebe si el rectángulo y la tangente cuadrada al círculo se superponen (fácil). Si no se superponen, no colisionan.
- Verifica si el centro del círculo está dentro del rectángulo (fácil). Si está adentro, colisionan.
- Calcula la distancia cuadrada mínima desde los lados del rectángulo hasta el centro del círculo (poco duro). Si es menor que el radio al cuadrado, chocan, de lo contrario no lo hacen.
Es eficiente, porque:
- Primero, verifica el escenario más común con un algoritmo barato y cuando está seguro de que no colisionan, termina.
- Luego, verifica el siguiente escenario más común con un algoritmo barato (no calcule la raíz cuadrada, use los valores al cuadrado) y cuando esté seguro de que colisiona, termina.
- Luego ejecuta el algoritmo más caro para verificar la colisión con los bordes del rectángulo.