cdeck homr11 subroutine homr11 (n,x,m,in,ia,ib,ih,nh,il) c this subroutine determines which of the m points of array c x whose subscripts are in array in are vertices of the c minimum area convex polygon containing the m points. the c subscripts of the vertices are placed in array ih in the c order they are found. nh is the number of elements in c array ih and array il. array il is a linked list giving c the order of the elements of array ih in a counter c clockwise direction. this algorithm corresponds to a c preorder traversal of a certain binary tree. each vertex c of the binary tree represents a subset of the m points. c at each step the subset of points corresponding to the c current vertex of the tree is partitioned by a line c joining two vertices of the convex polygon. the left son c vertex in the binary tree represents the subset of points c above the partitioning line and the right son vertex, the c subset below the line. the leaves of the tree represent c either null subsets or subsets inside a triangle whose c vertices coincide with vertices of the convex polygon. c formal parameters c input c n integer total number of data points c x real array (2,n) (x,y) co-ordinates of the data c m integer number of points in input subset c in integer array (m) subscripts for array x of the c points in the input subset c work area c ia integer array (m) subscripts for array x of left son c subsets. see comments after dimension c statements. c ib integer array (m) subscripts for array x of right son c subsets. c output c ih integer array (m) subscripts for array x of the c vertices of the homr11 hull c nh integer number of elements in array ih and c array il. same as number of vertices c of the convex polygon. c il integer array (m) a linked list giving in order in a c counter-clockwise direction the c elements of array ih dimension x(3,n) dimension in(m), ia(m), ib(m), ih(m), il(m) c the upper end of array ia is used to store temporarily c the sizes of the subsets which correspond to right son c vertices, while traversing down the left sons when on the c left half of the tree, and to store the sizes of the left c sons while traversing the rigt sons(down the right half) logical maxe, mine if (m.eq.1) go to 220 il(1)=2 il(2)=1 kn=in(1) kx=in(2) if (m.eq.2) go to 210 mp1=m+1 min=1 mx=1 kx=in(1) maxe=.false. mine=.false. c find two vertices of the homr11 hull for the initial c partition do 60 i=2,m j=in(i) if (x(1,j)-x(1,kx)) 30,10,20 10 maxe=.true. go to 30 20 maxe=.false. mx=i kx=j 30 if (x(1,j)-x(1,kn)) 50,40,60 40 mine=.true. go to 60 50 mine=.false. min=i kn=j 60 continue c if the max and min are equal, all m points lie on a c vertical line if (kx.eq.kn) go to 180 c if maxe (or mine) has the value true there are several c maxima (or minima) with equal first coordinates if (maxe.or.mine) go to 230 70 ih(1)=kx ih(2)=kn nh=3 inh=1 nib=1 ma=m in(mx)=in(m) in(m)=kx mm=m-2 if (min.eq.m) min=mx in(min)=in(m-1) in(m-1)=kn c begin by partitioning the root of the tree call homr12 (n,x,mm,in,ih(1),ih(2),0,ia,mb,mxa,ib,ia(ma),mxbb) c first traverse the left half of the tree c start with the left son 80 nib=nib+ia(ma) ma=ma-1 90 if (mxa.eq.0) go to 110 il(nh)=il(inh) il(inh)=nh ih(nh)=ia(mxa) ia(mxa)=ia(mb) mb=mb-1 nh=nh+1 if (mb.eq.0) go to 100 ilinh=il(inh) call homr12 (n,x,mb,ia,ih(inh),ih(ilinh),1,ia,mbb,mxa,ib(nib),ia 1 (ma),mxb) mb=mbb go to 80 c then the right son 100 inh=il(inh) 110 inh=il(inh) ma=ma+1 nib=nib-ia(ma) if (ma.ge.m) go to 120 if (ia(ma).eq.0) go to 110 ilinh=il(inh) c on the left side of the tree, the right son of a right son c must represent a subset of points which is inside a c triangle with vertices which are also vertices of the c convex polygon and hence the subset may be neglected. call homr12 (n,x,ia(ma),ib(nib),ih(inh),ih(ilinh),2,ia,mb,mxa,ib 1 (nib),mbb,mxb) ia(ma)=mbb go to 90 c now traverse the right half of the tree 120 mxb=mxbb ma=m mb=ia(ma) nia=1 ia(ma)=0 c start with the right son 130 nia=nia+ia(ma) ma=ma-1 140 if (mxb.eq.0) go to 160 il(nh)=il(inh) il(inh)=nh ih(nh)=ib(mxb) ib(mxb)=ib(mb) mb=mb-1 nh=nh+1 if (mb.eq.0) go to 150 ilinh=il(inh) call homr12 (n,x,mb,ib(nib),ih(inh),ih(ilinh),-1,ia(nia),ia(ma) 1 ,mxa,ib(nib),mbb,mxb) mb=mbb go to 130 c then the left son 150 inh=il(inh) 160 inh=il(inh) ma=ma+1 nia=nia-ia(ma) if (ma.eq.mp1) go to 170 if (ia(ma).eq.0) go to 160 ilinh=il(inh) c on the right side of the tree, the left son of a left son c must represent a subset of points which is inside a c triangle with vertices which are also vertices of the c convex polygon and hence the subset may be neglected. call homr12 (n,x,ia(ma),ia(nia),ih(inh),ih(ilinh),-2,ia(nia),mbb 1 ,mxa,ib(nib),mb,mxb) go to 140 170 nh=nh-1 return c all the special cases are handled down here c if all the points lie on a vertical line 180 kx=in(1) kn=in(1) do 200 i=1,m j=in(i) if (x(2,j).le.x(2,kx)) go to 190 mx=i kx=j 190 if (x(2,j).ge.x(2,kn)) go to 200 min=i kn=j 200 continue if (kx.eq.kn) go to 220 c if there are only two points 210 ih(1)=kx ih(2)=kn nh=3 if ((x(1,kn).eq.x(1,kx)).and.(x(2,kn).eq.x(2,kx))) nh=2 go to 170 c if there is only one point 220 nh=2 ih(1)=in(1) il(1)=1 go to 170 c multiple extremes are handled here c if there are several points with the (same) largest c first coordinate 230 if (.not.maxe) go to 250 do 240 i=1,m j=in(i) if (x(1,j).ne.x(1,kx)) go to 240 if (x(2,j).le.x(2,kx)) go to 240 mx=i kx=j 240 continue c if there are several points with the (same) smallest c first coordinate 250 if (.not.mine) go to 70 do 260 i=1,m j=in(i) if (x(1,j).ne.x(1,kn)) go to 260 if (x(2,j).ge.x(2,kn)) go to 260 min=i kn=j 260 continue go to 70 end