[metapost] glyph operator and contours order

[Dan Luecking]

At 07:06 AM 2/8/2011, Laurent Méhats wrote:
>Le 07/02/2011 21:14, Dan Luecking a écrit :
> > At 09:37 AM 2/6/2011, Laurent Méhats wrote:
> >
> >> The 'even-odd rule' wikipedia page led me to the 'point in polygon
> >> problem' and then to the 'winding number algorithm': "the winding number
> >> of a closed curve in the plane around a given point is an integer
> >> representing the total number of times that curve travels counterclockwise
> >> around the point"; if the winding number is zero then the point lies
> >> outside the curve, else it lies inside.
> >>
> >> vardef wnum (expr ccl, pnt)=
> >>   save sum;
> >>   sum:=0;
> >>   for t=1 upto length ccl:
> >>     sum:=sum+
> >>       angle((point t of ccl-pnt) rotated -angle(point t-1 of ccl-pnt));
> >>   endfor
> >>   sum/360
> >> enddef;
> >
> > This doesn't work except for polygons. The above
> > calculation only deals with the endpoints of a segment,
> > while the segment itself could go around the point on
> > either side.
>
>Indeed, I was a bit too much enthusiast ...
>
> > One modification can make it work: instead of evaluating
> > only at (point t of ccl) for integer t, step through the
> > loop with fractional step. How small a fraction? Small enough
> > so that the length of arc traveled between successive values
> > of t is less than the the distance from the path ccl to pnt.
> > This would either require a calculation to get that distance,
> > or one could vary the step size depending on the current
> > distance:
> >
> > % seg is a single Bezier segment (length=1)
> > vardef delta_theta (expr seg, pnt)=
> >   save A,B,C,D, M;
> >   A := point 0 of seg;
> >   B := postcontrol 0 of seg;
> >   C := precontrol 1 of seg;
> >   D := point 1 of seg;
>
>Let ngl stand for angle((D-pnt) rotated -angle(A-pnt)). I understand that
>ngl may be incorrect if pnt lies on D--A, and is incorrect if pnt lies
>strictly between D--A and seg: in the first case ngl would be 180 while we
>may expect -180, and in the second case we would expect ngl+360 if ngl is
>negative or ngl-360 if ngl is positive. Is that right ?

The path seg could cross the line A--D at some other point
besides A and D. This would give two regions "strictly between"
A--D and seg. In one of these ngl would be correct, in the
other incorrect.

>[Thinking aloud] The first case is easily detected, due to the value of
>ngl.

Except that the inaccuracy of angle and rotation could easily
produce a value of ngl slightly less than 180 or even slightly
"more" that 180 (meaning around -180).

>Would it be interesting to try and detect the second one ? (We may
>assume that seg has no inflexion point: if B--C intersects seg then it
>would be enough to consider seg on both sides of the intersection point.

This would introduce the well-known problems metapost has with
finding intersections.

>Thus we may assume that 'seg&(D--A)--cycle' is convex; that may help.)

If seg does cross A--D, it must have an inflection point, but
it doesn't necessarily cross _at_ the inflection point. Even
if seg doesn't cross A--D, seg&D--A&cycle could still be nonconvex,
having as many as 2 inflection points.



Daniel H. Luecking
Department of Mathematical Sciences
Fayetteville, Arkansas
http://www-cs-faculty.stanford.edu/~knuth/iaq.html