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

[Dan Luecking]

At 05:30 AM 2/3/2005, you wrote:

>Dear colleagues,
>
>Recently, I was overloaded with urgent duties, so I kept myself silent,
>nevertheless I tried to follow the thread concerning `workaround for
>turningnumber bug'. Although a lot has been said, I decided to add
>my voice.

Me too.

>    % this code works both with MF and MP
>    vardef area(expr p) = % p is a B\'ezier segment; result = \int y dx
>     save xa, xb, xc, xd, ya, yb, yc, yd;
>     (xa,20ya)=point 0 of p;
>     (xb,20yb)=postcontrol 0 of p;
>     (xc,20yc)=precontrol 1 of p;
>     (xd,20yd)=point 1 of p;
>       (xb-xa)*(10ya + 6yb + 3yc +   yd)
>      +(xc-xb)*( 4ya + 6yb + 6yc +  4yd)
>      +(xd-xc)*(  ya + 3yb + 6yc + 10yd)
>    enddef;
>
>    vardef Area(expr P) = % P is a cyclic path; result = area of the interior
>     area(subpath (0,1) of P)
>      for t=1 upto length(P)-1: + area(subpath (t,t+1) of P) endfor
>    enddef;
>
>[I'm not happy with the asymmetry of the code with respect to x and y,
>i.e., with the re-scaling of y coordinates, but it is the result of the
>narrow range of real numbers in MF/MF. Therefore, this code actually uses
>more than 3 real multiplications per node, but---I hope---one can live
>with this.]

I know it can be symmetrized, but maybe at the cost of doubling the
number of real multiplications. (Multiplications/divisions used be
considered an order of magnitude more complex than additions/subtractions
-- which may not be true any longer -- so the number was a measure of the
cost of the algorithm in computation.) I'll look into it.

>I have recollected the `area problem' because I do believe that ``integral''
>properties are more suitable for discrete geometry than ``infinitezimal''
>ones. This opinion was also presented during the discussion mentioned above,
>among others by Larry. A typical example of an infinitezimal property is
>tangency: it is impossible to distinguish *reliably* (using discrete
>geometry) tangent curves from crossing ones or laying closely.
>
>2. ``Infinitezimalness'' of turningnumber
>
>The `turningnumber' property suffers from the ``infinitezimalness'' and it
>cannot be cured.

Actually, it is both infinitessimal and integral: if f(t) is the formula
for a closed path then \int [f'(t) x f''(t)]/ abs(f'(t))^2 dt/2\pi gives
the turning number. The problem is detecting f'(t) = 0, which is the
infinitessimal part. Also detecting cusps at the endpoints since
directions don't have to match where one Bezier meets another and the
turning angles have to be added to the above integral.

>But as long as
>the angle is different from 360 degree, the ant may decide to choose
>a ``minimal'' turn.

The turning angle is plus or minus 180. You're probably thinking of
the exterior angle, which might be 0 or 360 at a cusp. A _turning angle_
of 360 leaves the ant facing the same way and will never occur.

>the same path rotated
>has sometimes turningnumber=0, sometimes =1 (differently in MP and MF;
>in MF, the reversing of the path direction after rotation may change
>the turning number).

The utility of the turning number has always escaped me. It seems solely 
designed for debugging, to catch problematic curves. MF seems to have no
problem generating "edge structures" for such paths. And Metapost will
happily attempt to fill them.


Dan


Daniel H. Luecking
Department of Mathematical Sciences
University of Arkansas