• Jueves 28 de Marzo de 2024, 20:08

Autor Tema:  Colision Circulo - Cuadrado  (Leído 5771 veces)

prueba2306

  • Miembro activo
  • **
  • Mensajes: 51
    • Ver Perfil
Colision Circulo - Cuadrado
« en: Miércoles 18 de Febrero de 2004, 02:57 »
0
Últimamente he estado buscando en la red cómo puedo llevar a cabo una colisión circulo - cuadrado, pero los ejemplos que muestran son un poco confusos (sumándole a que casi no se inglés)  :huh: .

Además de buscar también ejemplos de cuadrados que no están alineados con los ejes cardinales (x,y).

El tipo de juego que estoy haciendo es en 2d y garadecería mucho que alguién me enviara información al respecto o un link donde pueda informarme de forma clara (de preferencia en español... o talvez en inglés  :P).

Gracias de antemano.

Amilius

  • Miembro HIPER activo
  • ****
  • Mensajes: 665
    • Ver Perfil
Re: Colision Circulo - Cuadrado
« Respuesta #1 en: Miércoles 18 de Febrero de 2004, 16:18 »
0
Prueba con el DelphiX, es Open Source para Delphi 3 adelante.

Tiene un algoritmo de colisión inicialmente por rectángulos y una opción para activar colisión por pixeles.

Como el algoritmo que buscas es demasiado específico y poco aplicable en la generalidad de casos dudo que lo encuentres.

El algoritmo de colisión de pixeles sirve para cualquier tipo de formas geométricas, no importa lo retorcidas que sean:

- 1. Calcula el rectángulo de intersección de los dos rectángulos que enmarcan los "sprites" que se desea verificar si colisionaron o no. Es decir que previamente ejecuta un algoritmo de colisión por rectángulos que por fines de optimización es muchísimo más rápido.

- 2. Si el área del rectángulo de intersección es mayor o igual a cierto porcentaje "umbral" de una de las áreas rectángulo de los sprites,  por ejemplo 50%, es aconsejable indicar que existió una colisión. (<100% Sólo con fines de optimización. Si se quiere ser estrictamente precisos este umbral debe ser del 100%)

- 3. En el rectángulo intersección calculado hace un barrido hasta terminar con dicha área o encontrar dos pixeles con valor disntinto de "transparente" en ambos sprites y que vayan a "dibujarse" en el mismo sector, en ese caso existió una colisión.

Como ves el algoritmo es bastante sencillo, lo complicado son los detalles de implementación.

prueba2306

  • Miembro activo
  • **
  • Mensajes: 51
    • Ver Perfil
Re: Colision Circulo - Cuadrado
« Respuesta #2 en: Jueves 19 de Febrero de 2004, 20:52 »
0
:hola: Gracias por tu respuesta.

El problema es que estoy haciendo un juego de vista isométrica con java (usando applets) y existen los dos tipos de colisiones que antes mencioné, por lo que no creo que pueda usar ese tipo de colisión  :unsure: .

Gracias de todas maneras por tu ayuda. La tendré en cuenta cuando use delphi  :D .

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Colision Circulo - Cuadrado
« Respuesta #3 en: Sábado 21 de Febrero de 2004, 13:28 »
0
Hola.

Para poder saber si un círculo ha colisionado con un cuadrado (o rectángulo o cualquier cuadrilátero en general) se me ocurre que podrías hacer lo siguiente:
  • Tener representado el cuadrado por sus 4 vértices y sus 4 aristas.</li>
  • Calcular la distancia desde cada arista al centro del círculo.</li>
  • Si la distancia es menor que el radio del círculo, entonces hay colisión.</li>
Espero que te sirva, un saludo.

Ruben3d

Amilius

  • Miembro HIPER activo
  • ****
  • Mensajes: 665
    • Ver Perfil
Re: Colision Circulo - Cuadrado
« Respuesta #4 en: Sábado 21 de Febrero de 2004, 14:41 »
0
Cita de: "Ruben3d"
Hola.

Para poder saber si un círculo ha colisionado con un cuadrado (o rectángulo o cualquier cuadrilátero en general) se me ocurre que podrías hacer lo siguiente:
  • Tener representado el cuadrado por sus 4 vértices y sus 4 aristas.</li>
  • Calcular la distancia desde cada arista al centro del círculo.</li>
  • Si la distancia es menor que el radio del círculo, entonces hay colisión.</li>
Espero que te sirva, un saludo.

Ruben3d
Buena idea, pero existe un caso no cubierto:

- Si el círculo está contenido por completo por el cuadrilátero.

En ese caso la distancia desde cualquier punto del borde del cuadrilátero al centro del círculo será siempre mayor al radio del círculo.

Y la solución también es simple: calcular la distancia entre los centros de ambas figuras y que esa distancia también sea mayor al radio del círculo.

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Colision Circulo - Cuadrado
« Respuesta #5 en: Lunes 23 de Febrero de 2004, 20:37 »
0
Citar
calcular la distancia entre los centros de ambas figuras y que esa distancia también sea mayor al radio del círculo.

Esta solución para el caso particular falla si el círculo es considerablemente más pequeño que el cuadrilátero. Para ilustrarlo, pongo un ejemplo simple con un rectángulo de lados paralelos a los ejes:
Código: Text
  1.  
  2.  
  3. +---------------------------------+
  4. |                                 |
  5. |                                 |
  6. |                          _      |
  7. |                         / &#092;     |
  8. |                        |   |    |
  9. |                         &#092;_/     |
  10. +---------------------------------+
  11.  
  12.  
  13.  

Como se puede observar (a pesar de mi habilidad haciendo dibujos en ASCII) el centro del círculo cumple la condición de estar más alejado del centro del rectángulo que el tamaño del radio, por lo que no habría colisión, cuando en verdad sí la hay.

Creo que la solución pasaría por determinar si el centro del círculo está en el interior del cuadrado. Esto es bastante fácil si el rectángulo está alineado con los ejes, pero si no lo está el proceso es bastante más costoso computacionalmente hablando.

Un saludo.

Ruben3d

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Colision Circulo - Cuadrado
« Respuesta #6 en: Lunes 23 de Febrero de 2004, 21:09 »
0
Se me acaba de ocurrir cómo computar eficientemente si el centro del círculo está en el interior del cuadrilátero aprovechando que se trata de un juego en vista isométrica.

En un juego de este tipo, el cuadrilátero será un rombo, con este aspecto:

Código: Text
  1.  
  2.           B
  3.          /&#092;
  4.       /      &#092;
  5. A /      .O    &#092;
  6.    &#092;            / C
  7.       &#092;      /
  8.          &#092;/
  9.          D
  10.  
  11.  

donde A, B, C, D y O son puntos.

Viendo el dibujo podemos observar que A y C están a la misma altura, alineados con O. También están alineados B, O y D. Aprovechando esta característica se puede saber con pocos cálculos si el punto está en el interior del rombo realizando subdivisiones del espacio:
  • Se calcula si el punto está a la izq. o a la dcha. de la recta BD (eficiente, pues está alineada con el eje Y). Esto nos divide el espacio en dos subespacios.</li>
  • Calcular si el punto está encima o debajo de la recta AC (también eficiente). Esto nos divide el subespacio en el que estemos en otros dos.</li>
  • Llegados a este punto, en el subespacio que estemos sólo habrá una recta: AB, BC, CD ó DA. Dependiendo de en el subespacio que estemos, habrá que saber si estamos encima o debajo de la recta.</li>
  • Construimos la ecuación punto-pendiente de la recta correspondiente y sustituimos el valor de la componente X del punto.</li>
  • Ya solo resta comparar el resultado con el valor de la componente Y del punto para saber si está encima o debajo de la recta.</li>
De esta manera, sólo hay que realizar un cálculo complejo para uno de los segmentos, en vez de los cuatro.

Espero no haber metido la pata en ningún lado.

Un saludo.

Ruben3d