Círculo-Quadrado de detecção de colisão (intersecção)
https://stackoverflow.com/questions/401847
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como posso dizer se um círculo e um retângulo se cruzam no espaço 2D Euclidiano? (Isto é clássico geometria 2D)
Solução
Existem apenas dois casos em que os cruza círculo com o retângulo:
- De qualquer mentiras centro do círculo dentro do retângulo, ou
- Uma das extremidades do rectângulo tem um ponto no círculo.
Note que este não exige que o retângulo para ser paralelo ao eixo.
(Uma forma de ver isto: se nenhuma das bordas tem um ponto no círculo (se todas as arestas são completamente "fora" do círculo), então a única maneira que o círculo pode ainda cruzam o polígono é se ele mentiras completamente dentro do polígono.)
Com essa visão, algo como o seguinte irá funcionar, onde o círculo tem P centro e R raio, eo retângulo tem vértices A, B, C, D nessa ordem (código não completa):
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)))
Se você estiver escrevendo qualquer geometria você provavelmente tem as funções acima em sua biblioteca já. Caso contrário, pointInRectangle() pode ser implementado de várias maneiras; qualquer um dos em métodos polígono vai funcionar, mas para um retângulo que você pode apenas verificar se este funciona:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
E intersectCircle() é fácil de implementar também:. Uma forma seria a de verificar se o pé da perpendicular a partir P para a linha está perto o suficiente e entre os pontos finais, e verificar os terminais de outra forma
O legal é que o mesma idéia funciona não apenas para retângulos mas para a intersecção de um círculo com qualquer simples polígono - nem sequer tem que ser convexo
Outras dicas
Aqui está como eu faria isso:
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));
}
Eis como funciona:
-
O primeiro par de linhas de calcular os valores absolutos dos x e y diferença entre o centro do círculo e o centro do rectângulo. Isso recolhe os quatro quadrantes para baixo em um, de modo que os cálculos não tem que ser feito quatro vezes. A imagem mostra a área em que o centro do círculo tem agora de deitar. Note-se que apenas o único quadrante é mostrado. O retângulo é a área cinzenta, e a borda vermelha delineia a área crítica que é exatamente um raio de distância das bordas do retângulo. O centro do círculo tem que ser dentro desta borda vermelha para o cruzamento de ocorrer.
-
O segundo par de linhas de eliminar os casos fáceis onde o círculo é suficientemente longe do rectângulo (em qualquer direcção) que não é possível intersecção. Isto corresponde à área verde na imagem.
-
O terceiro par de linhas de lidar com os casos fáceis onde o círculo está suficientemente perto para o rectângulo (em qualquer direcção) que uma intersecção é garantida. Isto corresponde ao laranja e seções de cinza na imagem. Note-se que este passo deve ser feito após a etapa 2 para a lógica a fazer sentido.
-
As linhas restantes calcular o caso difícil onde o círculo pode intersectar o canto do rectângulo. Para resolver, calcular a distância do centro do círculo e canto, e depois verificar que a distância não é mais do que o raio do círculo. Esta falsa cálculo retorna para todos os círculos cujo centro está dentro da área sombreada vermelho e retorna verdadeiro para todos os círculos cujo centro está dentro da área sombreada branco.
Aqui é outra solução que é muito simples de implementar (e muito rápido, também). Ele vai pegar todos os cruzamentos, incluindo quando a esfera tenha entrado plenamente o retâ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);
Com qualquer biblioteca de matemática decente, que pode ser reduzido para 3 ou 4 linhas.
sua esfera e rect cruzam IIF
a distância entre círculo-centro e um vértice do seu rect é menor do que o raio da sua esfera
OR
a distância entre o centro do círculo-e a uma borda da sua rect é menor do que o raio da sua esfera ([ ponto-line distância])
OR
o centro do círculo está dentro da rect
ponto a ponto a distância:
P1 = [x1,y1] P2 = [x2,y2] Distance = sqrt(abs(x1 - x2)+abs(y1-y2))
-line ponto de distância:
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 do círculo
dentro rect:
tomar uma aproach eixo separando: se existe uma projecção para uma linha que separa o rectângulo do ponto, eles não se cruzam
você projeta o ponto em linhas paralelas aos lados de seu rect e pode facilmente determinar se eles se cruzam. se eles não se cruzam em todos os 4 projeções, eles (o ponto eo retângulo) não pode se cruzam.
você só precisa do produto interno (x = [x1, x2], = y [y1, y2], x * y = x1 * y1 + x2 * y2)
o teste ficaria assim:
//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
este não assume um retângulo alinhado ao eixo e é facilmente extensível para testar interseções entre conjuntos convexos.
Esta é a solução mais 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;
}
Observe a ordem de execução, e a metade da largura / altura é pré-calculado. Também a quadratura é feita "manualmente" para salvar alguns ciclos de relógio.
Aqui está o meu código C para a resolução de uma colisão entre uma esfera e uma caixa não-eixo alinhado. Ele se baseia em um par de minhas próprias rotinas de biblioteca, mas pode ser útil para alguns. Eu estou usando-o em um jogo e ele funciona perfeitamente.
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;
}
Na verdade, isso é muito mais simples. Você só precisa de duas coisas.
Em primeiro lugar, você precisa encontrar quatro ortogonal distâncias do centro do círculo para cada linha do retângulo. Em seguida, seu círculo não vai interseção com o retângulo se houver três deles são maiores do que o raio do círculo.
Em segundo lugar, você precisa encontrar a distância entre o centro do círculo e do centro do retângulo, então você círculo não estarão dentro do retângulo se a distância for maior do que a metade do comprimento diagonal retângulo.
Boa sorte!
A solução mais simples que eu vim acima com é bastante simples.
Ele funciona por encontrar o ponto no retângulo mais próximo do círculo, em seguida, comparando a distância.
Você pode fazer tudo isso com algumas operações, e até mesmo evitar a função 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;
}
E é isso! A solução acima assume uma origem na parte superior esquerda do mundo com o eixo x apontando para baixo.
Se você quer uma solução para lidar com colisões entre um círculo em movimento e retângulo, ele é muito mais complicado e coberto em outra resposta minha.
Para visualizar, tomar teclado numérico do seu teclado. Se a tecla '5' representa o retângulo, em seguida, todas as chaves 1-9 representam os 9 quadrantes do espaço dividido pelas linhas que compõem o seu retângulo (sendo 5 o interior.)
1) Se o centro do círculo é no quadrante 5 (isto é, no interior do rectângulo), em seguida, as duas formas intersectam.
Com isso fora do caminho, há dois casos possíveis: a) Os intersecta círculo com duas ou mais arestas vizinhas do rectângulo. b) Os intersecta círculo com uma extremidade do rectângulo.
O primeiro caso é simples. Se os intersecta círculo com dois bordos vizinhos do rectângulo, que deve conter o canto que liga estes dois bordos. (Isso, ou suas mentiras centro do quadrante 5, que já cobertos. Observe também que o caso em que cruza-se do círculo com apenas dois opostas bordas do retângulo é coberto também.)
2) Se qualquer um dos cantos A, B, C, D do mentira rectângulo dentro do círculo, em seguida, as duas formas intersectam.
O segundo caso é mais complicado. Devemos tomar nota de que só pode acontecer quando mentiras centro do círculo em um dos quadrantes 2, 4, 6 ou 8. (Na verdade, se o centro é em qualquer dos quadrantes 1, 3, 7, 8, a canto correspondente será o ponto mais próximo a ele.)
Agora, temos o caso de que o centro do círculo está em um dos quadrantes 'Edge', e isso só se cruza com a borda correspondente. Então, o ponto na extremidade que está mais próximo ao centro do círculo, deve situar-se dentro do círculo.
3) Para cada linha AB, BC, CD, DA, construo de linhas perpendiculares p (AB, P), p (AC, P), p (CD, P), p (DA, P) através do centro do círculo P. Para cada linha perpendicular, se o cruzamento com as mentiras borda originais dentro do círculo, em seguida, as duas formas intersectam.
Há um atalho para esta última etapa. Se o centro do círculo é no quadrante 8 e o bordo AB é a borda superior, o ponto de intersecção terá a coordenada y do A e B, e a coordenada x do centro P.
Você pode construir os quatro cruzamentos de linha e verificar se eles mentem em suas bordas correspondentes, ou descobrir qual P quadrante é in e check a interseção correspondente. Ambos devem simplificar a mesma equação booleana. Desconfie de que o passo 2 acima não descartou P estar em um dos quadrantes 'canto'; ele apenas olhou para um cruzamento.
Edit: Como se vê, eu ter esquecido o simples fato de que # 2 é um subcaso de # 3 acima. Afinal, cantos também são pontos nas bordas. Ver resposta da @ ShreevatsaR abaixo para uma grande explicação. E, no entretanto, esquecer # 2 acima, a menos que você quer um rápido, mas redundant check.
Esta função detectar colisões (interseções) entre Circle e Retângulo. Ele funciona como método e.James em sua resposta, mas este detectar colisões para todos os ângulos de retângulo (não só até esquina).
NOTA:
aRect.origin.x e aRect.origin.y são coordenadas do ângulo inferior esquerdo do retângulo!
aCircle.x e aCircle.y são coordenadas do círculo 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;
}
Eu criei classe para o trabalho com formas Esperamos que você goste
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;
}
}
Aqui está a modfied código 100% de trabalho:
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
Aqui está um teste-line um rápido para isso:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
Este é o caso, alinhado ao eixo onde rect_halves é um vector positivo que aponta a partir do meio rectângulo a um canto. A expressão dentro length() é um vector de delta center para um ponto mais próximo no rectângulo. Isso funciona em qualquer dimensão.
- Primeiro verifique se o retângulo e a tangente quadrado para as sobreposições círculo (fácil). Se eles não se sobrepõe, eles não colidem.
- Verifique se o centro do círculo está dentro do retângulo (fácil). Se ele está dentro, eles colidem.
- Calcular o mínimo quadrado distância dos lados do retângulo para o centro do círculo (pouco difícil). Se é menor que o raio ao quadrado, em seguida, eles colidem, então eles não fazem.
É eficiente, porque:
- Primeiro ele verifica o cenário mais comum com um algoritmo barato e quando é que eles não colidem, ela termina.
- Em seguida, ele verifica o cenário seguinte mais comum com um algoritmo barato (não calcular a raiz quadrada, usar os valores quadrados) e quando é certo que eles colidem termina.
- Em seguida, ele executa o algoritmo mais caro para verificar colisão com as fronteiras do retângulo.
Eu tenho um método que evita os Pitágoras caro se não for necessário - ie. quando delimitadora caixas do retângulo eo círculo não se cruzam.
E ele vai trabalhar para não-euclidiana demasiado:
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 pode ser substituído por Miny, Maxy eo mesmo para Minlon, maxLon: substituí-lo com minX, maxX
- NORMDIST ist método mais rápido, então o cálculo da distância completa um pouco. Por exemplo. sem a raiz quadrada no espaço euclidiano (ou sem um monte de outras coisas para haversine):
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Claro, se você usar esse método NORMDIST você precisa fazer criar umanormedDist = dist*dist;para o círculo
Veja a plena BBox e código do meu projeto GraphHopper Círculo .
Para aqueles que calcular colisão Circle / retângulo em coordenadas geográficas com SQL,
esta é a minha aplicação em Oracle 11 de sugeriu algoritmo .
Na entrada exige coordenadas círculo, raio do círculo no km e dois vértices coordenadas do retâ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;
Works, apenas descobriram isso há uma semana, e só agora chegou a testá-lo.
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
Supondo que você tenha as quatro bordas do retângulo verificar a distância a partir das bordas para o centro do círculo, se seu menos então o raio, em seguida, as formas são interseção.
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
Se os cruza retângulo para o círculo, um ou mais pontos de canto do retângulo deve estar dentro do círculo. Suponhamos que quatro pontos de um retângulo são A, B, C, D. pelo menos um deles deve intersectar o círculo. por isso, se a distância de um ponto para o centro do círculo é menor que o raio do círculo que deve cruzam o círculo. Para obter a distância que você pode usar o Teorema de Pitágoras,
H^2 = A^2 + B^2
Esta técnica tem alguns limites. Mas ele vai trabalhar melhor para os desenvolvedores de jogos. especialmente detecção de colisão
É uma boa atualização para o Algoritmo de Arvo
