Detecção de colisão círculo-retângulo (interseção)

192

Como posso saber se um círculo e um retângulo se cruzam no espaço euclidiano 2D? (isto é, geometria 2D clássica)

aib
fonte
1
O retângulo está sempre alinhado com os eixos ou pode ser girado por um ângulo arbitrário?
e.James
11
@ eJames: como isso importa? Você está verificando o retângulo quanto à interseção com um círculo ; você sempre pode transformar seu sistema de coordenadas para que o retângulo é eixo paralelo com nenhuma mudança no círculo :-)
ShreevatsaR
Você deve adicionar isso como uma resposta, girando através -Θ e tudo ...
aib
2
@ShreevatsaR: Importa em termos de tempo ou não, preciso me preocupar com a tradução de coordenadas ou não. @aib: Oh querida!
e.James

Respostas:

191

Existem apenas dois casos em que o círculo cruza com o retângulo:

  • O centro do círculo fica dentro do retângulo ou
  • Uma das arestas do retângulo tem um ponto no círculo.

Observe que isso não requer que o retângulo seja paralelo ao eixo.

Algumas maneiras diferentes pelas quais um círculo e um retângulo podem se cruzar

(Uma maneira de ver isso: se nenhuma das arestas tem um ponto no círculo (se todas as arestas estiverem completamente "fora" do círculo)), a única maneira pela qual o círculo ainda pode cruzar o polígono é se ele estiver completamente dentro do círculo. polígono.)

Com essa visão, algo como o seguinte irá funcionar, onde o círculo tem centro Pe raio R, e o retângulo tem vértices A, B, C, Dnessa 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 alguma geometria, provavelmente já possui as funções acima em sua biblioteca. Caso contrário, pointInRectangle()pode ser implementado de várias maneiras; qualquer ponto geral nos métodos de polígono funcionará, mas para um retângulo, você pode apenas verificar se isso funciona:

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

E intersectCircle()é fácil de implementar também: uma maneira seria verificar se o pé da perpendicular deP à linha está próximo o suficiente e entre os pontos de extremidade e, caso contrário, verifique os pontos de extremidade.

O legal é que a mesma idéia funciona não apenas para retângulos, mas para a interseção de um círculo com qualquer polígono simples - nem precisa ser convexa!

ShreevatsaR
fonte
25
Pelo que vale, eu realmente acho que essa resposta é melhor que a minha. Duas razões principais: 1: não requer rotação se o retângulo não é paralelo ao eixo e, 2: o conceito se estende facilmente a todos os polígonos.
precisa saber é o seguinte
2
@paniq: Bem, ambos são de tempo constante. :-) Mas sim, isso é mais útil como uma solução geral, cobrindo retângulos com qualquer orientação e, de fato, com qualquer polígono simples.
amigos estão
7
e o caso em que o retângulo está completamente dentro do círculo, mas o centro do círculo não está dentro do retângulo?
Ericsoco
2
@ericsoco: Boa observação. :-) Acho que deveria ter dito "cruza o disco" em "uma das bordas do retângulo cruza o círculo", porque eu quis dizer significa que ele compartilha um ponto com o próprio círculo, não necessariamente o limite do círculo. De qualquer forma, a descrição acima, "verifique se o pé da perpendicular de P [centro do círculo] até a linha está perto o suficiente e entre os pontos finais e verifique os pontos finais caso contrário" ainda funcionará - por exemplo, os pontos finais estão dentro do círculo ( disco).
precisa
2
@ DexD.Hunter Se o centro do círculo estiver fora do retângulo, mas uma parte dele estiver dentro do retângulo, então necessariamente uma das arestas do retângulo cruza o círculo.
ShreevatsaR
289

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

Veja como funciona:

ilusão

  1. O primeiro par de linhas calcula os valores absolutos da diferença xey entre o centro do círculo e o centro do retângulo. Isso reduz os quatro quadrantes em um, para que os cálculos não precisem ser feitos quatro vezes. A imagem mostra a área em que o centro do círculo deve estar agora. Observe que apenas o quadrante único é mostrado. O retângulo é a área cinza e a borda vermelha descreve a área crítica, a exatamente um raio de distância das bordas do retângulo. O centro do círculo deve estar dentro dessa borda vermelha para que a interseção ocorra.

  2. O segundo par de linhas elimina os casos fáceis em que o círculo está longe o suficiente do retângulo (em qualquer direção) para que nenhuma interseção seja possível. Isso corresponde à área verde na imagem.

  3. O terceiro par de linhas lida com os casos fáceis em que o círculo está próximo o suficiente do retângulo (em qualquer direção) para garantir uma interseção. Isso corresponde às seções laranja e cinza da imagem. Observe que esta etapa deve ser executada após a etapa 2 para que a lógica faça sentido.

  4. As linhas restantes calculam o caso difícil em que o círculo pode cruzar o canto do retângulo. Para resolver, calcule a distância do centro do círculo e do canto e verifique se a distância não é maior que o raio do círculo. Esse cálculo retorna falso para todos os círculos cujo centro está dentro da área sombreada em vermelho e retorna verdadeiro para todos os círculos cujo centro está dentro da área sombreada em branco.

e.James
fonte
4
Muito agradável! Notas: aparentemente aqui, rect.x / y está no canto superior direito do retângulo. Além disso, você pode eliminar a raiz quadrada cara, comparando-a com o quadrado do raio.
Luqui
2
Oh não, meu mal. rect.x / y está no canto inferior esquerdo do retângulo. Eu teria escrito: circleDistance.x = abs (circle.x - (rect.x + rect.width / 2));
Luqui
2
@ Tanner: Lá vamos nós. Hooray para backups e TOC;)
e.James
11
apenas para esclarecer - esta resposta se aplica apenas aos retângulos alinhados ao eixo. isso fica claro na leitura de comentários em outras respostas, mas não é óbvio apenas nesta resposta + comentários. (grande resposta para rects alinhado ao eixo tho!)
ericsoco
3
Ótimo! É importante que os leitores saibam que aqui acredito que a definição de um ret é ret.x e ret.y são o centro do ret . No meu mundo, o xy de um rect é o topo / esquerda do rect e 0,0 é o topo / esquerda do ecrã, pelo que utilizei:circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
erco
123

Aqui está outra solução bastante simples de implementar (e muito rápida também). Ele captura todas as interseções, inclusive quando a esfera entrou totalmente no 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 matemática decente, isso pode ser reduzido para 3 ou 4 linhas.

Cygon
fonte
3
Você tem um bug lá, você procura o mais próximo com a esquerda e a direita, e não na parte superior e inferior, caso contrário, é uma solução adorável.
Manveru 21/05
8
Eu gosto desta resposta da melhor maneira. É curto, fácil de entender e rápido.
John Kurlak
2
Eu acho que sua solução falhará se o retângulo for oblíquo aos eixos x e y.
Leo
3
@ Leo Acho que não é difícil modificar esse algoritmo para acomodar esse caso, basta aplicar uma transformação de coordenadas em que a origem está no centro do retângulo e o retângulo não é mais oblíquo. Você precisa aplicar a transformação apenas ao centro do círculo.
Enobayram
1
É basicamente o mesmo que o código encontrado em migapro.com/circle-and-rotated-rectangle-collision-detection, que eu também portamos para o Objective-C. Funciona muito bem; é uma boa solução para o problema.
PKCLsoft
10

sua esfera e seu retângulo cruzam IIF,
a distância entre o centro do círculo e um vértice do seu ret é menor que o raio da sua esfera
OU
a distância entre o centro do círculo e uma aresta do seu ret é menor que o raio da sua esfera ( [ distância da linha do ponto ])
OU
o centro do círculo está dentro do retângulo

distância do ponto:

P1 = [x1, y1]
P2 = [x2, y2]
Distância = sqrt (abs (x1 - x2) + abs (y1-y2))

distância da linha do ponto:

L1 = [x1, y1], L2 = [x2, y2] (dois pontos da sua linha, ou seja, os pontos do vértice)
P1 = [px, py] algum ponto

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


circunferência do centro dentro
do retângulo : faça uma aproximação do eixo separador: se houver uma projeção em uma linha que separa o retângulo do ponto, eles não se cruzam

você projeta o ponto em linhas paralelas aos lados do seu ret e pode facilmente determinar se elas se cruzam. se eles não se cruzam nas 4 projeções, eles (o ponto e o retângulo) não podem se cruzar.

você só precisa do produto interno (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)

seu teste ficaria assim:

// arestas do retângulo: TL (canto superior esquerdo), TR (canto superior direito), BL (canto inferior esquerdo), BR (canto inferior direito)
// ponto a testar: POI

separado = falso
para egde em {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}: // as arestas
    D = borda [0] - borda [1]
    innerProd = D * POI
    Intervalo_min = min (D * margem [0], D * margem [1])
    Intervalo_max = max (D * margem [0], D * margem [1])
    caso contrário (Intervalo_min ≤ produto interno ≤ Intervalo_max) 
           separado = verdadeiro
           break // fim do loop 
    fim se
fim para
se (separado é verdadeiro)    
      retornar "sem interseção"
outro 
      retornar "interseção"
fim se

isso não assume um retângulo alinhado ao eixo e é facilmente extensível para testar interseções entre conjuntos convexos.

user104676
fonte
1
A distância ponto a ponto não deveria estar usando um quadrado, não um abs?
Thomas
6

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 metade da largura / altura é pré-calculada. A quadratura também é feita "manualmente" para salvar alguns ciclos de relógio.

intrepidis
fonte
3
Eu não acho que você possa afirmar que cinco testes / comparações no caminho de código mais caro são a “solução mais rápida” sem alguma prova.
27613 Sam 13:40
1
Na minha experiência com esse método, a colisão não acontece na maioria das vezes. Portanto, os testes causarão uma saída antes que a maior parte do código seja executada.
Intrepidis
6

A solução mais simples que encontrei é bem direta.

Ele funciona encontrando o ponto no retângulo mais próximo do círculo e comparando a distância.

Você pode fazer tudo isso com algumas operações e até 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 no canto superior esquerdo do mundo, com o eixo x apontando para baixo.

Se você deseja uma solução para lidar com colisões entre um círculo e um retângulo em movimento, é muito mais complicado e abordado em outra resposta minha.

ClickerMonkey
fonte
Isso não detectará interseções se o raio do círculo for muito pequeno e seu centro estiver dentro do retângulo!
Yoav
2
Você pode fornecer informações reais que façam isso falhar? Quando o círculo está dentro, a parte esquerda do teste é 0,0. A menos que o raio seja zero, a parte direita do teste deve ser> 0,0
ClickerMonkey
Isso também funciona com retângulos girados? se não, então por favor me dar uma dica sobre isso .....
M Abdul Sami
4

Na verdade, isso é muito mais simples. Você precisa apenas de duas coisas.

Primeiro, você precisa encontrar quatro ortogonais distâncias do centro do círculo para cada linha do retângulo. Em seguida, seu círculo não cruzará o retângulo se três deles forem maiores que o raio do círculo.

Segundo, você precisa encontrar a distância entre o centro do círculo e o centro do retângulo, para não circular dentro do retângulo se a distância for maior que a metade do comprimento diagonal do retângulo.

Boa sorte!


fonte
3

Aqui está o meu código C para resolver uma colisão entre uma esfera e uma caixa alinhada sem eixo. Ele conta com algumas das minhas próprias rotinas de biblioteca, mas pode ser útil para alguns. Estou usando em um jogo e 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;
}
Madrayken
fonte
2

Para visualizar, pegue o teclado numérico do seu teclado. Se a tecla '5' representa seu retângulo, todas as teclas de 1 a 9 representam os 9 quadrantes de espaço divididos pelas linhas que compõem seu retângulo (com 5 sendo o interior).

1) Se o centro do círculo estiver no quadrante 5 (ou seja, dentro do retângulo), as duas formas se cruzam.

Com isso fora do caminho, existem dois casos possíveis: a) O círculo cruza com duas ou mais arestas vizinhas do retângulo. b) O círculo cruza com uma aresta do retângulo.

O primeiro caso é simples. Se o círculo cruzar com duas arestas vizinhas do retângulo, ele deverá conter o canto que liga essas duas arestas. (Esse ou seu centro está no quadrante 5, que já abordamos. Observe também que o caso em que o círculo se cruza com apenas duas arestas opostas do retângulo também é coberto.)

2) Se algum dos cantos A, B, C, D do retângulo estiver dentro do círculo, as duas formas se cruzam.

O segundo caso é mais complicado. Devemos notar que isso só pode acontecer quando o centro do círculo estiver em um dos quadrantes 2, 4, 6 ou 8. (De fato, se o centro estiver em qualquer um dos quadrantes 1, 3, 7, 8, o o 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 da "aresta" e só cruza com a aresta correspondente. Então, o ponto na aresta mais próximo do centro do círculo deve estar dentro do círculo.

3) Para cada linha AB, BC, CD, DA, construa as linhas perpendiculares p (AB, P), p (BC, P), p (CD, P), p (DA, P) através do centro do círculo P. Para cada linha perpendicular, se a interseção com a aresta original estiver dentro do círculo, as duas formas se cruzam.

Há um atalho para esta última etapa. Se o centro do círculo estiver no quadrante 8 e a aresta AB for a aresta superior, o ponto de interseção terá as coordenadas y de A e B e as coordenadas x do centro P.

Você pode construir as quatro interseções de linha e verificar se elas estão nas arestas correspondentes, ou descobrir em que quadrante P está e verificar a interseção correspondente. Ambos devem simplificar para a mesma equação booleana. Desconfie de que o passo 2 acima não excluiu P estar em um dos quadrantes de 'canto'; apenas procurou um cruzamento.

Edit: Como se vê, eu negligenciei o simples fato de que # 2 é uma sub-caixa de # 3 acima. Afinal, os cantos também são pontos nas bordas. Veja a resposta de @ ShreevatsaR abaixo para uma ótima explicação. Enquanto isso, esqueça o item 2 acima, a menos que você queira uma verificação rápida, mas redundante.

aib
fonte
2

Esta função detecta colisões (interseções) entre Círculo e Retângulo. Ele funciona como o método e.James em sua resposta, mas este detecta colisões para todos os ângulos de retângulo (não apenas no canto superior direito).

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 Circle Center!

static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {

    float testX = aCircle.x;
    float testY = aCircle.y;

    if (testX < aRect.origin.x)
        testX = aRect.origin.x;
    if (testX > (aRect.origin.x + aRect.size.width))
        testX = (aRect.origin.x + aRect.size.width);
    if (testY < aRect.origin.y)
        testY = aRect.origin.y;
    if (testY > (aRect.origin.y + aRect.size.height))
        testY = (aRect.origin.y + aRect.size.height);

    return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}
Faraona
fonte
1

Eu tenho um método que evita as pitágoras caras, se não for necessário - ou seja. quando delimitar caixas do retângulo e do círculo não se cruzam.

E funcionará também para não-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 pode ser substituído por minY, maxY e o mesmo para minLon, maxLon: substitua por minX, maxX
  • O normDist é um método um pouco mais rápido que o cálculo da distância total. 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. Obviamente, se você usar esse método normDist, precisará criar um normedDist = dist*dist;para o círculo

Veja o código completo BBox e Circle do meu projeto GraphHopper .

Karussell
fonte
1

Criei turma para trabalhar com formas espero que gostem

public class Geomethry {
  public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;

    float rectCenterX = rectangleX + rectHalfWidth;
    float rectCenterY = rectangleY + rectHalfHeight;

    float deltax = Math.abs(rectCenterX - circleX);
    float deltay = Math.abs(rectCenterY - circleY);

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
        if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
}

public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;
    float rectHalfWidth2 = rectangleWidth2/2.0f;
    float rectHalfHeight2 = rectangleHeight2/2.0f;

    float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
    float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle
        if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
  } 
}
pwipo
fonte
1

Aqui está o 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

Bassam Alugili
fonte
1

Aqui está um teste rápido de uma linha 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 vetor positivo apontando do meio do retângulo para um canto. A expressão dentro length()é um vetor delta de centerum ponto mais próximo no retângulo. Isso funciona em qualquer dimensão.

Tyler
fonte
1
  • Primeiro verifique se o retângulo e o quadrado tangente ao círculo se sobrepõem (fácil). Se não se sobrepõem, não colidem.
  • Verifique se o centro do círculo está dentro do retângulo (fácil). Se estiver lá dentro, eles colidem.
  • Calcule a distância mínima ao quadrado dos lados do retângulo até o centro do círculo (pouco rígido). Se for menor que o raio ao quadrado, eles colidem, caso contrário, não.

É eficiente, porque:

  • Primeiro, ele verifica o cenário mais comum com um algoritmo barato e quando é certo que eles não colidem, ele termina.
  • Em seguida, ele verifica o próximo cenário mais comum com um algoritmo barato (não calcule a raiz quadrada, use os valores ao quadrado) e quando tiver certeza de que colidem ele termina.
  • Em seguida, ele executa o algoritmo mais caro para verificar a colisão com as bordas do retângulo.
David C.
fonte
1

funcionou para mim (só funciona quando o ângulo do retângulo é 180)

function intersects(circle, rect) {
  let left = rect.x + rect.width > circle.x - circle.radius;
  let right = rect.x < circle.x + circle.radius;
  let top = rect.y < circle.y + circle.radius;
  let bottom = rect.y + rect.height > circle.y - circle.radius;
  return left && right && bottom && top;
}
sandeep
fonte
hmmm ... votei nisso, mas depois testei corretamente e acho que não funciona nas esquinas, por exemplo. Funcionaria para dois retângulos.
Dan Zen
1

Melhorando um pouco a resposta do e.James:

double dx = abs(circle.x - rect.x) - rect.w / 2,
       dy = abs(circle.y - rect.y) - rect.h / 2;

if (dx > circle.r || dy > circle.r) { return false; }
if (dx <= 0 || dy <= 0) { return true; }

return (dx * dx + dy * dy <= circle.r * circle.r);

Isso subtrai rect.w / 2e rect.h / 2uma vez em vez de até três vezes.

Estid Felipe Lozano Reyes
fonte
0

Para aqueles que precisam calcular a colisão de Círculo / Retângulo nas coordenadas geográficas com SQL,
esta é minha implementação no oracle 11 do algoritmo sugerido e.James .

Na entrada, são necessárias coordenadas circulares, raio do círculo em km e duas coordenadas de vértices 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;    
fl4l
fonte
0

Funciona, descobri isso há uma semana atrás e agora comecei 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)));
user3026859
fonte
Pode funcionar para o Circle-Square, mas a pergunta é sobre Circle-Rectangle.
martineau
0
def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
    if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
        return True
else:
    if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
        return True
return False
Cassiano
fonte
-2

Supondo que você tenha as quatro arestas do retângulo, verifique a distância entre as arestas e o centro do círculo, se for menor que o raio, as formas estão se cruzando.

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
Para o seu próprio bem
fonte
E o caso em que um pequeno círculo é totalmente fechado por um retângulo grande? Certamente isso é um cruzamento e falharia no teste nesta resposta.
31968 Ken Paul
Ah, sim, eu não pensei nisso. Você poderia apenas adicionar mais verificações como se sqrt ((rectangleRight.x / 2 - circleCenter.x) ^ 2 + (rectangleBottom.y / 2 - circleCenter.y) ^ 2) <raio, então eles se cruzam Isso será longo e lento, mas, do topo da minha cabeça, é o melhor que consigo.
ForYourOwnGood
Eles podem se cruzar em qualquer ponto [único] em qualquer uma das arestas. Você também deve encontrar as distâncias do centro da borda. (Ah, e chame seus cantos de "cantos") :)
aib 31/12/08
Isso parece detectar apenas quando um canto está dentro do círculo.
Stark
-2

Se o retângulo se cruzar com o círculo, um ou mais pontos de canto do retângulo devem estar dentro do círculo. Suponha que os quatro pontos de um retângulo sejam A, B, C, D. pelo menos um deles deve cruzar o círculo. portanto, se a distância de um ponto ao centro do círculo for menor que o raio do círculo, ele deve cruzar o círculo. Para obter a distância, você pode usar o teorema de Pitágoras,

H^2 = A^2 + B^2

Essa técnica tem alguns limites. Mas funcionará melhor para os desenvolvedores de jogos. especialmente detecção de colisão

É uma boa atualização para o algoritmo do Arvo

Md. Ashraful Islam
fonte
Essa resposta está incrivelmente errada sempre que o retângulo tem um lado maior que o raio do círculo.
Paul K