2D-Kollisionserkennung

21

Diese Herausforderung basiert auf der Kollisionserkennung, die ich kürzlich für ein einfaches Spiel schreiben musste.

Schreiben Sie ein Programm oder eine Funktion, die bei zwei Objekten je nachdem, ob die beiden Objekte kollidieren (dh sich kreuzen) oder nicht , einen wahren oder falschen Wert zurückgibt .

Sie müssen drei Arten von Objekten unterstützen:

  • Liniensegmente : durch 4 Gleitkommazahlen dargestellt, die die beiden Endpunkte angeben, dh (x 1 , y 1 ) und (x 2 , y 2 ) . Sie können davon ausgehen, dass die Endpunkte nicht identisch sind (das Liniensegment ist also nicht entartet).
  • Scheiben : dh gefüllte Kreise, dargestellt durch 3 Floats, zwei für den Mittelpunkt (x, y) und einen (positiv) für den Radius r .
  • Hohlräume : Dies sind die Ergänzung einer Scheibe. Das heißt, ein Hohlraum füllt den gesamten 2D-Raum mit Ausnahme eines kreisförmigen Bereichs, der durch einen Mittelpunkt und einen Radius festgelegt ist.

Ihr Programm oder Ihre Funktion erhält zwei solche Objekte in Form einer identifizierenden Ganzzahl (Ihrer Wahl) und ihre 3 oder 4 Gleitkommazahlen. Sie können Eingaben über STDIN, ARGV oder Funktionsargument vornehmen. Sie können die Eingabe in einer beliebigen, nicht vorverarbeiteten Form darstellen, z. B. 8 bis 10 einzelne Zahlen, zwei durch Kommas getrennte Wertelisten oder zwei Listen. Das Ergebnis kann zurückgegeben oder an STDOUT geschrieben werden.

Sie können davon ausgehen, dass die Objekte mindestens 10 -10 Längeneinheiten voneinander entfernt sind oder sich um so viel überschneiden, sodass Sie sich nicht um die Einschränkungen von Gleitkommatypen kümmern müssen.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Testfälle

Bei der Darstellung von Liniensegmenten mit 0, Discs mit 1und Hohlräumen mit 2einem listenbasierten Eingabeformat sollten alle folgenden Elemente eine wahrheitsgemäße Ausgabe liefern:

[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

Das Folgende sollte jedoch zu einer fehlerhaften Ausgabe führen

[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
Martin Ender
quelle
Schwieriger als ich zuerst dachte. Ausgehend von der Zeile / Zeilenfall stoße ich auf eine überraschende Anzahl von Randfällen. Könnten Sie nicht kollineare Segmente verbieten? Würde die Sache viel einfacher machen. ;)
Emil
@Emil Tut mir leid, aber 9 Stunden nach dem Posten muss ich davon ausgehen, dass andere möglicherweise damit begonnen haben, an der Herausforderung zu arbeiten, und eine Änderung der Spezifikation (abgesehen von der Behebung von Problemen mit dem Brechen) scheint mir keine gute Idee zu sein. Abhängig davon, wie Sie es tun, sollten parallele Liniensegmente der einzige Randfall sein, über den Sie sich Gedanken machen müssen, wenn es um Linienkollisionen geht.
Martin Ender
Klar, ich hatte nicht wirklich damit gerechnet, dass du es änderst. Ich war nur ein bisschen frustriert darüber, dass sich die Länge meines Codes durch die verschiedenen Varianten von kollinearen Liniensegmenten verdoppelt hat. :) (Übrigens eine große Herausforderung!)
Emil
Fallen kollineare Punkte nicht unter "Kollidiert nicht um 10 ^ -10"?
TwiNight
@TwiNight Nicht, wenn die beiden Linien kollinear sind, sich aber nicht überlappen. ZB[0,[-2,0],[-1,0]], [0,[1,0],[2,0]]
Martin Ender

Antworten:

6

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}

Zeilenumbrüche in der Funktion fdienen der Übersichtlichkeit. Sie sollten durch das Anweisungstrennzeichen ersetzt werden

Es ist so lange her, dass ich zuletzt ein so komplexes APL-Programm erstellt habe. Ich glaube, das letzte Mal war das, aber ich bin mir nicht sicher, ob das so komplex war.

Eingabeformat
Grundsätzlich identisch mit dem OP, außer bei Verwendung 0für Kavität, 1Scheibe und 2Liniensegment.

Großes Update

Ich habe es geschafft, viele Zeichen mit einem anderen Algorithmus zu spielen. Keine gBullen mehr ** t !!

Die Hauptfunktion fist in Fälle unterteilt:


2 2≡x: Segment-Segment

Berechnen Sie in diesem Fall den Vektor aus den Endpunkten jeder Linie und lösen Sie ein lineares Gleichungssystem, um zu überprüfen, ob der Schnittpunkt in den Vektoren enthalten ist.

Vorsichtsmaßnahmen:

  • Der Endpunkt eines Vektors wird nicht als Teil des Vektors betrachtet (während sein Ursprung ist). Befindet sich jedoch nur die Spitze eines Vektors auf dem anderen, ist die Eingabe gemäß Spezifikation ungültig.
  • Nicht entartete parallele Segmente geben unabhängig von der Kollinearität immer false zurück.
  • Wenn eines der Segmente entartet ist, geben Sie immer false zurück. Wenn beide Segmente entartet sind, geben Sie immer true zurück.

Beispiele: (Achtung 1 in Aktion in der Abbildung rechts beachten)


2≡2⌷x: Segment-Sonstige

In diesem Fall ist das andere Objekt ein kreisförmiges Objekt. Überprüfen Sie mithilfe der Abstandsüberprüfung, ob die Endpunkte des Segments innerhalb des Kreises liegen.

Konstruieren Sie im Disc-Fall auch ein Liniensegment mit dem Durchmesser senkrecht zum angegebenen Segment. Überprüfen Sie, ob die Segmente durch Rekursion kollidieren.
Schleichen Sie sich in dem Hohlraum-Fall in die Konstruktion des Segments "mal 0" ein, um es entartet zu machen. (Sehen Sie, warum ich jetzt 0für die Kavität und 1für die Scheibe verwende?) Da das angegebene Segment nicht entartet ist, gibt die Segment-Segment-Kollisionserkennung immer false zurück.

Kombinieren Sie abschließend die Ergebnisse der Distanzprüfung und der Kollisionserkennung. Negieren Sie für den Hohlraumfall zuerst die Ergebnisse der Abstandsüberprüfungen. Dann ergibt sich (in beiden Fällen) ODER die 3 zusammen.

In Bezug auf die Segment-Segment-Einschränkungen wird Nummer 3 angesprochen (und ausgenutzt). Nummer 2 ist kein Problem, da wir hier senkrechte Segmente schneiden, die niemals parallel sind, wenn sie nicht entartet sind. Nummer 1 wird nur im Scheibenkasten wirksam, wenn einer der angegebenen Endpunkte auf dem konstruierten Durchmesser liegt. Wenn der Endpunkt gut innerhalb des Kreises liegt, hätten sich die Abstandsprüfungen darum gekümmert. Wenn der Endpunkt auf dem Kreis liegt, darf der Kreis nur mit einem Punkt tangential zum Kreis liegen, da der konstruierte Durchmesser parallel zum angegebenen Segment ist. Dies ist keine gültige Eingabe.

Beispiele:


Standardfall: Andere-Andere

Berechnen Sie den Abstand zwischen den Mitten. Eine Disc-Disc-Kollision tritt genau dann auf, wenn der Abstand kleiner als die Summe der Radien ist. Eine Kollision zwischen Scheibenkavität tritt genau dann auf, wenn der Abstand größer ist als die Differenz der Radien.

Um sich um den Hohlraum-Hohlraum-Fall zu kümmern, negieren Sie das Ergebnis der Entfernungsprüfung UND mit jeder der identifizierenden ganzen Zahlen und ODER sie dann zusammen. Mit einer Logik kann gezeigt werden, dass dieser Prozess nur dann true zurückgibt, wenn beide identifizierenden Ganzzahlen falsch sind (Cavity-Cavity-Fall) oder wenn die Entfernungsprüfung true zurückgegeben wurde

TwiNight
quelle
Meines Erachtens muss die Byteanzahl die 2-Byte-pro-Zeichen-Natur von Unicode berücksichtigen, wenn Ihr Programm mit Zeichen geschrieben wird, die sich über Unicode statt über ASCII erstrecken.
COTO
@COTO Ich habe kein Unicode angegeben. Soweit mir bekannt ist, passt der APL-Zeichensatz in ein Byte, und es gibt Einzelbyte-Codepages, die alle APL-Zeichen enthalten. Wenn Sie diese Codierung verwenden, ist die Byteanzahl in Ordnung. Die Zählung nach Bytes ist hauptsächlich für Personen relevant, die Inhalte in Mehrbyte-Zeichenfolgen in "normalen" Sprachen codieren oder die Unicode-Verknüpfungen von Mathematica verwenden.
Martin Ender
@ MartinBüttner: Sie sagen also, dass niemand die 1-Byte-pro-Zeichen-Version des Strings in einem Texteditor - abgesehen von einer explizit für APL entwickelten - sinnvoll oder praktisch darstellen kann, sie zählt jedoch als 1-Byte-pro-Zeichen weil die Sprachspezifikation 256 oder weniger zulässige Zeichen enthält?
COTO
@COTO Gut und weil Codierungen existieren, nach denen eine Single-Byte-codierte Datei interpretiert werden könnte. Ich glaube nicht, dass ich bereit wäre, diesen Weg zu gehen, wenn die Leute ihre Kodierung erfinden müssten. Andernfalls könnte jedes Programm, das weniger als 257 verschiedene Zeichen verwendet, dies behaupten (was meiner Meinung nach fast jede Antwort auf PPCG wäre). Ich denke nur, wir sollten APL nicht dafür bestrafen, dass es mehrere Jahrzehnte älter ist als Unicoding. Damals war es sinnvoll, die Bytes, die Sie hatten, als seltsame, funky Zeichen zu interpretieren, die als Mnemonics funktionieren.
Martin Ender
1
@COTO Es gibt J, das auf APL basiert und nur ASCII-Zeichen verwendet. Sie erzielen in der Regel ähnliche Ergebnisse, sodass Sie wahrscheinlich auch von Unicode übertroffen werden. Und ich sollte hinzufügen, dass keine der beiden Sprachen für das Golfen entwickelt wurde und AFAIK beide tatsächlich professionell eingesetzt werden. Und bei den Golfherausforderungen geht es hier nicht so sehr darum, das grüne Häkchen zu setzen, sondern vielmehr darum, jedes noch so kleine Byte mit den Mitteln Ihrer Sprache aus Ihrem Programm zu entfernen und alle in derselben "Gewichtsklasse" zu schlagen, was Ihnen normalerweise mehr Stimmen einbringt als ohnehin eine knappe Sprache zu verwenden. ;)
Martin Ender
5

Javascript - 393 Bytes

Minimiert:

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

Erweitert:

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

Anmerkungen:

  • Definiert eine Funktion F, die die erforderlichen Argumente akzeptiert und den erforderlichen Wert zurückgibt
  • Das Eingabeformat ist mit dem Format im OP identisch, mit der Ausnahme, dass der ganzzahlige Typcode für jedes Grundelement vom Tupel getrennt ist. Zum Beispiel F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )oder F( 1,[[3,0],1], 2,[[0,0],1] ).
  • Code validiert für alle im OP gelieferten Testfälle
  • sollte alle Kanten- und Eckfälle behandeln, einschließlich Liniensegmente mit der Länge Null und Kreise mit dem Radius Null
COTO
quelle
Ah, danke, dass Sie diese beiden Randfälle erwähnt haben. Kreise mit Nullradius müssen nicht behandelt werden (der Pfosten gibt einen positiven Radius an), und ich werde auch klarstellen, dass die Enden des Liniensegments unterschiedlich sind.
Martin Ender
4

Python, 284

Im Vergleich zu all diesen geometrischen Tricks verwende ich einen hübschen Garbage-Algorithmus, der jedoch die richtigen Antworten liefert, obwohl es über eine Minute dauert, bis die Testfälle abgeschlossen sind. Der große Vorteil ist, dass ich nur die drei Bewertungsfunktionen schreiben muss und das Bergsteigen sich um alle Randfälle kümmert.

Golf gespielt:

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

Und zum Schluss ein Testskript für den Fall, dass jemand anderes dies in Python ausprobieren möchte:

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)
QuadmasterXLII
quelle