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 1
und Hohlräumen mit 2
einem 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
quelle
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]]
Antworten:
APL,
279208206203Zeilenumbrüche in der Funktion
f
dienen 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
0
für Kavität,1
Scheibe und2
Liniensegment.Großes Update
Ich habe es geschafft, viele Zeichen mit einem anderen Algorithmus zu spielen. Keine
g
Bullen mehr ** t !!Die Hauptfunktion
f
ist in Fälle unterteilt:2 2≡x
: Segment-SegmentBerechnen 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:
Beispiele: (Achtung 1 in Aktion in der Abbildung rechts beachten)
2≡2⌷x
: Segment-SonstigeIn 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
0
für die Kavität und1
fü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
quelle
Javascript - 393 Bytes
Minimiert:
Erweitert:
Anmerkungen:
F
, die die erforderlichen Argumente akzeptiert und den erforderlichen Wert zurückgibtF( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )
oderF( 1,[[3,0],1], 2,[[0,0],1] )
.quelle
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:
Ungolfed:
Und zum Schluss ein Testskript für den Fall, dass jemand anderes dies in Python ausprobieren möchte:
quelle