[metapost] Re: new is_clockwise routine

[Daniel H. Luecking]

On Wed, 30 Nov 2005, Giuseppe Bilotta wrote:

> Wednesday, November 30, 2005 Dan Luecking wrote:
>
> > Giuseppe: What you called a knot is what I would call a loop.
> > But what is the "knot factor"?  If that just the discriminant
> > of g'xg''?
>
> I obtain it as the only possibly-negative factor of the
> discriminant of the second-degree equation that gives the
> time value for the cusp or the time values where the loop
> crosses itself (the other factor is a sqaure, so it's always
> non-negative). Apart from a constant numerical factor, it's
> equal to
>
> 4 (P1 - P0) × (P2 - P1) (P2 - P1) × (P3 - P2) -
>   ((P1 - P0) × (P3 - P2))^2

OK. Lets call this 4ac-b^2. The quadratic g'xg'' is (a positive constant
times)
  q(t) = a(1-t)^2 + b(1-t)t + ct^2

If we divide this by t^2 and set u=(1-t)/t we get
  p(u) = au^2 + bu + c.
Then 0 < t < 1 corresponds to u > 0. The above expression is the
discriminant of p and of course helps determines its roots. These
determine the roots of q (except a root of q at 0 corresponds to a=0).

I'm sure Giuseppe knows the following but I will provide the details
for the rest:

We are mainly concerned with changes in curvature for g in 0 < t < 1,
which corresponds to roots of q in 0 < t < 1 and so with positive roots
of p.  Descarte's Rule of Signs can be applied and that gives us the
criteria you posted.

Descartes Rule is that the number of positive roots of p is the number
of changes in sign in the list a, b, c (0's are skipped), or is less
than that by an even number.

If a and b have opposite signs, there must be exactly one change in sign
and so exactly one positive root and so one change in curvature for g.

If they have the same sign, there might be no changes of sign (no
positive roots) or two changes (2 or 0 positive roots). In this last
case there can be no negative roots, (p(-u) has no changes of sign and
p(0) = c \ne 0) so the existence of positive roots is determined by the
existence of any roots, and that is determined by b^2 - 4ac: negative
means no roots, positive means 2 roots, 0 means a double root.

MF coding by cases:
vardef sign primary X =
  if X > 0    :  1
  elseif X < 0: -1
  else        :  0
  fi
enddef

message "q(t) has " &
if (a=0) and (c=0):
  "no roots"
elseif (a=0) or (c=0): % exactly one of a and c is 0
  if (sign b = sign a) or (sign b = sign c):
    "no roots"
  else:
    "one root"
  fi
elseif (sign a)*(sign c) < 0: % a,c nonzero, different signs
  "one root"
else: % a,c nonzero with same sign
  if sign b = sign a: % no sign changes
    "no roots"
  else: % 2 sign changes, examine discriminant
    if b**2 < 4a*c0:
      "no roots"
    elseif b**2 = 4a*c:
      "a double root" % a cusp
    else:
      "two roots"
    fi
  fi
fi & " in (0,1)";

As one needs only needs inequalities, one could (conditionally) scale a,
b, and c so that b**2 and 4a*c are within range. This can affect
precision if done in macros.

Taco: is this good enough for coding?

I might point out that, MF gets a turningnumber with less problem than
MP. If memory serves, MF determines whether g'(t) moves from one octant
to another (within a Bezier segment this amounts to detecting changes in
sign of a numeric quadratic function of t).

g'(t) is allowed to pass through (0,0). If it does so at a smooth point,
it will immediately return to the same octant, but at a cusp it will
change by 180 degrees: 4 octants (or 4 - epsilon).

At a corner where two Beziers meet there might be a discontinuous jump
in g' to a different octant. If the change is less than 4 octants, the
turning angle is well defined. There is then be a closer examination of
the remaining case, which I have not looked at.

Still, I don't see why it (or a modification) couldn't be used in
MetaPost.


Dan

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