Este desafío se basa en la detección de colisión real que tuve que escribir para un juego simple recientemente.

Escriba un programa o función que, dados dos objetos, devuelva un valor verdadero o falso dependiendo de si los dos objetos están en colisión (es decir, se cruzan) o no.

Debe admitir tres tipos de objetos:

• Segmentos de línea : representados por 4 flotantes, que indican los dos puntos finales, es decir (x ₁ , y ₁ ) y (x ₂ , y ₂ ) . Puede suponer que los puntos finales no son idénticos (por lo que el segmento de línea no está degenerado).
• Discos : es decir, círculos rellenos, representados por 3 flotadores, dos para el centro (x, y) y uno (positivo) para el radio r .
• Cavidades : son el complemento de un disco. Es decir, una cavidad llena todo el espacio 2D, excepto una región circular, especificada por un centro y radio.

Su programa o función recibirá dos de estos objetos en forma de un número entero de identificación (de su elección) y sus 3 o 4 flotantes. Puede tomar la entrada a través de STDIN, ARGV o argumento de función. Puede representar la entrada en cualquier forma conveniente que no esté preprocesada, por ejemplo, de 8 a 10 números individuales, dos listas de valores separados por comas o dos listas. El resultado puede ser devuelto o escrito en STDOUT.

Puede suponer que los objetos están separados por al menos ^10-10 unidades de longitud o que se cruzan entre sí, por lo que no debe preocuparse por las limitaciones de los tipos de punto flotante.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Representando segmentos de línea con 0, discos con 1y cavidades con 2, usando un formato de entrada basado en listas, lo siguiente debería producir una salida verdadera:

[0,[0,0],[2,2]], [0,[1,0],[2,4]]        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1]       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1]        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1]   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1]       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1]        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1]   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2]                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1]            # Intersecting discs
[1,[3,0],1], [2,[0,0],1]                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1]              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1]                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1]                # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1]               # Any two cavities intersect

mientras que lo siguiente debería resultar en una salida falsa

[0,[0,0],[1,0]], [0,[0,1],[1,1]]        # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]]      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]]        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]]        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1]           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1]            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1]  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5]             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity

APL, 279 208 206 203

s←1 ¯1
f←{x←⊣/¨z←⍺⍵[⍋⊣/¨⍺⍵]
2 2≡x:∧/0∧.=⌊(2⊃-⌿↑z)⌹⍣(≠.×∘⌽/x)⍉↑x←s×-/2⊢/↑z
2≡2⌷x:∨/((2⊃z)∇2,x[1]×(2⌷⊃z)+,∘-⍨⊂y÷.5*⍨+.×⍨y←⌽s×⊃-/y),x[1]=(×⍨3⊃⊃z)>+.×⍨¨y←(s↓⌽↑z)-2⌷⊃z
~x∨.∧x[1]≠(.5*⍨+.×⍨2⊃-⌿↑z)<-/⊢/¨z×s*1⌷x}

Los saltos de línea en la función fson para mayor claridad. Deben reemplazarse con el separador de instrucciones⋄

Ha pasado mucho tiempo desde la última vez que hice un programa APL tan complejo. Creo que la última vez fue esta, pero ni siquiera estoy seguro de que fuera tan complejo.

Formato de entrada
Básicamente igual que el OP, excepto que se usa 0para cavidad, 1para disco y 2para segmento de línea.

Actualización importante

Logré jugar muchos caracteres usando un algoritmo diferente. No más gtoros ** t !!

La función principal fse divide en casos:

2 2≡x: Segmento-segmento

En este caso, calcule el vector a partir de los puntos finales de cada línea y resuelva un sistema de ecuaciones lineales para verificar si la intersección está contenida dentro de los vectores.

Advertencias:

• El punto final de un vector no se considera parte del vector (mientras que su origen sí lo es). Sin embargo, si solo la punta de un vector está en el otro, la entrada no es válida de acuerdo con las especificaciones.
• Los segmentos paralelos no degenerados siempre devuelven falso, independientemente de la colinealidad.
• Si uno de los segmentos está degenerado, siempre devuelve falso. Si ambos segmentos están degenerados, siempre devuelve verdadero.

Ejemplos: (Tenga en cuenta la advertencia 1 en acción en la figura de la derecha)

2≡2⌷x: Segmento-otro

En este caso, el otro objeto es circular. Verifique si los puntos finales del segmento están dentro del círculo utilizando la verificación de distancia.

En el caso del disco, también construya un segmento lineal del diámetro perpendicular al segmento dado. Compruebe si los segmentos chocan por recursividad.
En el caso de la cavidad, colóquese un "multiplicado por 0" en la construcción de dicho segmento para que se degenere. (¿Ves por qué lo uso 0para cavidad y 1para disco ahora?) Como el segmento dado no está degenerado, la detección de colisión segmento-segmento siempre devuelve falso.

Finalmente, combine los resultados de las comprobaciones de distancia y la detección de colisiones. Para el caso de la cavidad, niegue primero los resultados de las comprobaciones de distancia. Luego (en ambos casos) O los 3 resultados juntos.

Con respecto a las advertencias segmento-segmento, se abordan los números 3 (y se explotan). El número 2 no es un problema ya que estamos intersectando segmentos perpendiculares aquí, que nunca son paralelos si no están degenerados. El número 1 solo tiene efecto en la caja del disco, cuando uno de los puntos finales dados está en el diámetro construido. Si el punto final está bien dentro del círculo, las comprobaciones de distancia lo habrían solucionado. Si el punto final está en el círculo, dado que el diámetro construido es paralelo al segmento dado, este último debe ser tangente al círculo con solo un punto tocando el disco, que no es una entrada válida.

Ejemplos:

Caso predeterminado: Otro-otro

Calcule la distancia entre los centros. La colisión disco-disco ocurre si y solo si la distancia es menor que la suma de los radios. La colisión de la cavidad del disco ocurre si y solo si la distancia es mayor que la diferencia en radios.

Para cuidar el caso cavidad-cavidad, niegue el resultado de la verificación de distancia, Y con cada uno de los enteros identificadores y luego O juntos. Usando algo de lógica, se puede mostrar que este proceso devuelve verdadero si y solo si ambos enteros identificadores son falsos (caso de cavidad-cavidad), o si la verificación de distancia devuelve verdadero

Javascript - 393 bytes

Minified:

F=(s,a,t,b,e,x)=>(x=e||F(t,b,s,a,1),[A,B]=a,[C,D]=b,r=(p,l)=>([g,h]=l,[f,i]=y(h,g),[j,k]=y(p,g),m=Math.sqrt(f*f+i*i),[(f*j+i*k)/m,(f*k-i*j)/m]),u=(p,c)=>([f,g]=c,[i,j]=y(p,f),i*i+j*j<g*g),y=(p,c)=>[p[0]-c[0],p[1]-c[1]],[n,o]=r(C,a),[q,v]=r(D,a),w=(v*n-o*q)/(v-o),z=r(B,a)[0],Y=u(A,b),Z=u(B,b),[v*o<0&&w*(w-z)<0,Y||Z||o<D&&o>-D&&n*(n-z)<0,!Y||!Z,x,u(A,[C,D+B]),B>D||!u(A,[C,D-B]),x,x,1][s*3+t])

Expandido:

F = (s,a,t,b,e,x) => (
    x = e || F(t,b,s,a,1),
    [A,B] = a,
    [C,D] = b,
    r = (p,l) => (
        [g,h] = l,
        [f,i] = y(h,g),
        [j,k] = y(p,g),
        m = Math.sqrt( f*f + i*i ),
        [(f*j + i*k)/m, (f*k - i*j)/m] ),
    u = (p,c) => (
        [f,g] = c,
        [i,j] = y(p,f),
        i*i + j*j < g*g ),
    y = (p,c) => [p[0] - c[0], p[1] - c[1]],
    [n,o] = r(C,a),
    [q,v] = r(D,a),
    w = (v*n - o*q)/(v - o),
    z = r(B,a)[0],
    Y = u(A,b), Z = u(B,b),
    [   v*o < 0 && w*(w-z) < 0,
        Y || Z || o < D && o > -D && n*(n-z) < 0,
        !Y || !Z,
        x,
        u(A,[C,D+B]),
        B > D || !u(A,[C,D-B]),
        x,
        x,
        1
    ][s*3+t]);

Notas:

• define la función F que acepta los argumentos requeridos y devuelve el valor requerido
• El formato de entrada es idéntico al formato en el OP, con la excepción de que el código de tipo entero para cada primitiva está separado de la tupla. Por ejemplo, F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )o F( 1,[[3,0],1], 2,[[0,0],1] ).
• código validado en todos los casos de prueba suministrados en el OP
• debe manejar todas las mayúsculas y minúsculas, incluidos los segmentos de línea de longitud cero y los círculos de radio cero

Pitón, 284

Estoy usando un algoritmo de basura bonito en comparación con todos estos trucos geométricos, pero obtiene las respuestas correctas a pesar de que lleva más de un minuto superar los casos de prueba. La gran ventaja es que solo tengo que escribir las tres funciones de puntuación, y la escalada se ocupa de todos los casos extremos.

Golfizado:

import math,random as r
n=lambda(a,c),(b,d):math.sqrt((a-b)**2+(c-d)**2)
x=lambda(t,a,b),p:max(eval(["n(b,p)-n(a,b)+","-b+","b-"][t]+'n(a,p)'),0)
def F(t,j):
q=0,0;w=1e9
 for i in q*9000:
    y=x(t,q)+x(j,q)
    if y<w:p,w=q,y
    q=(r.random()-.5)*w+p[0],(r.random()-.5)*w+p[1]
 return w<.0001

Sin golf:

import math
import random as r
def norm(a, b):
 return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def lineWeight(a, b, p):
 l1 = norm(a, p)
 l2 = norm(b, p)
 return min(l1, l2, l1 + l2 - norm(a, b))

def circleWeight(a, r, p):
 return max(0, norm(a, p) - r)

def voidWeight(a, r, p):
 return max(0, r - norm(a, p))

def weight(f1, f2, s1, s2, p):
 return f1(s1[1], s1[2], p) + f2(s2[1], s2[2], p)

def checkCollision(s1, s2):
 a = [lineWeight, circleWeight, voidWeight]
 f1 = a[s1[0]]
 f2 = a[s2[0]]
 p = (0.0, 0.0)
 w = 0
 for i in a*1000:
  w = weight(f1, f2, s1, s2, p)
  p2 = ((r.random()-.5)*w + p[0], (r.random()-.5)*w + p[1])
  if(weight(f1, f2, s1, s2, p2) < w):
   p = p2
 if w < .0001:
  return True
 return False

Y finalmente, un script de prueba en caso de que alguien más quiera probar esto en python:

import collisiongolfedbak
reload(collisiongolfedbak)

tests = [
[0,[0,0],[2,2]], [0,[1,0],[2,4]],        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1],       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1],        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1],   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1],       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1],        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1],   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2],                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1],            # Intersecting discs
[1,[3,0],1], [2,[0,0],1],                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1],              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1],                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1] ,               # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1] ,              # Any two cavities intersect
[0,[0,0],[1,0]], [0,[0,1],[1,1]] ,       # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]],      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]],        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]],        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1],           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1],            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1],  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5],             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity
]

for a, b in zip(tests[0::2], tests[1::2]):
 print collisiongolfedbak.F(a,b)