Kiedy wbijesz zestaw gwoździ w drewnianą deskę i owiniesz je gumką, otrzymasz wypukły kadłub .

Twoim zadaniem, jeśli zdecydujesz się to zaakceptować, jest znalezienie Wypukłego Kadłuba danego zestawu punktów 2D.

Niektóre zasady:

• Napisz jako funkcję, argumentem są współrzędne listy punktów (w dowolnym formacie)
• Wyjściem musi być lista punktów w wypukłym kadłubie wymienionych zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara, zaczynając od dowolnego z nich
• Lista wyjściowa może mieć dowolny rozsądny format, w którym współrzędne każdego punktu są wyraźnie rozróżnialne. (Na przykład NIE lista z jednym przyciemnieniem {0,1, 1,3, 4, ...})
• Jeśli trzy lub więcej punktów w segmencie wypukłego kadłuba są wyrównane, na wyjściu należy zachować tylko dwie skrajności

Przykładowe dane:

Próbka 0

Wejście:

{{1, 1}, {2, 2}, {3, 3}, {1, 3}}

Wynik:

{{3, 3}, {1, 3}, {1, 1}}

(Liczby są tylko ilustracyjne)

Próbka 1

Wejście:

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

Wynik:

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

Próbka 2

Wejście:

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

Wynik:

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

Obowiązują standardowe zasady gry w golfa. Brak bibliotek geometrii ad-hoc. Wygrywa krótszy kod.

Edytuj 1

Szukamy tutaj odpowiedzi algorytmicznej, a nie wstępnie zaprogramowanej procedury wyszukiwania wypukłego kadłuba, takiej jak ta w MatLab lub ta w Mathematica

Edytuj 2

Odpowiadanie na komentarze i dodatkowe informacje:

1. Możesz założyć, że lista wprowadzania zawiera minimalną liczbę punktów, która Ci odpowiada. Ale musisz zapewnić właściwe traktowanie wyrównanych (pod) zestawów.
2. Powtarzające się punkty możesz znaleźć na liście wprowadzania
3. Maksymalna liczba punktów powinna być ograniczona tylko dostępną pamięcią
4. Re „zmiennoprzecinkowy”: Musisz mieć możliwość przetwarzania list wejściowych ze współrzędnymi dziesiętnymi, jak podano w próbkach. Możesz to zrobić za pomocą reprezentacji zmiennoprzecinkowej

.

Ruby, 168 znaków

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}

Ten kod ruby ​​wykorzystuje również algorytm pakowania prezentów. Funkcja Cprzyjmuje tablicę punktów i zwraca wypukły kadłub jako tablicę.

Przykład:

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

Mathematica 151

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

testowanie:

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

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

Jeśli funkcja nie musi być dostępna, usuń, f=aby zgolić jeszcze dwa znaki.

Wejście / wyjście to pojedyncza tablica punktów, przy czym każdy punkt jest definiowany przez x,ywłaściwości. Tablica wejściowa jest modyfikowana, a także zwracana (jeśli ta ostatnia nie jest wymagana, usuń dwa ostatnie znaki).

Wyjaśnienie może zostać dodane później.

Zestaw testowy (nie będzie działał w oldIE):

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

sugerowane środowisko testowe: http://coffeescript.org/

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

Wykorzystuje algorytm pakowania prezentów. Wynik zaczyna się od punktu najbardziej na lewo i jest zawijany przeciwnie do ruchu wskazówek zegara.

Przykład: h([(1, 1), (2, 2), (3, 3), (1, 3)])zwraca[(1, 3), (1, 1), (3, 3)]