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

[Boguslaw Jackowski]

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. Sorry for somewhat lengthy email, but after a few days of
silence, you understand... ;-)

1. Recollections.

I must say that I have a feeling of d\'ej\`a vu...

Almost all topics discussed in this thread were considered some 5 years
ago on the METAFONT discussion list. Already then, Larry proposed using
winding number instead of turning number, and using area as an alternative.
Larry and Dan came up with a nice formula for calculating the area of a
B\'ezier curve requiring 3 real multiplications per node (plus 2). Being
delighted with their concepts, I proposed the following implementation:

    % 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;

    % little tests:
    show Area(reverse fullcircle scaled 200);
    show Area(unitsquare rotated 45 scaled 10);

    end.

[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 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.

In order to explain this, let me introduce the following naive model: imagine
a 0-dimensional ant walking along the curve. The ant does not see the
surrounding area, only the curve, but it has an infinitezimal compass, so it
understands the notion of direction. As long as the curve is smooth,
everything is clear. The trouble appears at corners: strictly speaking, there
is no direction there! So, the ant may turn either through its left or
through its right shoulder (provided an ant has a shoulder). But as long as
the angle is different from 360 degree, the ant may decide to choose
a ``minimal'' turn. The real problem appears with paths like the following:

   path p; p=(0,0)--(0,100)--(100,100){left}..{down} (0,0) & cycle;

[Note, that cusps of this kind cannot be easily dismissed from practical
applications.] The turning number of this path is actually undefined! There
is no method to define the turning angle at cusps (t=0, t=2) locally, i.e.,
without observing the area around. The turning angle can be 360 as well as
-360 -- the poor ant has no basis to choose between positive and negative
value. Only if it could observe the surrounding region of the cusps and could
tell where is the interior of the curve, it would have enough information
to turn ``properly''.

Actually, this path exhibits strange behaviour in MP as well as in MP:
both `p' and `reverse p' have the turningnumber=1; 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).

This cannot be helped.

Therefore, agreeing with Larry, I'd propose, at the moment, the using
of the macro Area (or its more efficient variant) for checking the
orientation of a path. The important drawback of this approach is
that the paths with turningnumber 0 (``8-shaped'', with selfintersections)
cannot be easily identified.

3. Totalweight and culling.

In order to handle also selfintersections (without finding all
intersection points which, as we know, is difficult) one should
have the function corresponding to the `cull' primitive in METAFONT.
It is a powerful operation on bitmaps that enables to drop areas
with pixels having specified weight, e.g., negative pixels.

The following (simplistic) MF code might be use to identify whether
we deal with an 8-shaped curve (`cullit' is a MF macro that drops
negative pixels):

   % given path p
   interim turningcheck:=0; interim autorounding:=0; % technicalities
   %
   currentpicture:=nullpicture;
   fill p; cullit; w1:=totalweight currentpicture;
   %
   currentpicture:=nullpicture;
   fill reverse p; cullit; w2:=totalweight currentpicture;
   %
   show w1, w2;
   if w1/(w1+w2)<eps: message "negative";
   elseif w2/(w1+w2)<eps: message "positive";
   else: message "zero";
   fi
   end.

Note that this code cannot be easily re-implemented in METAPOST.
As was mentioned, one would have to find selfintersection points.
And this was the problem that triggered the whole avalanche
of problems recently discussed here.

Cheers -- Jacko

-- 
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