User:Devon McCormick/convexHull

Brief description of the concept of a convex hull and some code for finding one for a given set of points.

What is a Convex Hull?

Here is a description of a convex hull. Intuitively, it is an efficient border around a set of points where, by efficient, we mean that it in some sense minimizes the area enclosed. Here is an online Java application that may help develop an intuitive feel for the meaning of this concept.

What Use is a Convex Hull?

This article in Dr. Dobbs provides a good introduction to convex hulls and mentions a few uses such as

• Collision detection in video games
• Visual pattern matching and object discrimination
• Mapping
• Path determination

Additionally, the feasible set of points for the solution of a linear programming problem is always convex. In fact, the optimal solution to such a problem can be found among the extreme points of such a set (provided that the set is bounded). This is the basis of the simplex algortithm.

How Might we Find a Convex Hull in J?

Here's some code submitted to the J Forum by Lars Strand <Lars.Strand@skogoglandskap.no> and to which I added a visualization function. He offers the following explanation of the algorithm used.

from Lars Strand <Lars.Strand@skogoglandskap.no>  Jan 11 (2 days ago)
reply-to Programming forum <programming@jsoftware.com>	
to	 programming@jsoftware.com	
date	 Jan 11, 2008 6:55 AM	
subject	 [Jprogramming] manuscript	

Constructing a convex hull in J.

A number of points are given. The problem is to determine the smallest,
convex region which includes all of the points. The solution starts with
the point (0) having the smallest x-value. The next point (1) will be
the point which together with the first point defines a line having
the smallest angle to the x-axis. Using this point as vertex, the task
is to find a third point (2) so that a line from the vertex has the
largest angle to the line 0-1. 3 points in the solution are now
determined.

The procedure is repeated after a shift of  (1) to (0), (2) to (1), and
a new point (2) found in the same way. The procedure stops when the new
point (2) is the same as the starting point. The solution contains the
point numbers of the hull.

His code for this, lightly edited, follows.

compl=: 3 : 0                 NB. First = last
   nopts=: #y
   list=: i.#y
   startpt=: 0{sort y         NB. start
   startno=: y i.startpt
   red=: y-startpt
   angels=: 1{"1 *.red
   mina=: <./angels

   pt0=: startno
   pt1=: angels i. mina
   alt=: pt0,.pt1,.(i.nopts)-.pt0,pt1
   ina=: y angle3 "1 alt
   maxa=: >./ina
   pt2=: 2{(ina i. maxa){alt
   solution=: pt0,pt1,pt2     NB. The first 3

   while. (-. pt2= startno) do.
      pt0=: pt1
      pt1=: pt2
      alt=: pt0,.pt1,.(i.nopts)-.pt0,pt1
      ina=: y angle3 "1 alt
      maxa=: >./ina
      pt2=: {:(ina i. maxa){alt
      solution=: solution,pt2
   end.
)

angle3=: 4 : 0
   'p0 p1 p2'=: y
   v=: 1{"1 *.x-p1{x
   v1=: p0{v
   if. v1<0 do.v1=: (o.2) + v1 end.
   v2=: p2{v
   if. v2<0 do.v2=: (o.2) + v2 end.
   diff=: |v1-v2
   if. diff>o.1 do. (o.2)-diff end.
)

To see a set of points in blue and trace the convex hull in red using this code, use the following code:

   load 'plot'
showSolution=: 3 : 0
   pd 'show' [ pd y [ pd 'type point;pensize 5'
   pd 'pensize 2' [ pd 'color RED'
   pd 'show' [ pd y{~compl y [ pd 'type line'
)

For example, enter this

   showSolution pts=. j./?2 20$10

to find and graph the solution for 20 randomly-generated points. You should see something like this:

As written, this code does not generalize beyond two dimensions.

Further Considerations

Henry Rich had this advice to offer for building an efficient algorithm:

Any convex-hull implementation should start out with the following step:

Pick any 4 points that you think are toward the outside of the point set (min/max x/y are good candidates).

Discard any points that are inside the quadrilateral defined by these points.

This is quick and for large sets can greatly reduce the number of points that the detailed calculation needs to handle.