[metapost] Re: new is_clockwise routine

[Giuseppe Bilotta]

Saturday, November 26, 2005 Laurence Finston wrote:

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

I don't understand why a curve looping is a problem. If a
curve loops, it's still turning the same way, so if it's
clockwise it remains clockwise. Also, if the curve has an
inflection then it most surely can't be clockwise (or
counterclockwise).

At most, the problems arise when the curve has a cusp
since, in this case both sides have the same direction (I'm
talking about a single Bézier cubic with a cusp, not cusps
generated by joining two cubics) even though the curve as a
whole doesn't turn the same way all around.

Finding the direction at which a curve turns at any given
point is easy: just find the sign of the cross product

g'×g''

which is also the sign of the curvature. (I'm talking about
planar curves here, since in 3D it doesn't make sense at all
to talk about clockwise vs counterclockwise, so a×b = a_x
b_y - a_y b_x): if the cross product is positive, the curve
turns counterclockwise, if it's negative it turns clockwise.
Except of course at knots, but in this case g' = 0.

Inflection points are given by g'×g'' = 0, which is a second
degree equation for Bézier cubics.

In general, to find the clockwiseness of a single Bézier
cubics it suffices to check for the sign of

(P1 - P0) × (P2 - P1)

and

(P2 - P1) × (P3 - P2)

(P0, P1, P2, P3 are the points that define the curve: P0 ..
controls P1 and P2 .. P3)

If they are both positive, the curve is counter clockwise. If they
are both negative, the curve is clockwise, if they have
opposite sign the curve changes direction somewhere
inbetween (which can be found as mentioned above).

There are only two cases when this check fails: when the
cubic has a cusp between the two extrema, or when the curve
has TWO inflections.

However, both this cases only happen when the two director
segments P0 -> P1 and P2 -> P3 cross, which is quite
straightforward to check. If this happens, the curve has
either two inflection points or a cusp or a knot. If any of
this cases is to be considered invalid, then the curve can
be discarded as not being either clockwise or
counterclockwise. If knots (loops) are acceptable, it is
possible to tell the three cases apart by checking for the
knot factor (however, I'm afraid this check may overflow
METAPOST, so other methods may be more appropriate: checking
for solutions of g'=0 in [0,1] (in which case we have a
cusp) and checking the curvature sign at t = .5, then at t =
1/4 and 3/4, etc).

I have problems following METAPOST code, though, so someone
else will have to check if Werner's code does this, and in
case write a more complete test.

For paths formed by more than one cubic, just run the check
for every cubic, ensuring that there is no direction change
at any of the nodes.

-- 
Giuseppe "Oblomov" Bilotta