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.