[metapost] Re: new is_clockwise routine

[Werner LEMBERG]

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

I thought that the idea of my code is quite obvious, but apparently it
isn't.  Here's the used algorithm.

  1. Find a point P on the path which has a non-zero direction.

  2. Construct a ray of `infinite' length, starting in the vicinity of
     P which intersects the path at this point.

  3. Use `intersectiontimes' to find the intersection.  If the
     direction of the path at this point is (near) zero, or if we have
     a grazing intersection, get a new ray.

  4. Shorten the ray so that it starts right after the intersection.
     Repeat step 3 until no intersection is found.  Then go back to
     the last intersection and compare the path's direction with the
     direction of the ray.  According to the Nonzero Winding Number
     Rule we have found a clockwise oriented path if it crosses the
     ray from left to right.

This method completely avoids any problems with the geometry of Bézier
curves.  If problems arise, a different ray is tried.  Since you don't
have to analyze the whole path, compared to the old method, it should
be quite fast inspite of using the `intersectiontimes' which is a slow
MetaPost command.

> A more serious problem is determining whether the curve loops or
> changes direction between two values of 't'.

As mentioned in my last mail, I assume that the curve doesn't
intersect itself.  It's not needed for my particular problem, and it
makes life much simpler.

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

Exactly.


    Werner