Wyzwanie to opiera się na wykrywaniu kolizji, które ostatnio musiałem napisać dla prostej gry.

Napisz program lub funkcję, która, biorąc pod uwagę dwa obiekty, zwraca wartość prawdy lub fałszu w zależności od tego, czy oba obiekty są w kolizji (tj. Przecinają się), czy nie.

Musisz obsługiwać trzy typy obiektów:

• Segmenty linii : reprezentowane przez 4 zmiennoprzecinkowe, wskazujące dwa punkty końcowe, tj. (X ₁ , y ₁ ) i (x ₂ , y ₂ ) . Możesz założyć, że punkty końcowe nie są identyczne (więc odcinek linii nie jest zdegenerowany).
• Tarcze : tzn. Wypełnione koła, reprezentowane przez 3 zmiennoprzecinkowe, dwie dla środka (x, y) i jedną (dodatnią) dla promienia r .
• Wnęki : są uzupełnieniem płyty. Oznacza to, że wnęka wypełnia całą przestrzeń 2D, z wyjątkiem okrągłego obszaru określonego przez środek i promień.

Twój program lub funkcja otrzyma dwa takie obiekty w postaci identyfikującej liczby całkowitej (do wyboru) i ich 3 lub 4 zmiennoprzecinkowe. Możesz przyjmować dane wejściowe za pomocą argumentu STDIN, ARGV lub funkcji. Możesz reprezentować dane wejściowe w dowolnej dogodnej formie, która nie jest wstępnie przetwarzana, np. Od 8 do 10 pojedynczych liczb, dwie listy wartości oddzielone przecinkami lub dwie listy. Wynik można zwrócić lub zapisać w STDOUT.

Możesz założyć, że obiekty są oddalone od siebie o co najmniej ^10-10 jednostek lub przecinają się tak bardzo, więc nie musisz się martwić ograniczeniami typów zmiennoprzecinkowych.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Reprezentując segmenty linii 0, dyski 1i wnęki 2, przy użyciu formatu wejściowego opartego na listach, poniższe elementy powinny generować prawdziwy wynik:

[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

podczas gdy poniższe powinny skutkować wynikiem fałszowania

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

Podziały linii w funkcji fsłużą przejrzystości. Powinny zostać zastąpione separatorem instrukcji⋄

Minęło tyle czasu, odkąd ostatnio stworzyłem tak złożony program APL. Myślę, że był to ostatni raz, ale nie jestem nawet pewien, czy to było tak złożone.

Format wejściowy
Zasadniczo taki sam jak OP, z wyjątkiem użycia 0wnęki, 1dla dysku i 2dla segmentu linii.

Ważna aktualizacja

Udało mi się zagrać w golfa wiele znaków przy użyciu innego algorytmu. Nigdy więcej gbyków ** t !!

Główna funkcja fjest podzielona na przypadki:

2 2≡x: Segment-segment

W takim przypadku obliczyć wektor z punktów końcowych każdej linii i rozwiązać układ równań liniowych, aby sprawdzić, czy przecięcie jest zawarte w wektorach.

Ostrzeżenia:

• Punkt końcowy wektora nie jest uważany za część wektora (podczas gdy jego początkiem jest). Jednak jeśli tylko końcówka wektora znajduje się na drugim, dane wejściowe są nieprawidłowe zgodnie ze specyfikacją.
• Nie zdegenerowane równoległe segmenty zawsze zwracają fałsz, niezależnie od kolinearności.
• Jeśli jeden z segmentów jest zdegenerowany, zawsze zwracaj wartość false. Jeśli oba segmenty są zdegenerowane, zawsze zwracaj true.

Przykłady: (Uwaga zastrzeżenie 1 w akcji na rysunku po prawej)

2≡2⌷x: Inne segmenty

W tym przypadku drugi obiekt jest okrągły. Sprawdź, czy punkty końcowe segmentu znajdują się w okręgu za pomocą kontroli odległości.

W przypadku dysku zbuduj również odcinek linii o średnicy prostopadłej do danego odcinka. Sprawdź, czy segmenty nie kolidują przez rekurencję.
W przypadku wnęki zakradnij się „razy 0” w konstrukcji wspomnianego segmentu, aby go zdegenerować. (Zobacz, dlaczego używam teraz 0wnęki i 1dysku?) Ponieważ dany segment nie jest zdegenerowany, wykrywanie kolizji segmentu zawsze zwraca wartość false.

Na koniec połącz wyniki kontroli odległości i wykrycia kolizji. W przypadku wnęki najpierw neguj wyniki kontroli odległości. Następnie (w obu przypadkach) LUB 3 wyniki razem.

Jeśli chodzi o zastrzeżenia dotyczące segmentów segmentów, numery 3 są adresowane (i wykorzystywane). Liczba 2 nie stanowi problemu, ponieważ przecinamy tutaj prostopadłe segmenty, które nigdy nie są równoległe, jeśli nie są zdegenerowane. Liczba 1 obowiązuje tylko w przypadku dysku, gdy jeden z podanych punktów końcowych znajduje się na skonstruowanej średnicy. Gdyby punkt końcowy znajdował się dobrze wewnątrz okręgu, zajęłyby go kontrole odległości. Jeśli punkt końcowy znajduje się na okręgu, ponieważ skonstruowana średnica jest równoległa do danego segmentu, ten ostatni musi być styczny do koła, a tylko jeden punkt dotyka dysku, co nie jest prawidłowym wprowadzeniem.

Przykłady:

Domyślny przypadek: inny-inny

Oblicz odległość między środkami. Zderzenie dysku z dyskiem występuje wtedy i tylko wtedy, gdy odległość jest mniejsza niż suma promieni. Zderzenie wnęki dysku następuje wtedy i tylko wtedy, gdy odległość jest większa niż różnica promieni.

Aby zająć się przypadkiem wnęka-wnęka, zaneguj wynik kontroli odległości ORAZ z każdą z liczb całkowitych identyfikujących, a następnie LUB razem. Używając pewnej logiki, można pokazać, że ten proces zwraca wartość true wtedy i tylko wtedy, gdy obie liczby całkowite identyfikujące są fałszem (przypadek wnęki-wnęki) lub jeśli sprawdzenie odległości zwróciło wartość prawda

JavaScript - 393 bajtów

Zminimalizowane:

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

Rozszerzony:

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

Uwagi:

• definiuje funkcję, Fktóra akceptuje wymagane argumenty i zwraca wymaganą wartość
• format wejściowy jest identyczny z formatem w OP, z tym wyjątkiem, że kod liczb całkowitych dla każdej operacji podstawowej jest oddzielny od krotki. Na przykład F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )lub F( 1,[[3,0],1], 2,[[0,0],1] ).
• kod sprawdzony we wszystkich przypadkach testowych dostarczonych w PO
• powinien obsługiwać wszystkie przypadki krawędzi i narożników, w tym odcinki linii o zerowej długości i okręgi o zerowym promieniu

Python, 284

Używam dość algorytmu śmieciowego w porównaniu do wszystkich tych geometrycznych sztuczek, ale uzyskuje prawidłowe odpowiedzi, mimo że przejście przez przypadki testowe zajmuje więcej niż minutę. Dużą zaletą jest to, że muszę tylko napisać trzy funkcje oceniania, a wspinaczka górska zajmuje się wszystkimi przypadkami na krawędzi.

Gra w golfa:

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

Nie golfowany:

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

Na koniec skrypt testowy na wypadek, gdyby ktokolwiek chciał wypróbować to w Pythonie:

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)