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

[Daniel H. Luecking]

On Fri, 4 Feb 2005, Taco Hoekwater wrote:

> Some comments on such a future operator, though:
>  >>
> >>  vardef Area(expr P) =
>  >>  [....]
>
> To fit into the language, I propose the following syntax for the
> primitive version:
> 	<numeric> := area <path>
> or even
> 	<numeric> := area <subpath> of <path>
> Where the result is a proportial fraction of the bounding rectangle.
>
> Dan, can you take this (different presentation of the result) into
> account? The current version might output an <enormous number>, so
> restoring the symmetry is only half of the problem.

Did you mean  "area (t1,t2) of p"? (i.e., a <pair> of times rather than
a <subpath>). If so, what area would you like it to return? I see six
reasonable possibilities:
(1 - 4) The (signed) area swept out by the line from a corner of the
        bounding rectangle to a point moving along the subpath.
    (5) The (signed) area swept out by the line from point 0 of <path>.
    (6) The (signed) area swept out by the line from point t1 of <path>.

In any of these cases, one just use Jacko's algorithm with the following
small changes: First perform a shift of the path to whichever of the six
points you choose:
  save q; path q; q = p shifted - point 0 of p;
then define scalings:
  A = xpart (urcorner q - llcorner q);
  B = ypart (urcorner q - llcorner q);
and then change each of Jacko's equations to use these scalings (and q)
instead of Jacko's hard coded "20" (and p). For example for the first
one:
 (A*xa, B*ya) = point 0 of q;

By the way, for a cycle it theoretically doesn't matter what point
one measures area from. I would pick point 0 of p, myself.

While area might be useful, is it really necessary to make it a
primitive? Jacko's macro works fine by itself.

>
> I'd be happy to code and propose such an extension for the next
> 'feature' release of MP.
>
> Dan> 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.
>
> If you need to multiply/divide by an integer, try to use powers of 2.
> These allow substitution by bitshifts on machines were mul/div are
> actually harder than add/sub, and you don't have to worry about it
> any more.

The real multiplications (xb - xa)*( ... ) are the crux. One can easily
replace 10ya (for example) with 8ya + 2ya if that is significantly
faster.

> Now, back to the turningnumber :
>
> > 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.
>
> The only actual use I know of is that the "counterclockwise" macro in
> MF uses turningnumber to reverse a path explicitly (because it would
> have raised an error while coloring pixels, otherwise).

Unless you set turningcheck to 0.

I've run into turningnumber only in the karta font. The characters
were coded by giving outline paths, filling the ones with positive
turning and unfilling the reverse of the ones with negative turning
(one wishes for an eofill command here). But with judicious use of
culling (and making turningcheck 0) one can just do
  addto currentpicture contour p;
and get the same effect more efficiently in MF. When I ported karta.mf
to MP (nkarta.mp) I used the same code as the original, but my own
preference would have been not to use the turningnumber as the signal
for which operation to perform.

> I don't like the use of Area() for turningnumbers, because Area()
> assumes that the path is extremely well-behaved. Under that condition,
> it is definately easier (as Werner suggests) to calculate a sum of
> direction angles. Counting angles is also a lot faster.

I agree.

-- 
Dan Luecking
Dept. of Mathematical Sciences
University of Arkansas
Fayetteville, AR 72101