Convex hull

Convex hull is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Find the points which form a convex hull from a set of arbitrary two dimensional points.

For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15).

Go

<lang go>package main

import ( "fmt" "image" "sort" )

// ConvexHull returns the set of points that define the // convex hull of p in CCW order starting from the left most. func (p points) ConvexHull() points { // From https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain // with only minor deviations. sort.Sort(p) var h points

// Lower hull for _, pt := range p { for len(h) >= 2 && !ccw(h[len(h)-2], h[len(h)-1], pt) { h = h[:len(h)-1] } h = append(h, pt) }

// Upper hull for i, t := len(p)-2, len(h)+1; i >= 0; i-- { pt := p[i] for len(h) >= t && !ccw(h[len(h)-2], h[len(h)-1], pt) { h = h[:len(h)-1] } h = append(h, pt) }

return h[:len(h)-1] }

// ccw returns true if the three points make a counter-clockwise turn func ccw(a, b, c image.Point) bool { return ((b.X - a.X) * (c.Y - a.Y)) > ((b.Y - a.Y) * (c.X - a.X)) }

type points []image.Point

func (p points) Len() int { return len(p) } func (p points) Swap(i, j int) { p[i], p[j] = p[j], p[i] } func (p points) Less(i, j int) bool { if p[i].X == p[j].X { return p[i].Y < p[i].Y } return p[i].X < p[j].X }

func main() { pts := points{ {16, 3}, {12, 17}, {0, 6}, {-4, -6}, {16, 6}, {16, -7}, {16, -3}, {17, -4}, {5, 19}, {19, -8}, {3, 16}, {12, 13}, {3, -4}, {17, 5}, {-3, 15}, {-3, -9}, {0, 11}, {-9, -3}, {-4, -2}, {12, 10}, } hull := pts.ConvexHull() fmt.Println("Convex Hull:", hull) }</lang>

Output:

Convex Hull: [(-9,-3) (-3,-9) (19,-8) (17,5) (12,17) (5,19) (-3,15)]

J

Restated from the implementation at http://kukuruku.co/hub/funcprog/introduction-to-j-programming-language-2004 which in turn is a translation of http://dr-klm.livejournal.com/42312.html

<lang J>counterclockwise =: ({. , }. /: 12 o. }. - {.) @ /:~ crossproduct =: 11"_ o. [: (* +)/ }. - {. removeinner =: #~ 1, 0 > 3 crossproduct\ ], 1: hull =: [: removeinner^:_ counterclockwise</lang>

Example use:

<lang J> hull 16j3 12j17 0j6 _4j_6 16j6 16j_7 16j_3 17j_4 5j19 19j_8 3j16 12j13 3j_4 17j5 _3j15 _3j_9 0j11 _9j_3 _4j_2 12j10 _9j_3 _3j_9 19j_8 17j5 12j17 5j19 _3j15</lang>

zkl

<lang zkl>// Use Graham Scan to sort points into a convex hull // https://en.wikipedia.org/wiki/Graham_scan, O(n log n) // http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/ // http://geomalgorithms.com/a10-_hull-1.html fcn grahamScan(points){

  N:=points.len();
  # find the point with the lowest y-coordinate, x is tie breaker
  p0:=points.reduce(fcn([(a,b)]ab,[(x,y)]xy){

if(b<y)ab else if(b==y and a<x)ab else xy });

  #sort points by polar angle with p0, ie ccw from p0
  points.sort('wrap(p1,p2){ ccw(p0,p1,p2)>0 });

  # We want points[0] to be a sentinel point that will stop the loop.
  points.insert(0,points[-1]);
  M:=1; # M will denote the number of points on the convex hull.
  foreach i in ([2..N]){
     # Find next valid point on convex hull.
     while(ccw(points[M-1], points[M], points[i])<=0){

if(M>1) M-=1; else if(i==N) break; # All points are collinear else i+=1;

     }
     points.swap(M+=1,i); # Update M and swap points[i] to the correct place.
  }
  points[0,M]

}

1. Three points are a counter-clockwise turn if ccw > 0, clockwise if
2. ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
3. gives twice the signed area of the triangle formed by p1, p2 and p3.

fcn ccw(a,b,c){ // a,b,c are points: (x,y)

  ((b[0] - a[0])*(c[1] - a[1])) - ((b[1] - a[1])*(c[0] - a[0]))

}</lang> <lang zkl>pts:=List( T(16,3), T(12,17), T(0,6), T(-4,-6), T(16,6), T(16, -7), T(16,-3),T(17,-4), T(5,19), T(19,-8), T(3,16), T(12,13), T(3,-4), T(17,5), T(-3,15), T(-3,-9), T(0,11), T(-9,-3), T(-4,-2), T(12,10), ) .apply(fcn([(x,y)]){ return(x.toFloat(),y) }).copy(); hull:=grahamScan(pts); println("Convex Hull (%d points): %s".fmt(hull.len(),hull.toString(*)));</lang>

Output:

Convex Hull (7 points): L(L(-3,-9),L(19,-8),L(17,5),L(12,17),L(5,19),L(-3,15),L(-9,-3))