[metapost] Re: d\'ej\`a vu or turningnumber, area et caetera

[Boguslaw Jackowski]

Hello, again,

As promised, this email concerns Werner's concept of the finding of a 
path's orientation, using the conrol nodes. Werner's proposal of the 
implementation reads as follows:

  vardef Angle primary d =
   if d <> (0, 0): angle d else: 0 fi
  enddef;
  vardef turn_angle primary p =
   save res, alpha, beta, gamma;
   res := 0;
   for t = 0 upto length p -1:
     alpha := Angle (postcontrol t of p - point t of p)
              - Angle (point t of p - precontrol t of p);
     if alpha > 180: alpha := alpha - 360; fi;
     if alpha <= -180: alpha := alpha + 360; fi;
     beta := Angle (point t + 1 of p - precontrol t + 1 of p)
             - Angle (postcontrol t of p - point t of p);
     if beta > 180: beta := beta - 360; fi;
     if beta <= -180: beta := beta + 360; fi;
     res := res + alpha + beta;
   endfor;
   res
  enddef;

[Note a cosmetic change---it is not a Boolean function.]

First, the code can be modified/rewritten as follows:

  vardef turn_angle primary p =
   save res; res := 0;
   for t = 0 upto length p -1:
    res := res +
     (-Angle(postdir t of p)+Angle(postdir t+1 of p) + 180) mod 360 -180 ;
   endfor;
   res % anticlockwise is positive
  enddef;

where

  vardef postdir expr t of p = % t is expected to be integer
   (postcontrol t of p) - (point t of p)
  enddef;

This implementation however, as well as the original one, does not work with
and important group of paths, namely, with broken lines having control nodes
coinciding with the basic nodes. For example, the
turn_angle(p)=turn_angle(reverse p)=0 for

  p:=(0,0) .. controls (0,0) and (1,1) ..
     (1,1) .. controls (1,0) and (0,1) ..
     (0,1) .. controls (0,1) and (0,0) .. (0,0) & cycle;

The original Werner's `is_clockwise' function returns `true'. Paths of this
kind frequently occur in fonts -- it is commonly accepted to use them
as straight lines. [Incidentally, the MF/MP operator `---' yields almost
such paths.]

The problem of such paths can be easily solved. Let a, b, c, d denote the
nodes of the B\'ezier segment a .. controls b and c .. d.

A more general definition of `postdir' (and, for completeness, `predir'),
given below, is based on the following observation, being the consequence of
the de l'H\^ospital's rule: normally the vector a-->b determines the ``post''
direction at node a; if b coincides with a, then the vector a-->c determines
the direction; if c also coincides coincides with a, then the last resort is
vector c-->d; if d also coincides with a, the B\'ezier segment is
degenerated, and can be removed.

vardef postdir expr t of p = % t is expected to be integer
  save a,b,c,d,s; pair a,b,c,d; path s;
  s:=subpath (t,t+1) of p;
  a=point 0 of s;
  b=postcontrol 0 of s;
  c=precontrol 1 of s;
  d=point 1 of s;
  if a<>b:     b-a
  elseif a<>c: c-a
  elseif a<>d: d-a
  else:       (0,0)
  fi
enddef;

vardef predir expr t of p = % t is expected to be integer
  save a,b,c,d,s; pair a,b,c,d; path s;
  s:=subpath (t-1,t) of p;
  a=point 0 of s;
  b=postcontrol 0 of s;
  c=precontrol 1 of s;
  d=point 1 of s;
  if d<>c:     d-c
  elseif d<>b: d-b
  elseif d<>a: d-a
  else:       (0,0)
  fi
enddef;

[Perhaps a constant factor should be taken into account in the
implementation above, but from the point of view of the determining
of angles, it is unimportant.]

Now, `turn_ang' works quite efficiently (speed-up is some 30% in
comparison with Werner's `is_clockwise') and yields ``reasonable''
results for ``reasonable'' paths. It fails for paths with cusps,
loops, and with segments turning by the angle >=180. Note that
cusps and large turning angles are indifferent for the `Area' function.

Cheers -- Jacko

Ps. Note that the `direction' operator, defined in MP/MF as follows:

       vardef direction expr t of p =
        postcontrol t of p - precontrol t of p enddef;

     can be improved using the functions `predir' and `postdir'
     defined above:

       vardef gendir expr t of p =
        if round(t)=t:
         predir t of p + postdir t of p
        else:
         gendir 1 of
           ((subpath (floor t, t) of p) & (subpath (t, ceiling t) of p))
        fi
       enddef;

-- 
BOP s. c.
ul. Bora-Komorowskiego 24, 80-377 Gdansk, Poland
tel. (+48 58) 553 46 59,  fax (+48 58) 511 03 81
bop at bop.com.pl, http://www.bop.com.pl