Cómo determinar si dos sectores circulares se superponen entre sí

Question

Cada sector se puede representar como (x, y, r, a, d), donde x, y es la ubicación, r es el radio, d es la dirección, y a es el ángulo. Dada esta información de dos sectores circulares, ¿cómo determinar si se superponen entre sí? ¿Hay algún algoritmo eficiente para resolverlo? ¡Gracias!

Answer 1

Conozco una manera muy rápida de descartar esta posibilidad, ya que la usé para colisiones circulares.

Calcule la distancia entre los dos centros y luego, si es mayor que la suma de los radios, no puede haber colisión. Para una mayor eficacia, no utilice la raíz cuadrada, sólo el trabajo directamente en los valores al cuadrado:

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (r1 + r2) * (r1 + r2): 
    # No chance of collision. 

Trabajando hacia fuera para segmentos circulares será un poco más difícil.

---

Su elección del método depende de la precisión que necesite. Si estás haciendo matemáticas reales, probablemente necesites una gran precisión. Pero, por ejemplo, si estás haciendo esto para algo así como un juego de computadora, lo suficientemente cerca puede ser lo suficientemente bueno.

Si ese fuera el caso, buscaría transformar el arco en una serie de líneas rectas (cuyo número probablemente dependería de a, la "extensión" del arco). Probablemente podría salirse con la suya un par de líneas para una extensión de un grado de arco, pero eso no funcionaría demasiado bien para 180 grados).

La detección de colisiones de línea recta es un método mucho más conocido, aunque debe tener en cuenta que el número de comparaciones puede aumentar rápidamente.

---

Si no desea utilizar segmentos de línea, este es el proceso a seguir. Utiliza un algoritmo de colisión circular para descubrir el cero, uno o dos puntos de colisión para los círculos completos, luego verifica esos puntos para ver si están dentro de ambos arcos.

Primero, ejecute esa marca de verificación para detectar el caso donde no es posible una colisión. Si no es posible una colisión entre los círculos, tampoco pueden colisionar los arcos.

En segundo lugar, compruebe si los círculos tienen un solo punto de colisión. Ese es el caso si:

(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) == (r1 + r2) * (r1 + r2) 

dentro de un margen de error adecuado, por supuesto. Todos deberíamos saber ahora que la comparación de los números de coma flotante para la igualdad debería usar algún tipo de comparación delta.

Si ese es el caso, tiene un punto para comprobar y puede encontrar ese punto fácilmente. Es el punto r1 unidades a lo largo de la línea recta que va desde (x1,y1) a (x2,y2) o, mirándolo como mover alguna fracción largo de esa línea:

(x1 + (x2-x1) * (r1+r2)/r1, y1 + (y2-y1) * (r1+r2)/r1) 

De lo contrario, hay dos puntos a comprobar y se pueden utilizar las respuestas a una pregunta como this one para establecer cuáles son esos dos puntos.

vez que haya algunos puntos de colisión, es una much simpler method para averiguar si esos puntos están en un arco, teniendo en cuenta que el punto candidato tendrá que ser en ambos arcos para que chocan entre sí, no sólo en un .

Answer 2

Ya que tenemos sectores circulares, ángulo y la dirección no importa si usted está haciendo esto en tiempo real. Lo siguiente aplica solo a sectores de círculo completo, o si ambos sectores están apuntando el uno al otro.

puede seguir los siguientes pasos:

1) Encuentra la distancia entre cada sector, 2) Restar tanto radio a esa distancia, 3) si el resultado es negativo, se ha producido una colisión entre ambos sectores. de lo contrario, es la distancia a la colisión.

por ejemplo, tenemos dos sectores, tanto con un radio de 50 unidad. la distancia entre sus puntos centrales es 80. reste 80-50-50 = -20, para que sepa que ha habido una colisión de 20 unidades de distancia.

de otro modo, si la distancia era de 500, 500-50-50 = 400, un valor positivo, ahora se sabe que estos dos sectores son 400 unidades de diferencia.

ahora, si los círculos están muy cerca, por ejemplo, 1 unidad aparte, 1-50-50 = -99, lo que significa que se superponen casi por completo.

Para los verdaderos sectores circulares segmentados que es lo que ha especificado en los comentarios, debe usar las respuestas paxdiablos o Macs.

Answer 3

Hay dos pasos. En primer lugar es averiguar si los dos centros son lo suficientemente cerca entre sí para permitir una colisión, lo cual puede hacerse mediante la comparación de la distancia entre ellos a la suma de sus radios:

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) > ((r1 + r2) * (r1 + r2))) 
    // No collision. 

Luego hay que comprobar si la línea entre los centros cae dentro de los arcos definidos por sus diversos ángulos:

float angle1to2 = Math.atan2(y2 - y1, x2 - x1); 
if (angle1to2 < (d1 - a1/2) || angle1to2 > (d1 + a1/2)) 
    // No collision 
float angle2to1 = angle1to2 + Math.PI; 
if (angle2to1 < (d2 - a2/2) || angle2to1 > (d2 + a2/2)) 
    // No collision 

Si se obtiene a través de estos cheques sin la posibilidad de una colisión ser excluido, entonces usted ha detectado con éxito una colisión.

Advertencia: este código no se ha probado en absoluto. En particular, las llamadas atan2 pueden necesitar algunos ajustes dependiendo de su sistema de coordenadas.

EDIT: acaba de darse cuenta de que se pierde un caso de esquina importante, donde los arcos no están "apuntando" entre sí, pero aún se superponen. Se rumiará sobre esto y regresará ...