20
\$\begingroup\$

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

enter image description here

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

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

Mathematica graphics

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

Mathematica graphics

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

.

\$\endgroup\$
  • 2
    \$\begingroup\$ I predict that MATLAB will win this one. \$\endgroup\$ – Paul R Mar 27 '13 at 16:41
  • \$\begingroup\$ 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? \$\endgroup\$ – Peter Taylor Mar 27 '13 at 17:25
  • \$\begingroup\$ @PeterTaylor the example indicates the last answer is true \$\endgroup\$ – John Dvorak Mar 27 '13 at 17:27
  • \$\begingroup\$ May we overwrite the input? \$\endgroup\$ – John Dvorak Mar 27 '13 at 17:32
  • \$\begingroup\$ The problem with treating collinear points consistently is there are rounding issues. We should be allowed to make mistakes. \$\endgroup\$ – John Dvorak Mar 27 '13 at 17:47
2
\$\begingroup\$

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]]
\$\endgroup\$
2
\$\begingroup\$

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

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ 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}} \$\endgroup\$ – Dr. belisarius Mar 27 '13 at 23:30
  • \$\begingroup\$ @belisarius issue with points collinear with the first one sometimes producing incorrect hull fixed \$\endgroup\$ – John Dvorak Mar 28 '13 at 0:04
  • \$\begingroup\$ @belisarius please add this as a test case to the question. \$\endgroup\$ – John Dvorak Mar 28 '13 at 0:06
  • \$\begingroup\$ It seems to work properly now :) \$\endgroup\$ – Dr. belisarius Mar 28 '13 at 21:20
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Don't you need a print to get the output? \$\endgroup\$ – Dr. belisarius Mar 29 '13 at 0:34
  • \$\begingroup\$ I thought by "output" you meant the output of the function. Do you want the function to print the result instead of return it? \$\endgroup\$ – cardboard_box Mar 29 '13 at 1:01
  • \$\begingroup\$ 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? \$\endgroup\$ – Dr. belisarius Mar 29 '13 at 1:06
  • \$\begingroup\$ 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)] \$\endgroup\$ – Dr. belisarius Mar 29 '13 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.