The even–odd rule is an algorithm implemented in vector-based graphic software,[1] like the PostScript language and Scalable Vector Graphics (SVG), which determines how a graphical shape with more than one closed outline will be filled. Unlike the nonzero-rule algorithm, this algorithm will alternatively color and leave uncolored shapes defined by nested closed paths irrespective of their winding.
The SVG defines the even–odd rule by saying:
The rule can be seen in effect in many vector graphic programs (such as Freehand or Illustrator), 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 problem.
The SVG computer vector graphics standard may be configured to use the even–odd rule when drawing polygons, though it uses the non-zero rule by default.[2]
Below is a partial example implementation in Python,[3] by using a ray to the right of the point being checked:
Args: x -- The x coordinates of point. y -- The y coordinates of point. poly -- a list of tuples [(x, y), (x, y), ...]
Returns: True if the point is in the path or is a corner or on the boundary""" c = False for i in range(len(poly)): ax, ay = poly[i] bx, by = poly[i - 1] if (x
ay): # point is a corner return True if (ay > y) != (by > y): slope = (x - ax) * (by - ay) - (bx - ax) * (y - ay) if slope