Find the Convex Hull of a set of 2D points

Question

When you hammer a set of nails into a wooden board and wrap a rubber band around them, you get a Convex Hull.

Your mission, should you decide to accept it, is to find the Convex Hull of a given set of 2D points.

---

Some rules:

• Write it as a function, the point's list coordinates (in any format you want) is the argument
• The output must be the list of points in the convex hull listed clockwise or anticlockwise, starting at any of them
• The output list can be in any reasonable format where each point's coordinates are clearly distinguishable. (For example NOT a one dim list { 0.1, 1.3, 4, ...})
• If three or more points in a segment of the convex hull are aligned, only the two extremes should be kept on the output

Sample data:

Sample 0

Input:

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

Output:

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

(The figures are just illustrative)

Sample 1

Input:

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

Output:

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

Sample 2

Input:

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

Output:

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

Standard code-golf rules apply. No ad-hoc geometry libraries. Shorter code wins.

Edit 1

We are looking for an algorithmic answer here, not a convex hull finder pre-programmed routine like this one in MatLab or this one in Mathematica

Edit 2

Answering comments and additional info:

1. You can assume the input list contains the minimum number of points that suits you. But you must ensure proper treatment of aligned (sub)sets.
2. You may find repeated points in the input list
3. The maximum number of points should be limited only by the available memory
4. Re "floating point": You need to be able to process input lists with decimal coordinates as those given in the samples. You could do that by using a floating point representation

.

Answer 1

Ruby, 168 characters

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}

This ruby code also uses the gift wrapping algorithm. The function C accepts an array of points and returns the convex hull as array.

Example:

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

Answer 2

Mathematica 151

still work in progress

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

testing:

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

Answer 3

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

If the function needs not be accessible, remove f= to shave off two more characters.

Input/output is a single array of points, with each point being defined by the x,y properties. The input array is modified, as well as returned (if the latter not required, remove the last two characters).

Explanation may be added later.

Test suite (won't work in oldIE):

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

suggested test environment: http://coffeescript.org/

Answer 4

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

Uses a gift wrapping algorithm. The result starts with the leftmost point and wraps counter-clockwise.

Example: h([(1, 1), (2, 2), (3, 3), (1, 3)]) returns [(1, 3), (1, 1), (3, 3)]

Answer 5

C++ (gcc), 327 301 bytes

#import<bits/stdc++.h>
using V=std::complex<double>;using W=std::deque<V>;W f(W x){V m=x[0],r,c;double v=imag(m),t,g,s=1;for(V a:x)c=m=imag(a-m)>0?a:m,v=fmin(imag(a),v);W p;do{p.push_back(r=c);g=4;for(V a:x)m=c=a!=r?t=std::arg(s*(a-r)),t<g|t==M_PI?g=t,a:c:c;s=imag(m)-v?s:-1;}while(m!=p[0]);return p;}

Try it online!

Another implementation of the gift wrapping algorithm. Slightly golfed less:

#import<bits/stdc++.h>
using V=std::complex<double>;
using W=std::deque<V>;
W f(W x){
  V m=x[0],r,c;
  double v=imag(m),t,g,s=1;
  // find topmost point
  for(V a:x)
    c=m=imag(a-m)>0?a:m,
    v=fmin(imag(a),v);
  W p;
  do{
    p.push_back(r=c);
    g=4;
    // loop to find the smallest angle t
    for(V a:x)
      m=c=a!=r?
        t=std::arg(s*(a-r)),t<g|t==M_PI?
          g=t,a
        :
          c
      :
        c;
    // are we wrapping over or under?
    s=imag(m)-v?s:-1;
  // loop until we've gone all the way around
  }while(m!=p[0]);
  return p;
}