Esse desafio é baseado na detecção de colisão real que tive que escrever recentemente para um jogo simples.

Escreva um programa ou função que, dados dois objetos, retorne um valor verdadeiro ou falso, dependendo de os dois objetos estarem em colisão (ou seja, se cruzarem) ou não.

Você precisa suportar três tipos de objetos:

• Segmentos de linha : representados por 4 pontos flutuantes, indicando os dois pontos finais, ou seja (x ₁ , y ₁ ) e (x ₂ , y ₂ ) . Você pode assumir que os pontos de extremidade não são idênticos (portanto, o segmento de linha não é degenerado).
• Discos : ou seja, círculos preenchidos, representados por 3 flutuadores, dois para o centro (x, y) e um (positivo) para o raio r .
• Cavidades : são o complemento de um disco. Ou seja, uma cavidade preenche todo o espaço 2D, exceto uma região circular, especificada por um centro e raio.

Seu programa ou função receberá dois desses objetos na forma de um número inteiro de identificação (de sua escolha) e seus 3 ou 4 carros alegóricos. Você pode receber entradas via STDIN, ARGV ou argumento de função. Você pode representar a entrada de qualquer forma conveniente que não seja pré-processada, por exemplo, 8 a 10 números individuais, duas listas de valores separadas por vírgula ou duas listas. O resultado pode ser retornado ou gravado em STDOUT.

Você pode supor que os objetos estejam com pelo menos 10 a ¹⁰ unidades de comprimento ou se cruzam com isso, portanto, não precisa se preocupar com as limitações dos tipos de ponto flutuante.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Casos de teste

Representando segmentos de linha com 0, discos 1e cavidades com 2, usando um formato de entrada baseado em lista, todos os itens a seguir devem produzir uma saída verdadeira:

[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

enquanto o seguinte deve resultar em uma saída 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}

Quebras de linha na função fsão para maior clareza. Eles devem ser substituídos pelo separador de instruções⋄

Faz tanto tempo desde a última vez que criei um programa APL tão complexo. Acho que a última vez foi essa, mas nem tenho certeza se isso foi tão complexo.

Formato de entrada
Basicamente igual ao OP, exceto 0para cavidade, 1disco e 2segmento de linha.

Major update

Consegui jogar muitos caracteres usando um algoritmo diferente. Não há mais gtouros ** t !!

A função principal fé dividida em casos:

2 2≡x: Segmento-segmento

Nesse caso, calcule o vetor a partir dos pontos finais de cada linha e resolva um sistema de equações lineares para verificar se a interseção está contida nos vetores.

Ressalvas:

• O ponto final de um vetor não é considerado como parte do vetor (enquanto sua origem é). No entanto, se apenas a ponta de um vetor estiver na outra, a entrada será inválida de acordo com as especificações.
• Segmentos paralelos não degenerados sempre retornam falsos, independentemente da colinearidade.
• Se um dos segmentos estiver degenerado, sempre retorne false. Se ambos os segmentos forem degenerados, sempre retorne verdadeiro.

Exemplos: (Observe a advertência 1 em ação na figura à direita)

2≡2⌷x: Segmento-outro

Nesse caso, o outro objeto é circular. Verifique se os pontos finais do segmento estão dentro do círculo usando a verificação de distância.

No caso do disco, também construa um segmento de linha do diâmetro perpendicular ao segmento especificado. Verifique se os segmentos colidem por recursão.
No caso da cavidade, esgueirar-se "vezes 0" na construção do referido segmento para fazê-lo degenerar. (Veja por que eu uso agora 0para cavidade e 1disco?) Como o segmento especificado não é degenerado, a detecção de colisão de segmento de segmento sempre retorna falso.

Finalmente, combine os resultados das verificações de distância e a detecção de colisão. Para o caso de cavidade, negue primeiro os resultados das verificações de distância. Então (em ambos os casos) OU os 3 resultados juntos.

Em relação às advertências segmento a segmento, os números 3 são abordados (e explorados). O número 2 não é um problema, pois estamos cruzando segmentos perpendiculares aqui, que nunca são paralelos se não forem degenerados. O número 1 entra em vigor apenas na caixa do disco, quando um dos pontos finais especificados está no diâmetro construído. Se o ponto final estiver bem dentro do círculo, as verificações de distância teriam resolvido isso. Se o ponto final estiver no círculo, já que o diâmetro construído é paralelo ao segmento especificado, o último deve ser tangente ao círculo, com apenas um ponto tocando no disco, o que não é uma entrada válida.

Exemplos:

Caso padrão: Outro-outro

Calcule a distância entre os centros. A colisão de disco ocorre se, e somente se, a distância for menor que a soma dos raios. A colisão da cavidade do disco ocorre se, e somente se, a distância for maior que a diferença nos raios.

Para cuidar do caso cavidade-cavidade, negue o resultado da verificação da distância E com cada um dos números inteiros de identificação e, em seguida, com OU. Usando alguma lógica, pode-se mostrar que esse processo retorna verdadeiro se e somente se ambos os números inteiros de identificação forem falsos (caso Cavidade-cavidade) ou se a verificação de distância retornou verdadeiro

Javascript - 393 bytes

Minificado:

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 a função Fque aceita os argumentos necessários e retorna o valor necessário
• O formato de entrada é idêntico ao formato no OP, com a exceção de que o código do tipo inteiro para cada primitiva é separado da tupla. Por exemplo, F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )ou F( 1,[[3,0],1], 2,[[0,0],1] ).
• código validado em todos os casos de teste fornecidos no OP
• deve lidar com todas as caixas de aresta e canto, incluindo segmentos de linha com comprimento zero e círculos com raio zero

Python, 284

Estou usando um algoritmo de lixo bastante comparado a todos esses truques geométricos, mas ele obtém as respostas certas, mesmo que demore mais de um minuto para passar pelos casos de teste. A grande vantagem é que eu só tenho que escrever as três funções de pontuação e a escalada cuida de todos os casos extremos.

Golfe:

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

Ungolfed:

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

E, finalmente, um script de teste, caso alguém queira tentar isso em 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)