Tag Archives: computation.

Filling Algorithms.

Recently,  posted interesting information about algorithms used to fill in closed paths. As my project may involve writing such algorithms I would like to write about an observation I saw on an algorithm site. It eluded me the first time I saw Nichola’s post, but after thinking about it for awhile I pieced it together. Namely, the odd-even rule may not fill all the regions[cells] with odd winding numbers only.

Odd-Even Rule: counts the number of times a ray starting from the point R crosses the boundary edges.[ We say the point R is  ‘inside’  if this number is odd and  “outside”  otherwise.]

Winding Number: counts the number of times the path winds around point R. [The point R is “outside” when wn(R)=0.]

Consider this polygon:

Ordinary polygon that is not simple. [Click to enlarge.]

On the left the two cells inside have a count of two by the Even-Odd Rule. Therefore they are “outside” and we do not fill them.  On the right  we have the same shape, but we use the winding number to color the “outside” cells. The vertices are ordered so we may follow the path unambiguously to calculate the winding number. For any R in the green cell we have wn(R)=2 —Check it! Hence, we only have one cell “outside” and the green cell gets filled.

As we can see from this example it  is not always the case the two methods will provide the same filling. If the polygon is simple —e.i. a Jordan Curve— then we are guaranteed to have the same filling. Not otherwise.

While it is true that the parity of these two rules is the same, the relationship is not isomorphic. Let R be the base of a ray to infinity on the space of our polygon. Observe the following, for the odd-even rule and the winding number respectively,

\[2n \;  \forall n \in \mathbb{N \cup{0}}  \text{ ‘outside’   equivalent  }  wn(R)=0\ \text{     ‘outside’} \]

but

\[2n  \;  \forall n \in \mathbb{N \cup{0}}  \text{ ‘outside’  not equivalent  }  wn(R)=2n \; \; \forall n \in \mathbb{N}\;  \text{    ‘inside’} \]

Our example exhibits \(n=1\), which falls on the second category.