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 rectangle 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. Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Lars Strand > Sent: Friday, January 11, 2008 6:56 AM > To: [email protected] > 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. > > > > The script > > xvalues =: 9.8 5.8 2.2 5.5 5.5 5.8 4.0 6.9 3.4 4.6 7.6 3.0 > > yvalues =: 4.7 2.9 3.2 0.5 7.3 5.0 0.5 4.6 4.0 8.4 7.9 6.1 > > kompl =: xvalues j. yvalues > > > > 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 else. v1 end. > > v2=: p2{v > > if.v2<0 do.v2=:(o.2) + v2 else. v2 end. > > diff=:|v1-v2 > > if. diff>o.1 do. (o.2)-diff end. > > ) > > > > > > > > > > ---------------------------------------------------------------------- > For information about J forums see > http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
