Convex hull: Difference between revisions

Content added Content deleted

Inline

Revision as of 21:29, 1 June 2015

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" "image/color" "image/png" "log" "os" "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:

@@ Line 70: / Line 70: @@
 	hull := pts.ConvexHull()
 	fmt.Println("Convex Hull:", hull)
-	if err := writePNG("hull.png", mkimage(pts, hull)); err != nil {
-		log.Fatal(err)
-	}
-}
-func writePNG(filename string, im image.Image) error {
-	f, err := os.Create(filename)
-	if err != nil {
-		return err
-	}
-	defer f.Close()
-	return png.Encode(f, im)
-}
-func mkimage(pts, hull points) image.Image {
-	const margin = 5
-	r := image.Rect(-margin, -margin, margin, margin)
-	for _, p := range pts {
-		r = r.Union(image.Rect(p.X-margin, p.Y-margin, p.X+margin, p.Y+margin))
-	}
-	im := image.NewRGBA(r)
-	c := color.RGBA{0, 0xff, 0, 0xff}
-	for _, p := range pts {
-		im.Set(p.X, p.Y, c)
-	}
-	c = color.RGBA{0xff, 0, 0, 0xff}
-	for _, p := range hull {
-		im.Set(p.X, p.Y, c)
-	}
-	return im
 }</lang>
 {{out}}
@@ Line 106: / Line 75: @@
 Convex Hull: [(-9,-3) (-3,-9) (19,-8) (17,5) (12,17) (5,19) (-3,15)]
 </pre>
 =={{header|J}}==