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.