Tantangan ini didasarkan pada deteksi tabrakan aktual yang harus saya tulis untuk permainan sederhana baru-baru ini.

Tulis program atau fungsi yang, mengingat dua objek, mengembalikan nilai yang benar atau salah tergantung pada apakah kedua objek tersebut bertabrakan (mis. Berpotongan) atau tidak.

Anda perlu mendukung tiga jenis objek:

• Segmen garis : diwakili oleh 4 pelampung, menunjukkan dua titik akhir, yaitu (x ₁ , y ₁ ) dan (x ₂ , y ₂ ) . Anda dapat mengasumsikan bahwa titik akhir tidak identik (sehingga segmen garis tidak mengalami degenerasi).
• Cakram : yaitu lingkaran yang diisi, diwakili oleh 3 pelampung, dua untuk pusat (x, y) dan satu (positif) untuk jari-jari r .
• Rongga : ini adalah pelengkap disk. Artinya, rongga mengisi semua ruang 2D, kecuali wilayah melingkar, ditentukan oleh pusat dan jari-jari.

Program atau fungsi Anda akan menerima dua objek tersebut dalam bentuk integer pengidentifikasi (pilihan Anda) dan 3 atau 4 floatnya. Anda dapat mengambil input melalui STDIN, ARGV atau argumen fungsi. Anda dapat mewakili input dalam bentuk apa pun yang tidak diproses sebelumnya, mis. 8 hingga 10 angka individual, dua daftar nilai yang dipisahkan koma atau dua daftar. Hasilnya dapat dikembalikan atau ditulis ke STDOUT.

Anda mungkin berasumsi bahwa objek-objek itu setidaknya 10 ^-10 unit panjang terpisah atau berpotongan sebanyak itu, sehingga Anda tidak perlu khawatir tentang keterbatasan tipe floating point.

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

Mewakili segmen garis dengan 0, cakram dengan 1dan lubang 2, dengan menggunakan format input berbasis daftar, yang berikut ini semua harus menghasilkan output yang benar:

[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

sementara yang berikut semua harus menghasilkan output yang salah

[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}

Jeda baris dalam fungsi fini untuk kejelasan. Mereka harus diganti dengan pemisah pernyataan⋄

Sudah begitu lama sejak saya terakhir membuat program APL yang begitu kompleks. Saya pikir yang terakhir kali ini tetapi saya bahkan tidak yakin itu serumit.

Format input
Pada dasarnya sama dengan OP, kecuali menggunakan 0untuk rongga, 1untuk disk dan 2untuk segmen garis.

Pembaruan utama

Saya berhasil bermain golf banyak karakter menggunakan algoritma yang berbeda. Tidak ada lagi gbulls ** t !!

Fungsi utama fdibagi menjadi beberapa kasus:

2 2≡x: Segmen-segmen

Dalam kasus ini, hitung vektor dari titik akhir setiap garis dan pecahkan sistem persamaan linear untuk memeriksa apakah persimpangan tersebut terdapat di dalam vektor.

Peringatan:

• Titik akhir vektor tidak dianggap sebagai bagian dari vektor (asal asalnya). Namun, jika hanya ujung vektor di yang lain, input tidak valid sesuai dengan spesifikasi.
• Segmen paralel yang tidak merosot selalu mengembalikan false, terlepas dari collinearity.
• Jika salah satu segmen mengalami kemunduran, selalu kembalikan false. Jika kedua segmen mengalami kemunduran, selalu kembali benar.

Contoh: (Perhatikan peringatan 1 sedang beraksi pada gambar di sebelah kanan)

2≡2⌷x: Segmen-lainnya

Dalam hal ini, objek lainnya adalah yang bundar. Periksa apakah titik akhir segmen berada di dalam lingkaran menggunakan pemeriksaan jarak.

Dalam kasus disk, buat juga segmen garis diameter yang tegak lurus terhadap segmen yang diberikan. Periksa apakah segmen bertabrakan dengan rekursi.
Dalam kasus rongga, menyelinap "kali 0" dalam pembangunan segmen tersebut untuk membuatnya merosot. (Lihat mengapa saya gunakan 0untuk rongga dan 1untuk disk sekarang?) Karena segmen yang diberikan tidak merosot, deteksi tabrakan segmen-segmen selalu kembali salah.

Akhirnya menggabungkan hasil pemeriksaan jarak dan deteksi tabrakan. Untuk kasus rongga, meniadakan hasil pemeriksaan jarak terlebih dahulu. Kemudian (dalam kedua kasus) ATAU 3 hasilnya bersamaan.

Mengenai peringatan segmen-segmen, angka 3 ditujukan (dan dieksploitasi). Nomor 2 bukan masalah karena kami memotong segmen tegak lurus di sini, yang tidak pernah sejajar jika tidak merosot. Nomor 1 berlaku hanya dalam kasus disk, ketika salah satu titik akhir yang diberikan adalah pada diameter yang dibangun. Jika titik akhir berada di dalam lingkaran, pemeriksaan jarak akan menanganinya. Jika titik akhir berada di lingkaran, karena diameter yang dibangun sejajar dengan segmen yang diberikan, yang terakhir harus bersinggungan dengan lingkaran dengan hanya satu titik menyentuh disk, yang bukan merupakan input yang valid.

Contoh:

Kasus bawaan: Lainnya-lainnya

Hitung jarak antara pusat. Tabrakan cakram-cakram terjadi jika dan hanya jika jaraknya lebih kecil dari jumlah jari-jari. Tabrakan rongga cakram terjadi jika dan hanya jika jaraknya lebih besar dari perbedaan jari-jari.

Untuk menangani rongga-rongga, meniadakan hasil pemeriksaan jarak, DAN dengan masing-masing bilangan bulat pengidentifikasi dan kemudian ATAU mereka bersama-sama. Menggunakan beberapa logika, seseorang dapat menunjukkan bahwa proses ini mengembalikan true jika dan hanya jika kedua bilangan bulat mengidentifikasi palsu (kasus rongga-rongga), atau jika pemeriksaan jarak kembali benar

Javascript - 393 byte

Diperkecil:

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])

Diperluas:

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]);

Catatan:

• mendefinisikan fungsi Fyang menerima argumen yang diperlukan dan mengembalikan nilai yang diperlukan
• format input identik dengan format dalam OP, dengan pengecualian bahwa kode tipe integer untuk setiap primitif terpisah dari tuple. Misalnya, F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )atau F( 1,[[3,0],1], 2,[[0,0],1] ).
• kode divalidasi pada semua kasus uji yang disediakan dalam OP
• harus menangani semua kasus tepi dan sudut, termasuk segmen garis panjang nol dan lingkaran radius nol

Python, 284

Saya menggunakan algoritma sampah yang cantik dibandingkan dengan semua trik geometrik ini, tetapi ia mendapatkan jawaban yang tepat meskipun dibutuhkan lebih dari satu menit untuk melewati kasus uji. Keuntungan besar adalah bahwa saya hanya perlu menulis tiga fungsi penilaian, dan hillclimbing menangani semua kasus tepi.

Golf:

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

Tidak Disatukan:

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

Dan akhirnya, skrip uji jika ada orang yang ingin mencoba ini dengan 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)