# Find the Convex Hull of a set of 2D points

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

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

.

• I predict that MATLAB will win this one. Commented Mar 27, 2013 at 16:41
• Can we assume that there are at least 3 points? Can we assume that the points are distinct? Are we required to support floating point coordinates? Commented Mar 27, 2013 at 17:25
• @PeterTaylor the example indicates the last answer is true Commented Mar 27, 2013 at 17:27
• May we overwrite the input? Commented Mar 27, 2013 at 17:32
• The problem with treating collinear points consistently is there are rounding issues. We should be allowed to make mistakes. Commented Mar 27, 2013 at 17:47

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


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


# 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).

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/

• I tried it with {{1, 1}, {2, 2}, {3, 3}, {1, 3}} and it returned [{"x" : 1, "y" : 1, "r" : 0}, {"x" : 1, "y" : 3, "r" : 0}, "x" : 2, "y" : 2, "r" : 0.78..}] while I think the correct answer is some permutation of {{3, 3}, {1, 3}, {1, 1}} Commented Mar 27, 2013 at 23:30
• @belisarius issue with points collinear with the first one sometimes producing incorrect hull fixed Commented Mar 28, 2013 at 0:04
• @belisarius please add this as a test case to the question. Commented Mar 28, 2013 at 0:06
• It seems to work properly now :) Commented Mar 28, 2013 at 21:20

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

• Don't you need a print to get the output? Commented Mar 29, 2013 at 0:34
• I thought by "output" you meant the output of the function. Do you want the function to print the result instead of return it? Commented Mar 29, 2013 at 1:01
• I thought that requiring the output list can be in any reasonable format was clear enough. Do you think it needs to be explicitly stated? Commented Mar 29, 2013 at 1:06
• It seems your output points doesn't always match the input ones if floating point is used. For example h([(0, 1), (0,1), (0.1 , 1)]) gives me [(0, 1), (0.10000000000000001, 1)] Commented Mar 29, 2013 at 1:47

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