Cuando martillas un juego de clavos en una tabla de madera y envuelves una banda de goma alrededor de ellos, obtienes un casco convexo .

Su misión, si decide aceptarla, es encontrar el casco convexo de un conjunto determinado de puntos 2D.

Algunas reglas:

• Escríbalo como una función, las coordenadas de la lista de puntos (en cualquier formato que desee) es el argumento
• La salida debe ser la lista de puntos en el casco convexo enumerado en sentido horario o antihorario, comenzando en cualquiera de ellos
• La lista de salida puede estar en cualquier formato razonable donde las coordenadas de cada punto sean claramente distinguibles. (Por ejemplo, NO es una lista tenue {0.1, 1.3, 4, ...})
• Si tres o más puntos en un segmento del casco convexo están alineados, solo los dos extremos deben mantenerse en la salida

Data de muestra:

Muestra 0

Entrada:

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

Salida:

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

(Las cifras son solo ilustrativas)

Muestra 1

Entrada:

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

Salida:

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

Muestra 2

Entrada:

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

Salida:

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

Aplican reglas estándar de código de golf. No hay bibliotecas de geometría ad-hoc. El código más corto gana.

Editar 1

Estamos buscando una respuesta algorítmica aquí, no una rutina preprogramada de buscador de casco convexo como esta en MatLab o esta en Mathematica

Editar 2

Responder comentarios e información adicional:

1. Puede suponer que la lista de entrada contiene el número mínimo de puntos que le conviene. Pero debe garantizar un tratamiento adecuado de los conjuntos (sub) alineados.
2. Puede encontrar puntos repetidos en la lista de entrada
3. El número máximo de puntos debe estar limitado solo por la memoria disponible
4. Re "punto flotante": debe poder procesar listas de entrada con coordenadas decimales como las que figuran en las muestras. Usted podría hacerlo mediante el uso de una representación de punto flotante

.

Ruby, 168 caracteres

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}

Este código ruby ​​también usa el algoritmo de envoltura de regalos. La función Cacepta una matriz de puntos y devuelve el casco convexo como matriz.

Ejemplo:

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

pruebas:

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

Si la función no necesita ser accesible, elimine f=para eliminar dos caracteres más.

Entrada / salida es una matriz única de puntos, con cada punto definido por las x,ypropiedades. La matriz de entrada se modifica y se devuelve (si no se requiere esta última, elimine los dos últimos caracteres).

La explicación se puede agregar más tarde.

Conjunto de pruebas (no funcionará en oldIE):

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

entorno de prueba sugerido: http://coffeescript.org/

Pitón, 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

Utiliza un algoritmo de envoltura de regalos. El resultado comienza con el punto más a la izquierda y se ajusta en sentido antihorario.

Ejemplo: h([(1, 1), (2, 2), (3, 3), (1, 3)])devoluciones[(1, 3), (1, 1), (3, 3)]