Finden Sie die konvexe Hülle einer Reihe von 2D-Punkten

20

Wenn Sie einen Satz Nägel in ein Holzbrett hämmern und ein Gummiband um sie wickeln, erhalten Sie einen konvexen Rumpf .

Bildbeschreibung hier eingeben

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

Mathematica-Grafiken (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}}

Mathematica-Grafiken

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

Mathematica-Grafiken

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:

  1. 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.
  2. Möglicherweise finden Sie wiederholte Punkte in der Eingabeliste
  3. Die maximale Anzahl von Punkten sollte nur durch den verfügbaren Speicher begrenzt werden
  4. 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

.

Dr. belisarius
quelle
2
Ich gehe davon aus, dass MATLAB diesen Titel gewinnen wird.
Paul R
Können wir davon ausgehen, dass es mindestens 3 Punkte gibt? Können wir annehmen, dass die Punkte unterschiedlich sind? Müssen wir Gleitkommakoordinaten unterstützen?
Peter Taylor
@ Peter Taylor das Beispiel zeigt an, dass die letzte Antwort wahr ist
John Dvorak
Dürfen wir die Eingabe überschreiben?
John Dvorak
Das Problem bei der konsistenten Behandlung von kollinearen Punkten besteht in Rundungsproblemen. Wir sollten Fehler machen dürfen.
John Dvorak

Antworten:

2

Ruby, 168 Zeichen

C=->q{r=[]
f=m=q.sort[0]
t=-0.5
(_,_,t,*f=q.map{|x,y|a=x-f[0]
b=y-f[1]
[0==(d=a*a+b*b)?9:(-t+e=Math.atan2(b,a)/Math::PI)%2,-d,e,x,y]}.sort[0]
r<<=f)while
!r[1]||f!=m
r}

Dieser Ruby-Code verwendet auch den Geschenkverpackungsalgorithmus. Die Funktion Cakzeptiert ein Array von Punkten und gibt die konvexe Hülle als Array zurück.

Beispiel:

>p C[[[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]]]

[[5.3, 2.4], [11, 1.1], [12.9, 3.1], [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]]
Howard
quelle
2

Mathematica 151

noch in arbeit

f = For[t = Sort@#; n = 1; l = Pi; a = ArcTan; c@1 = t[[1]],
       n < 2 || c@n != c@1, 
       n++,
      (l = a @@ (# - c@n); c[n + 1] = #) & @@
      t[[Ordering[Mod[a@## - l, 2 Pi] & @@ (#2 - #1) & @@@ Tuples@{{c@n}, t}, 1]]]] &

testen:

ClearAll[a, c, t];
s = {{1, 0}, {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}};
f@s
Show[Graphics@Line@Table[c@i, {i, n}], 
     ListPlot[{t, Table[c@i, {i, n}]}, 
     PlotStyle -> {PointSize[Medium], PointSize[Large]}, 
     PlotRange -> All]]

Bildbeschreibung hier eingeben

Dr. belisarius
quelle
1

CoffeeScript, 276:

f=($)->z=$[0];e.r=Math.atan2(e.x-z.x,e.y-z.y)for e in $;$.sort((x,y)->(x.r>y.r)-(x.r<y.r));(loop(a=$[i-1]||$[$.length-1];b=$[i];c=$[i+1]||$[0];break if!b;s=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);break if s<0||!s&&(a.x-b.x)*(b.x-c.x)<0;$.splice i,1))for i in [$.length-1..0];$

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,yEigenschaften 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):

alert JSON.stringify f({x:e[0], y:e[1]} for e in JSON.parse "
{{1, 1}, {2, 2}, ...}
".replace(/{/g,"[").replace(/}/g,"]"))

Vorgeschlagene Testumgebung: http://coffeescript.org/

John Dvorak
quelle
Ich habe es mit probiert {{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}}
Dr. belisarius
@belisarius Problem mit Punkten kollinear mit dem ersten manchmal produzieren falschen Rumpf behoben
John Dvorak
@belisarius bitte füge dies als Testfall der Frage hinzu.
John Dvorak
Es scheint jetzt richtig zu funktionieren :)
Dr. Belisarius
1

Python, 209 205 195

from math import*
s=lambda(a,b),(c,d):atan2(d-b,c-a)
def h(l):
 r,t,p=[],pi/2,min(l)
 while 1:
    q=min(set(l)-{p},key=lambda q:(s(p,q)-t)%(2*pi));m=s(p,q);r+=[p]*(m!=t);p=q;t=m
    if p in r:return r

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

Pappschachtel
quelle
Benötigen Sie nicht eine print, um die Ausgabe zu erhalten?
Dr. Belisarius
Ich dachte mit "Ausgabe" meinst du die Ausgabe der Funktion. Möchten Sie, dass die Funktion das Ergebnis druckt, anstatt es zurückzugeben?
cardboard_box
Ich dachte, dass das Anfordern the output list can be in any reasonable formatklar genug war. Meinen Sie, es muss explizit angegeben werden?
Dr. Belisarius
Es scheint, dass Ihre Ausgabepunkte nicht immer mit den Eingabepunkten übereinstimmen, wenn Gleitkommazahlen verwendet werden. Zum Beispiel h([(0, 1), (0,1), (0.1 , 1)])gibt mir[(0, 1), (0.10000000000000001, 1)]
Dr. Belisarius