[metapost] glyph operator and contours order

[Laurent Méhats]

Le 06/02/2011 16:13, Laurent Méhats a écrit :
> Le 06/02/2011 09:22, Taco Hoekwater a écrit :
>> On 02/05/2011 04:02 PM, Laurent Méhats wrote:
>>> so my question would be: given two
>>> non intersecting nor self-intersecting cycles, is there a proper way to
>>> decide whether one lies inside the other ?
>>
>> Not easily. I vaguely recall that there was some test code
>> based on a discussion a year or so ago on the list, but I
>> cannot find it any more.
>>
>> The correct solution would be for metapost to allow non-continuous
>> paths and even/odd fill rules, then change the output of 'glyph'
>> accordingly. That extension is indeed planned, but not for the next
>> release.
> 
> Fine. I don't know these 'even/odd fill rules', thanks for the lead. I'll
> have a look to them and try to find a temporary workaround.

Ok, for the problem at hand, that is under the non-intersecting
hypothesis, it is actually enough to decide whether one point of the first
cycle lies inside the second one, or conversely.

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;

Except for precision problems, this should do the trick.

Regards,
Laurent Méhats