[metapost] Re: new is_clockwise routine

[Laurence Finston]

Thu Nov 24 17:12:27 CET 2005 
Werner LEMBERG wl at gnu.org wrote:

> Below I present a completely different solution which should > > work for
all curves which don't have a self-intersection.  

> Please comment.  [...]

I've given your problem some thought.  I haven't gotten very far with
parametric curves in my own work.  I'm currently occupied with the conic
sections and quadrics.  However, the following is what I plan on trying first,
if and when I get to this point.  You may be way ahead of me on this subject,
so I hope you don't find my ideas hopelessly naive.  I must also mention that
I haven't read your macros, since they look complicated, and I don't usually
read other people's code, except under duress.

I wouldn't use direction or tension at all, since they're only used for
finding the intermediate control points.  Once you've got them, you don't
direction or tension anymore.  The representation of a Bezier curve with
control points can be transformed in a straightforward way to a polynomial. 
In the case of MetaPost, it will be a cubic.   It will be rather ugly, but in
a form that's easy for a computer to handle.  In addition, this procedure is
well-documented, for example, in Huw Jones' and David Solomon's books.  Full
references are available here:
http://www.gnu.org/software/3dldf/manual/user_ref/3DLDF/Bibliography.html#Bibl
iography

Once you do this, you will have a 3rd degree polynomial in, say, 't'.
The definition of Bezier curves of order 'n' ensures that 'n - 1' derivatives
can be taken for all values of 't'.  I'm not sure exactly what information the
derivatives will give me, but I'm pretty sure they will tell me the speed,
direction, acceleration, and possibly the curvature of the original cubic, or,
to be precise, the set of connected cubics.  It seems to me that comparing the
direction of the original curve for different values of 't', where 't_x - t_{x
- 1} = delta t' is a suitably small value, would be a good test for
clockwise-ness or counter-clockwise-ness.  (There must be a better term for
these characteristics.)  If taking derivatives gives me the curvature, this
might even make for a better test.

However, I see a couple of problems with this approach.  First of all, Bezier
curves, unlike more general spline curves, don't use weights or knots, and
they aren't projectively invariant.  On the one hand, it makes the problem
easier to solve, but on the other hand, the solution as proposed can't be
generalized to 3D (or higher dimensions).  However, "dummy" weights and knots
could be used.  The polynomials for NURBs (which would be required in
practice) are even uglier than the ones for Bezier curves, but can also be
found in a straightforward manner.

A more serious problem is determining whether the curve loops or changes
direction between two values of 't'.  Perhaps a clever mathematician could
figure out a way of doing this.  If not, I believe that choosing an
appropriately small value for 'delta t' would suffice.

I'm not sure whether it would be possible to implement this using macros.  I
think it would probably be better to do so within the source code of MF/MP
itself.  However, unless one knows it already, learning it well enough to be
able to modify it must be quite an undertaking.  

Laurence Finston