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
