Wenn Sie einen Satz Nägel in ein Holzbrett hämmern und ein Gummiband um sie wickeln, erhalten Sie einen konvexen Rumpf .
Ihre Mission ist es, den konvexen Rumpf eines gegebenen Satzes von 2D-Punkten zu finden, falls Sie sich dafür entscheiden, dies zu akzeptieren .
Einige Regeln:
- Schreiben Sie es als Funktion. Die Listenkoordinaten des Punktes (in jedem gewünschten Format) sind das Argument
- Die Ausgabe muss die Liste der Punkte in der konvexen Hülle sein, die im Uhrzeigersinn oder gegen den Uhrzeigersinn aufgeführt sind und bei jedem von ihnen beginnen
- Die Ausgabeliste kann in jedem vernünftigen Format vorliegen, bei dem die Koordinaten der einzelnen Punkte klar voneinander unterschieden werden können. (Zum Beispiel KEINE One-Dim-Liste {0.1, 1.3, 4, ...})
- Wenn drei oder mehr Punkte in einem Segment der konvexen Hülle ausgerichtet sind, sollten nur die beiden Extreme auf dem Ausgang beibehalten werden
Beispieldaten:
Probe 0
Eingang:
{{1, 1}, {2, 2}, {3, 3}, {1, 3}}
Ausgabe:
{{3, 3}, {1, 3}, {1, 1}}
(Die Zahlen sind nur zur Veranschaulichung)
Probe 1
Eingang:
{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {2.1, 11.1}, {9.5, 14.9},
{13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, {5.3, 2.4},
{8.45, 4.7}, {11.5, 9.6}, {13.8, 7.3}, {12.9, 3.1}, {11, 1.1}}
Ausgabe:
{{13.8, 7.3}, {13.2, 11.9}, {9.5, 14.9}, {6.7, 15.25}, {4.4, 14},
{2.1, 11.1}, {0.6, 5.1}, {5.3, 2.4}, {11, 1.1}, {12.9, 3.1}}
Probe 2
Eingang:
{{1, 0}, {1, 1}, {1, -1}, {0.68957, 0.283647}, {0.909487, 0.644276},
{0.0361877, 0.803816}, {0.583004, 0.91555}, {-0.748169, 0.210483},
{-0.553528, -0.967036}, {0.316709, -0.153861}, {-0.79267, 0.585945},
{-0.700164, -0.750994}, {0.452273, -0.604434}, {-0.79134, -0.249902},
{-0.594918, -0.397574}, {-0.547371, -0.434041}, {0.958132, -0.499614},
{0.039941, 0.0990732}, {-0.891471, -0.464943}, {0.513187, -0.457062},
{-0.930053, 0.60341}, {0.656995, 0.854205}}
Ausgabe:
{{1, -1}, {1, 1}, {0.583004, 0.91555}, {0.0361877, 0.803816},
{-0.930053, 0.60341}, {-0.891471, -0.464943}, {-0.700164, -0.750994},
{-0.553528, -0.967036}}
Es gelten die Standardregeln für Code-Golf. Keine Ad-hoc-Geometriebibliotheken. Kürzere Code gewinnt.
Bearbeiten 1
Wir suchen hier nach einer algorithmischen Antwort, nicht nach einer vorprogrammierten Routine für die Suche nach konvexen Hüllen wie dieser in MatLab oder dieser in Mathematica
Bearbeiten 2
Beantwortung von Kommentaren und zusätzlichen Informationen:
- Sie können davon ausgehen, dass die Eingabeliste die Mindestanzahl von Punkten enthält, die zu Ihnen passt. Sie müssen jedoch eine ordnungsgemäße Behandlung der ausgerichteten (Teil-) Mengen sicherstellen.
- Möglicherweise finden Sie wiederholte Punkte in der Eingabeliste
- Die maximale Anzahl von Punkten sollte nur durch den verfügbaren Speicher begrenzt werden
- Zu "Gleitkomma": Sie müssen in der Lage sein, Eingabelisten mit Dezimalkoordinaten zu verarbeiten, die in den Beispielen angegeben sind. Sie können dies mithilfe einer Gleitkommadarstellung tun
.
Antworten:
Ruby, 168 Zeichen
Dieser Ruby-Code verwendet auch den Geschenkverpackungsalgorithmus. Die Funktion
C
akzeptiert ein Array von Punkten und gibt die konvexe Hülle als Array zurück.Beispiel:
quelle
Mathematica 151
noch in arbeittesten:
quelle
CoffeeScript, 276:
Wenn die Funktion nicht verfügbar sein muss, entfernen Sie
f=
, um zwei weitere Zeichen zu entfernen .Eingabe / Ausgabe ist ein einzelnes Array von Punkten, wobei jeder Punkt durch die
x,y
Eigenschaften definiert wird . Das Eingabearray wird geändert und zurückgegeben (wenn letzteres nicht erforderlich ist, entfernen Sie die letzten beiden Zeichen).Erklärung kann später hinzugefügt werden.
Testsuite (funktioniert in oldIE nicht):
Vorgeschlagene Testumgebung: http://coffeescript.org/
quelle
{{1, 1}, {2, 2}, {3, 3}, {1, 3}}
und es ist zurückgekehrt,[{"x" : 1, "y" : 1, "r" : 0}, {"x" : 1, "y" : 3, "r" : 0}, "x" : 2, "y" : 2, "r" : 0.78..}]
während ich denke, die richtige Antwort ist eine Permutation von{{3, 3}, {1, 3}, {1, 1}}
Python,
209 205195Verwendet einen Geschenkverpackungsalgorithmus. Das Ergebnis beginnt mit dem Punkt ganz links und wird gegen den Uhrzeigersinn umgebrochen.
Beispiel:
h([(1, 1), (2, 2), (3, 3), (1, 3)])
kehrt zurück[(1, 3), (1, 1), (3, 3)]
quelle
print
, um die Ausgabe zu erhalten?the output list can be in any reasonable format
klar genug war. Meinen Sie, es muss explizit angegeben werden?h([(0, 1), (0,1), (0.1 , 1)])
gibt mir[(0, 1), (0.10000000000000001, 1)]