The even–odd rule is an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 implemented in vector-based graphic software, like the PostScript

PostScript

PostScript is a dynamically typed concatenative programming language created by John Warnock and Charles Geschke in 1982. It is best known for its use as a page description language in the electronic and desktop publishing areas. Adobe PostScript 3 is also the worldwide printing and imaging...

 language, which determines how a graphical shape with more than one closed outline will be filled. Opposite: nonzero-rule

Nonzero-rule

In two-dimensional computer graphics, the non-zero winding rule is a means of determining whether a given point falls within an enclosed curve. Unlike the similar even-odd rule, it relies on knowing the direction of stroke for each part of the curve....

.

The SVG specification says: "This rule determines the "insideness" of a point on the canvas by drawing a ray from that point to infinity in any direction and counting the number of path segments from the given shape that the ray crosses. If this number is odd, the point is inside; if even, the point is outside."

The rule can be seen in effect in many vector graphic programs (like Freehand or Illustrator

Illustrator

An Illustrator is a narrative artist who specializes in enhancing writing by providing a visual representation that corresponds to the content of the associated text...

), where a crossing of an outline with itself causes shapes to fill in strange ways.

On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon

Point in polygon

In computational geometry, the point-in-polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon...

problem.

Implementation in insight toolkit (ITK)

bool
IsInside( const PointType & point, const PolygonType & polygon) const
{
int numpoints = polygon->NumberOfPoints;
int X=0;
int Y=1;
if(numpoints < 3)
{
return false;
}
 
const PointListType & points = polygon->GetPoints;
typename PointListType::const_iterator it = points.begin;
typename PointListType::const_iterator itend = points.end;
itend--;
 
PointType first = (*it).GetPosition;
PointType last = (*itend).GetPosition;
 
// If last point same as first, don't bother with it.
if( polygon->IsClosed )
{
numpoints--;
}
 
bool oddNodes = false;
 
PointType node1;
PointType node2;
 
for(int i = 0; i < numpoints; i++)
{
node1 = (*it).GetPosition;
it++;
if(i numpoints - 1)
{
node2 = first;
}
else
{
node2 = (*it).GetPosition;
}
 
const double x = point[X];
const double y = point[Y];
 
if((node1[Y] < y && node2[Y] >= y) ||
(node2[Y] < y && node1[Y] >= y))
{
if( node1[X] + (y – node1[Y])/
(node2[Y] – node1[Y]) * (node2[X] – node1[X]) < x )
{
oddNodes = !oddNodes;
}
}
}
 
return oddNodes;
}
External links

• Definition of fill rules in SVG