Das Zählen der Anzahl von Dreiecken in einem Bild ist eine Aufgabe, die häufig bei Gehirntests verwendet wird. Sie erhalten ein Bild, das Formen enthält, die aus Dreiecken bestehen. Sie müssen dann alle möglichen Dreiecke im Bild finden.
Aufgabe
Sie erhalten eine Liste von Zeilen in einem Format Ihrer Wahl. Sie müssen dann eine Liste der darin gefundenen Dreiecke ausgeben
Eingang
Sie erhalten eine Liste von Zeilen, die jeweils durch vier ganzzahlige Koordinaten (z. B. x1 y1 x2 y2
) angegeben sind. Sie können das Eingabeformat wählen, sofern es klar dokumentiert ist. Beispiele:
0 4 8 1
0 4 9 5
8 1 9 5
2 8 0 4
9 5 2 8
[[0, 4, 8, 1], [0, 4, 9, 5], [8, 1, 9, 5], [2, 8, 0, 4], [9, 5, 2, 8]]
Hier ist die gleiche Eingabe wie bei einem Bild:
Eine andere mit Kreuzungen (nur in einem Format, um Platz zu sparen):
[[2, 1, 5, 0], [2, 1, 2, 7], [5, 0, 6, 6], [5, 0, 2, 7], [6, 6, 2, 1], [2, 7, 6, 6]]
Ausgabe
Sie müssen eine Liste aller Dreiecke ausgeben, die jeweils durch sechs Gleitkommakoordinaten (z. B. x1 y1 x2 y2 x3 y3
) in dem durch die Eingabe angegebenen Bild angegeben sind. Dies sind möglicherweise keine ganzen Zahlen, da sich die Linien an jedem Punkt kreuzen können. Sie können das Ausgabeformat auswählen, sofern es eindeutig dokumentiert ist. Beispielausgaben für die obigen Beispieleingaben:
0 4 8 1 9 5
0 4 9 5 2 8
[[0, 4, 8, 3, 9, 5], [0, 4, 9, 5, 2, 8]]
[[2, 1, 5, 0, 2, 7], [2, 1, 5, 0, 6, 6], [5, 0, 6, 6, 2, 7], [2, 1, 6, 6, 2, 7], [2, 1, 5, 0, 3.674, 3.093], [5, 0, 6, 6, 3.674, 3.093], [6, 6, 2, 7, 3.674, 3.093], [2, 7, 2, 1, 3.674, 3.093]]
Sie können das annehmen
Es gibt keine Randfälle, in denen eine Linie einen Schnittpunkt kreuzt, aber keine Linien wie
[[0, 9, 1, 8], [1, 8, 2, 9], [2, 9, 3, 8], [3, 8, 4, 9], [4, 9, 0, 9]]
Es gibt keine Winkel über 179 Grad
[[0, 0, 0, 1], [0, 1, 0, 2], [0, 2, 0, 0]]
Regeln
- Sie können jede gewünschte Sprache verwenden.
- Es dürfen keine externen Ressourcen verwendet werden.
- Es gelten Standardlücken .
Wertung
Dies ist Code-Golf , daher gewinnt die kürzeste Antwort in Bytes .
[0,9],[1,8],[2,9],[3,8],[4,9]
tatsächlich ein W mit einer Linie, die über die Oberseite gezogen wird. Ist das kein Dreieck oder 2 Dreiecke?[0,0],[1,0],[2,0],[1,2]
ein "Viereck" mit einem Winkel von 180 Grad. Keine Dreiecke oder 1 Dreieck?Antworten:
PostGIS, 162
Ich denke, dies entspricht den Regeln. Es ist eine Abfrage für PostGIS, eine Erweiterung von PostgreSQL. Es wird angenommen, dass die Eingabe eine Koordinatentabelle für jede Zeile mit der Bezeichnung L ist. Die Ausgabe ist eine Reihe von Zeilen mit der Polygondefinition für die gebildeten Dreiecke.
Im Gebrauch sieht es wie folgt aus
Die Ausgabe ist wie folgt
quelle
Mathematica
915 395 401405Aktualisieren
Diese Programmierherausforderung ist viel schwieriger als es zunächst scheint.
Der vorliegende Ansatz funktioniert mit einfachen Fällen, in denen es nur einen einzigen Schnittpunkt entlang der Länge eines Liniensegments gibt. Bei mehreren Kreuzungen entlang eines Segments ist es erforderlich, alle Schnittpunkte entlang jeder Linie zu verfolgen und neue Untersegmente (daher zusätzliche Diagrammkanten) zu erstellen, die den neuen Schnittpunkt mit allen Schnittpunkten entlang der Ziellinie verbinden.
Trotz dieser Einschränkung kann es sinnvoll sein, die dem aktuellen Ansatz zugrunde liegende Logik zu teilen.
Die Eingabezeilensegmente werden als Regionen behandelt. Wenn sie sich schneiden, ist der Schwerpunkt die Koordinate der Kreuzung. Wir müssen die Schnittpunkte beseitigen, die an den Eckpunkten von Liniensegmenten auftreten. Linien, die sich nicht schneiden, haben einen unbestimmten Schwerpunkt.
Für jeden Schnittpunkt werden vier neue Kanten erstellt. Sie verbinden den Schnittpunkt mit den vier Eckpunkten der beiden Schnittlinien.
Ein Diagramm wie das unten rechts wird mit den alten und neuen Kanten erstellt.
Die Eckpunkte sind die Koordinaten der jeweiligen Punkte. Zyklen, dh geschlossene Schleifen von drei Eckpunkten, sind Dreiecke, vorausgesetzt, die drei Eckpunkte sind nicht kollinear.
Gegenwärtig prüfen wir, ob ein "Dreieck" eine unbestimmte Fläche hat. (Aus irgendeinem Grund wird für drei kollineare Punkte kein Bereich von 0 zurückgegeben.)
Ein einfaches Beispiel
Unten sind (a) die in der Koordinatenebene aufgetragene Figur und (b) der Graph, der die gegebenen Knoten sowie den Schnittpunktknoten zeigt ,
{114/23, 314/69}
. In letzterem befinden sich die Eckpunkte nicht an den jeweiligen kartesischen Koordinaten.Es scheint, dass es in der rechten Abbildung mehr Kanten gibt als in der linken. Denken Sie jedoch daran, dass sich links überlappende Grafikkanten befinden. Jede Diagonale entspricht tatsächlich 3 Grafikkanten!
Jede Zeile darunter ist ein Dreieck.
Ein komplexeres Beispiel
Hier ist das Diagramm, das den Eingabekoordinaten entspricht . Die Eckpunkte liegen an ihren erwarteten kartesischen Koordinaten. (Wenn Sie den Golfcode ausführen, werden die Scheitelpunkte an anderer Stelle angezeigt, wobei die Scheitelpunktbeschriftungen und -kanten berücksichtigt werden. Zur besseren Lesbarkeit habe ich die Scheitelpunktkoordinaten mit ein wenig zusätzlichem Code zugewiesen, der für die Lösung nicht erforderlich ist.)
Hier ist das abgeleitete Diagramm.
Es enthält den abgeleiteten Schnittpunkt
(0,1/11)
, an dem sich einige der Eingangslinien kreuzen.Der Code fand 19 Dreiecke. Neun von ihnen haben den Punkt
(0,1/11)
als einen der Eckpunkte.quelle
Java,
10511004(Voll funktionsfähiges Programm)
Ich dachte, dies ist eine schöne Herausforderung, nicht nur Code zu spielen, sondern vor allem das Schreiben mathematischer Funktionen zu üben.
Und um eine "Grundlinie" zu zeichnen, habe ich diese in Java erstellt. * Wartet darauf, dass alle anfangen zu lachen * .
Code
Eingang
Durch Leerzeichen getrennte Ganzzahlen. In 4er-Paaren (x1, y1, x2, y2)
Ausgabe (reale Ausgabe rundet nicht auf 3 Dezimalstellen)
Jede Linie enthält ein Dreieck. Jede Linie besteht aus durch Leerzeichen getrennten Gleitkommawerten in Zweierpaaren (x1, y1, x2, y2, x3, y3). (Hinweis: Die Reihenfolge der 3 Punkte, die das Dreieck bilden, ist undefiniert.)
Erläuterung
Ich begann eine Methode zu schreiben, um den Schnittpunkt zwischen zwei nicht unendlichen Linien zu finden. Die resultierende Methode ist für einen Java-Stil ziemlich kurz (246). Anstatt die Methodeneingabe aus 8 Doppel- oder zwei Punkten (P) bestehen zu lassen, verwende ich einen beliebigen Parameter, um große Mengen an Zeichen zu sichern. Um die Verwendung des Array-Operators zu minimieren, wird jeder Parameter, der mehr als zweimal verwendet wird, in eine eigene Variable eingefügt.
Weitere Erklärung hinzugefügt werden ... (diese Antwort kann wahrscheinlich noch mehr Golf gespielt werden)
quelle
BBC BASIC
Emulator unter http://www.bbcbasic.co.uk/bbcwin/bbcwin.html
Ich erwarte, dass dies bis in die 400er Jahre hinein Golf spielen wird.
Input-Output
Jedes Mal, wenn der Benutzer eine neue Zeile eingibt, prüft das Programm, ob neue Dreiecke erstellt wurden, und gibt diese sofort aus (siehe unten).
Ein neues Dreieck wird überall dort erstellt, wo sich die neue Linie mit zwei bereits vorhandenen Linien schneidet, die sich ebenfalls gegenseitig schneiden (außer wenn sich alle drei Linien an einem Punkt schneiden, was ein Sonderfall ist, der behandelt werden muss).
Code
Das Hauptprogramm ist so einfach wie möglich. Am Ende steht die Funktion, die die komplexe Aufgabe des Erkennens von Schnittpunkten gemäß der Formel in http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection ausführt
Die Funktion gibt Null zurück, wenn kein Schnittpunkt vorhanden ist, und eine Gleitkommazahl ungleich Null, falls vorhanden. Es hat auch einen Nebeneffekt: Die Koordinaten des Schnittpunkts werden an die Zeichenfolge z $ angehängt. Darüber hinaus sind in BBC Basic die Variablen einer Funktion für das Hauptprogramm sichtbar, vorausgesetzt, das Hauptprogramm verfügt nicht über eine gleichnamige Variable (auch nach Beendigung der Funktion).
Daher hat das Hauptprogramm Zugriff auf die Variablen
x
undy
undm
undn
, die die Koordinaten der aktuellen und vorherigen Schnittpunkte speichern. Dies wird verwendet, um festzustellen, ob wir wirklich ein Dreieck gefunden haben und nicht nur drei Linien, die sich an einem Punkt schneiden.quelle