%% labelauto.mp
%% Version 02.01.2006
% Provides macros:
%   *) label.auto(lbl, pos);
%   *) label[25](lbl, pos);
%   *) circlabel
%   *) labelit (?)


% distance between label border and point
%labeloffset := 0.1cm;
extra_beginfig := extra_beginfig & "; init_labelauto;";


% Redefine draw command
def draw expr p =
  if (path p) :
    drawem[incr ndrawem] := p;
  elseif (picture p) :
    drawem[incr ndrawem] := tightpath p;
  else : ; fi
  addto currentpicture
  if picture p:
    also p
  else:
    doublepath p withpen currentpen
  fi
  _op_
enddef;

vardef drawlabel@# =
  draw (thelabel.auto(lab@#, @#));
enddef;

%picture getlabel[];
%getlabel[1] = btex $1$ etex;
%getlabel["A"] = btex $A$ etex;
%getlabel["B"] = btex $B$ etex;
%
%	if (@#=1): btex $1$ etex
%	elseif (@#=2): btex $2$ etex
%	else: btex $a$ etex
%	fi;
%enddef;


% filter necessery items that can intersect label
vardef calcdrawemidx (expr lbl, pos, dist) =
  save R; numeric R;
  R = xpart(lrcorner lbl - llcorner lbl) + ypart(ulcorner lbl - llcorner lbl) + dist;
  boolean add;

  %draw fullcircle scaled (2*R) shifted pos;
  ndrawemidx := 0;
  for i=1 upto ndrawem :
    add := false;
    for j=(R/2) step (R/2) until (2*R):
      if ((fullcircle scaled j shifted pos) intersectiontimes (drawem[i]) <> (-1,-1)) :
	    add := true;
	  fi
	endfor
	if (add): drawemidx[incr ndrawemidx] := i; fi
  endfor
%  show "ndrawemidx";
%  show ndrawemidx;
enddef;

%def pathdrawemidx (expr p) =
%  ndrawemidx := 0;
%  for i=1 upto ndrawem :
%    if (p intersectiontimes (drawem[i]) <> (-1,-1)) :
%		drawemidx[incr ndrawemidx] := i;
%	fi
%  endfor
%enddef;


% count lbl intersections with current picture items
def labeliscount (expr box) =
  begingroup
    save npt;
    npt := 0;
%    draw box withcolor (white - blue * 0.2);
    for i=1 upto ndrawemidx :
      if ((box intersectiontimes
               (drawem[drawemidx[i]])) = (-1,-1)) :
        ;
      else:
        npt:=npt+1;
      fi
    endfor
    npt
  endgroup
enddef;


def originaltime(expr fst, new) =
  begingroup
	if ((new >= 1) or (new <= 3)):
		ceiling(fst+0.001) + new
	elseif (new < 1):
		fst+0.001+new*(ceiling(fst+0.001)-fst-0.001)
	else:
		floor(fst+3.999)+(new-3)*(fst+3.999-floor(fst+3.999))
	fi
  endgroup
enddef;

vardef boxisdistance (expr box) =
	save tot; numeric tot;
	save times;	pair times;
	save fst,scd; numeric fst, scd;
	save fstceil,scdfloor,tmp;
	tot:=0;
	for i=1 upto ndrawemidx :
		times := box intersectiontimes (drawem[drawemidx[i]]);
		if (times <> (-1,-1)):
			fst := xpart times;
			times := (subpath(fst+0.001,fst+3.999) of box) intersectiontimes(drawem[drawemidx[i]]);
			if (times <> (-1,-1)):
				scd := originaltime(fst, xpart times);
				fstceil := ceiling fst;
				scdfloor := floor scd;
				if (scd-fst > 2):
					tmp := scd;
					scd := fst+4;
					fst := tmp;
					fstceil := ceiling fst;
					scdfloor := floor scd;
				fi
				% test how the line intersects box
				if (fstceil = scdfloor): % cuts a corner from the box
					tmp := (scd-scdfloor)*(fstceil-fst);
				elseif (fstceil+1 = scdfloor): % cuts a whole edge from the box
					tmp := (scd-scdfloor)+(fstceil-fst);
				else: % cuts only part of an edge
					%tmp := (scd-fst)*(scd-fst)/2;
				fi
				% add to total badness
				%tot := tot + min(scd-fst,4+fst-scd);
				tot := tot + tmp; % + 0*(scd-fst)/5;
			fi
		fi
	endfor
	tot
enddef;

% Total intersectiondistance of label
def labelisdistance(expr lblpath, pos, dist, ang) =
	boxisdistance(lblpath shifted
		(labelshift(lblpath , ang) + ((dist,0) rotated ang) + pos)
	)
enddef;


vardef labeldirstep (expr lblpath, pos, dist, ang) =
	save fa,fb,fc; numeric fa,fb,fc;
	save h,retang; numeric h,retang;
	h:=1;
	%show pos, dist, ang, lblpath;
	fa := labelisdistance(lblpath, pos, dist, ang-h);
	fb := labelisdistance(lblpath, pos, dist, ang);
	fc := labelisdistance(lblpath, pos, dist, ang+h);
	%show fa, fb, fc;
	if (fa+fc<>2*fb):
	%if (true):
		retang:=ang-.5*h*(fc-fa)/(fa+fc-2*fb);
		if (labelisdistance(lblpath,pos,dist,retang) < fb):
			retang
		else:
			ang
		fi
	else:
		ang
	fi	

enddef;


vardef labeldirrecurse (expr lblpath, pos, dist, ang) =
	save curdir, newdir;
	curdir = ang;
	forever:
		newdir := labeldirstep(lblpath, pos, dist, curdir);
	exitunless(newdir<>curdir);
		show (curdir, newdir);
		curdir := newdir;
	endfor
	curdir
enddef;


vardef labeldirfind (expr lblpath, pos, dist, alpha, beta) =
	save bestdir, bestdirdist; numeric bestdir, bestdirdist;
	save curdir, curdirdist; numeric curdir, curdirdist;
	bestdirdist = 4000;
	bestdir = -315;
	save tries; tries := 10 + round((beta-alpha)/5);
	save ii; ii := (beta-alpha)/tries;
%	for i=0 step 1 until 360: show (i, labelisdistance(lblpath, pos, dist, i)); endfor
	for i=alpha step ii until beta:
		%curdir := labeldirrecurse(lblpath, pos, dist, i);
		curdirdist := labelisdistance(lblpath, pos, dist, i);
		if (curdirdist < bestdirdist):
			bestdir := i;
			bestdirdist := curdirdist;
		fi
	endfor
	bestdir
enddef;

% shift box of lbl at angle ang
def labelshift (expr box, ang) =
  begingroup
% 2 varianti, ei tea kumb on parem?
%    (box shifted (-center box)) intersectionpoint ((0,0)--((1,0) scaled 1000 rotated ang))
%     point (ang/90 + 1.5) of box shifted (-center box)
% tekkis kollisioon paketiga geometrieplus
    save C; pair C; C := center(box);
    point (ang/90 + 1.5) of box shifted (-C)
  endgroup
enddef;


% seda peaks muutma, kui tahta arvesse votta tahekuju ?
def tightpath expr lbl =
  begingroup
    save box; path box;
    save oldmargin; oldmargin := bboxmargin; bboxmargin := 0;
    box := bbox lbl; bboxmargin := oldmargin;
    box
  endgroup
enddef;


def tightpathinnull expr lbl =
  (tightpath lbl) shifted (-center (tightpath lbl))
enddef;


vardef nextdirectionwithcount (expr lblpath, pos, dist, dirstart, dirdir, cntmin, cntmax) =
  save curshift; pair curshift;
  % eeldame, et dirdir = +-1
  % add on esimese poorde suurus (12.8 kraadi)
  save adddir; adddir = dirdir * 12.8;
  save curdir; curdir := dirstart;

  %show "NDWC::", cntmin, curdir;

  curshift := labelshift((lblpath) , curdir) + ((dist,0) rotated curdir) + pos;
  curcnt := labeliscount(lblpath shifted curshift);
  if ((curcnt >= cntmin) and (curcnt <= cntmax)): dirstart
  else:

  forever:
  exitunless ((curcnt < cntmin) or (curcnt > cntmax));
  exitunless (dirdir * (curdir-dirstart) < 360);
    curdir := curdir + adddir;
	%show "L1 " , curdir;
    curshift := labelshift((lblpath) , curdir) + ((dist,0) rotated curdir) + pos;
    curcnt := labeliscount(lblpath shifted curshift);
  endfor

  if (dirdir*(curdir-dirstart) >= 360) : % no direction possible
    dirstart
  else:

  forever:
    adddir := adddir/2;
  	if ((curcnt < cntmin) or (curcnt > cntmax)) :
	    curdir := curdir + adddir;
	else :
		curdir := curdir - adddir;
	fi
	%show "L2 " , curdir;
  exitunless (adddir*dirdir > 1/4);
    curshift := labelshift((lblpath) , curdir) + ((dist,0) rotated curdir) + pos;
    curcnt := labeliscount(lblpath shifted curshift);
  endfor

  forever:
    curshift := labelshift((lblpath) , curdir) + ((dist,0) rotated curdir) + pos;
    curcnt := labeliscount(lblpath shifted curshift);
  exitunless ((curcnt < cntmin) or (curcnt > cntmax));
    curdir := curdir + adddir;
	%show "L3 " , curdir;
  endfor

  %show "<<", curdir;
  curdir

  fi fi
enddef;




% find optimal direction for lblpath between angles (alpha, beta)
def labeldirection (expr lblpath, pos, dist, alpha, beta) =
  begingroup
    save curshift;
    pair curshift;
    best := -1;  % suurim tyhi vahemiku suurus
    bbb  := -360 + (alpha+beta)/2; % vahemiku keskpunkt
    aaa  := 0;  % vahemiku alguspunkt
    ccc  := alpha;  % vahemiku lopppunkt

	calcdrawemidx (lblpath, pos, dist);
	%save lblpath; path lblpath; lblpath = tightpathinnull lbl;

    forever:
	  aaa := nextdirectionwithcount(lblpath, pos, dist, ccc, 1, 0, 0);
    exitunless (aaa < beta);
	  ccc := nextdirectionwithcount(lblpath, pos, dist, aaa, 1, 1, 4000);
	exitunless (aaa <> ccc);
	  if (ccc-aaa > best) : best := ccc-aaa; bbb := (aaa+ccc-1)/2;
		%show (aaa,bbb,ccc);
	  fi
	endfor

	%i := nextdirectionwithcount(lblpath, pos, dist, bbb, -1, 1, 4000);
    %curshift := labelshift((lblpath) , i) + ((dist,0) rotated i) + pos;
    %draw lblpath shifted curshift withcolor red;

	%i := nextdirectionwithcount(lblpath, pos, dist, bbb, 1, 1, 4000);
    %curshift := labelshift((lblpath) , i) + ((dist,0) rotated i) + pos;
    %draw lblpath shifted curshift withcolor green;

	if (best <> -1):
		bbb
	else:
		if (labelisdistance(lblpath, pos, dist, bbb) = 0):
			bbb+360
		else:
			bbb
		fi
	fi
		%labeldirfind (lblpath,pos,dist,0,360)
%		if (dist > 10*labeloffset):
%			bbb
%		else:
%			labeldirection(lbl,pos,dist+0.1*labeloffset)
%		fi
%	fi

  endgroup
enddef;


def labelpositionatdistancedirection (expr lblpath, pos, dist, ang) =
    pos shifted (
      labelshift(lblpath, ang) + ((dist,0) rotated ang)
    )
enddef;


def labelpositionatdistance (expr lblpath, pos, dist, alpha, beta) =
begingroup
%	show "labposatdistance";
%    show labeldirection(tightpathinnull(lbl),pos,dist,0,360);
  labelpositionatdistancedirection (lblpath, pos, dist,
    labeldirection(lblpath,pos,dist,alpha,beta)
  )
endgroup
enddef;


vardef labelposition (expr lblpath, pos, alpha, beta) =
	save ret; pair ret;
	save i; i:=1;
	forever: %i=1 step 0.2 until 10:
		%show labeldirection(lblpath, pos, i*labeloffset, 0, 360);
		exitunless (labeldirection(lblpath, pos, i*labeloffset, 0, 360) = -180);
		%show "labelposition not ok", i;
		i := i+0.2;
	endfor
%	if (i=1):
		ret := labelpositionatdistance(lblpath, pos, i*labeloffset,alpha,beta);
		ret
%	else:
%		labelpositionatdistancedirection (lbl, pos, (max(1,i-0.0))*labeloffset,
%			labeldirection(tightpathinnull(lbl),pos, i*labeloffset)
%		)
%	fi
enddef;



numeric labeldirectionbool[];
for i=5 step 5 until 360 : labeldirectionbool[i] = i; endfor
for i=-360 step 5 until 0: labeldirectionbool[i] = 360+i; endfor
labeldirectionbool.auto=-1;
labeldirectionbool.top =-2;
labeldirectionbool.bot =-2;
labeldirectionbool.lft =-2;
labeldirectionbool.rt  =-2;
labeldirectionbool.ulft=-2;
labeldirectionbool.urt =-2;
labeldirectionbool.lrt =-2;
labeldirectionbool.llft=-2;
labeldirectionbool     =-2;

vardef thelabel@#(expr s,z) =  % Position s near z
  save p; picture p;
  if picture s:  p=s
  else:    p = s infont defaultfont scaled defaultscale
  fi;
  if (labeldirectionbool@# >= 0):
    autolabeldirection (p, z, labeldirectionbool@#)
  elseif (labeldirectionbool@# = -1) :
    autolabel (p, z, 0, 360)
  else :
    p shifted (z + labeloffset*laboff@# -
       (labxf@#*lrcorner p + labyf@#*ulcorner p
         + (1-labxf@#-labyf@#)*llcorner p
       )
    )
  fi
enddef;



def autolabel (expr lbl, pos, alpha, beta) =
  thelabel (lbl, labelposition(tightpathinnull(lbl), pos, alpha, beta))
enddef;

def autolabeldirection (expr lbl, pos, ang) =
  thelabel(lbl,labelpositionatdistancedirection(
               tightpathinnull(lbl),pos,labeloffset,ang))
enddef;


vardef circlabel@# (expr lbl, pos) =
  begingroup
    save circ;
    path circ;

    label@# (lbl, pos);

    circ = fullcircle scaled dotlabeldiam shifted pos;
    unfill circ;
    draw (circ);
  endgroup
enddef;


vardef circlabels@# (text t) =
  forsuffixes $=t:
    circlabel@# (str$,$);
  endfor
enddef;


def init_labelauto =
  path drawem[];
  picture drawempic[];
  numeric ndrawem, ndrawempic;
  numeric drawemidx[];
  numeric ndrawemidx;
  ndrawem := 0; ndrawempic := 0; ndrawemidx := 0;
enddef;


vardef labelit@# =
  begingroup
    save lbl; picture lbl;
    lbl := lab@#;

    label.auto(lbl,@#);
    draw bbox thelabel.auto(lbl, @#) withcolor 0.9*white;
  endgroup
enddef;


endinput