ti-enxame.com

Como faço para detectar interseções entre um círculo e qualquer outro círculo no mesmo plano?

Eu estou procurando um algoritmo para detectar se um círculo se cruza com qualquer outro círculo no mesmo plano (dado que pode haver mais de um círculo em um plano).

Um método que eu encontrei é fazer o teste do eixo de separação. Diz:

Dois objetos não se cruzam se você puder encontrar uma linha que separe os dois objetos, isto é, uma linha de forma que todos os objetos ou pontos de um objeto fiquem em lados diferentes da linha.

No entanto, não sei como aplicar esse método ao meu caso.

Alguém pode me ajudar?

33
Jean-Luc Godard

Dois círculos se cruzam se, e somente se, a distância entre seus centros estiver entre a soma e a diferença de seus raios. Dados dois círculos (x0, y0, R0) e (x1, y1, R1), a fórmula é a seguinte:

ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)

Esquadrar ambos os lados permite que você evite a lenta SQRT e permaneça com ints se suas entradas forem inteiros:

(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2

Como você precisa apenas de um teste sim/não, essa verificação é mais rápida do que calcular os pontos de interseção exatos.

A solução acima deve funcionar mesmo para o caso "um círculo dentro do outro".

63
dasblinkenlight

Assumindo a interseção do círculo preenchido (ou seja: um círculo dentro do outro é uma interseção).

Onde:

  • x0, y0, r0 = centro e raio do círculo 0.
  • x1, y1, r1 = centro e raio do círculo 1.

Código:

boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);
6
Craigo

Solução XNA/C #

    class Circle
    {
        public Vector2 Center;
        public float Radius;

        public bool Intersects(Circle circle)
        {
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusSum = circle.Radius + Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusSum * radiusSum;
        }
        public bool Contains(Circle circle)
        {
            if (circle.Radius > Radius)
                return false;
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusD = Radius - circle.Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusD * radiusD;
        }
    }

Observe que o método Circle.Intersects () retorna true mesmo se um círculo estiver dentro de outro (trata-os como círculos "preenchidos").

4
Peter Gruden

Se a distância entre os centros de dois círculos for no máximo a soma de seus raios, mas pelo menos o valor absoluto da diferença entre os raios, então os próprios círculos se cruzam em algum ponto.

A parte "pelo menos a diferença" se aplica se você se importar apenas com os próprios círculos, e não com suas áreas internas. Se você se importa se os círculos ou as áreas que eles delimitam compartilham pontos - isto é, se um círculo totalmente dentro do outro conta como "interseção" para você - então você pode abandonar "pelo menos a diferença" Verifica.

2
cHao

Eu tentei a fórmula dada aqui que é uma suposta resposta e todo mundo votou para cima, embora seja seriamente falho. Eu escrevi um programa em JavaFX para permitir ao usuário testar se dois círculos se cruzam alterando os valores centerX, centerY e Radius de cada círculo e esta fórmula absolutamente não funciona, exceto de uma maneira ... Eu não consigo entender por que, mas quando mova o círculo 2 perto do círculo 1 ele funciona mas quando eu movo o círculo 1 para o outro lado perto do círculo 2 ele não funciona ..... ????? isso é um pouco estranho ... imaginei que a fórmula precisava ser testada da maneira oposta também, então tentei isso e não funciona

if (Math.abs(circle1Radius - circle2Radius) <=
            Math.sqrt(Math.pow((circle1X - circle2X), 2)
            + Math.pow((circle1Y - circle2Y), 2)) &&
            Math.sqrt(Math.pow((circle1X - circle2X), 2)
            + Math.pow((circle1X - circle2Y), 2)) <=
            (circle1Radius + circle2Radius)} {
    return true;
} else {
    return false;
}

Isso funciona:

    // dx and dy are the vertical and horizontal distances
    double dx = circle2X - circle1X;
    double dy = circle2Y - circle1Y;

    // Determine the straight-line distance between centers.
    double d = Math.sqrt((dy * dy) + (dx * dx));

    // Check Intersections
    if (d > (circle1Radius + circle2Radius)) {
        // No Solution. Circles do not intersect
        return false;
    } else if (d < Math.abs(circle1Radius - circle2Radius)) {
        // No Solution. one circle is contained in the other
        return false;
    } else {
        return true;
    }

Vá aqui para a fórmula Intersecção de dois círculos

A fórmula usada não é minha fórmula todo o crédito vai para Paul Bourke (abril de 1997)

 First calculate the distance d between the center of the circles. d = ||P1 - P0||.

    If d > r0 + r1 then there are no solutions, the circles are separate.

    If d < |r0 - r1| then there are no solutions because one circle is contained within the other.

    If d = 0 and r0 = r1 then the circles are coincident and there are an infinite number of solutions.

Considering the two triangles P0P2P3 and P1P2P3 we can write

a2 + h2 = r02 and b2 + h2 = r12

Using d = a + b we can solve for a,

a = (r02 - r12 + d2 ) / (2 d)

It can be readily shown that this reduces to r0 when the two circles touch at one point, ie: d = r0 + r1

Solve for h by substituting a into the first equation, h2 = r02 - a2
So

P2 = P0 + a ( P1 - P0 ) / d

And finally, P3 = (x3,y3) in terms of P0 = (x0,y0), P1 = (x1,y1) and P2 = (x2,y2), is

x3 = x2 +- h ( y1 - y0 ) / d

y3 = y2 -+ h ( x1 - x0 ) / d 
0
John Conner