Even–odd Rule

The even–odd rule is an algorithm implemented in vector-based graphic software, 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 graphics vector standard may be configured to use the even–odd rule when drawing polygons, though it uses the non-zero rule by default.

Implementation

Below is an example implementation in Python:

def is_point_in_path(x: int, y: int, poly) -> bool:
# Determine if the point is in the polygon.
#
# 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

num = len(poly)
j = num - 1
c = False
for i in range(num):
if (x

poly 0]) and (y

poly 1]):
# point is a corner
return True
if ((poly 1] > y) != (poly 1] > y)):
slope = (x-poly 0])*(poly 1]-poly 1])-(poly 0]-poly 0])*(y-poly 1])
if slope

0:
# point is on boundary
return True
if (slope < 0) != (poly 1] < poly 1]):
c = not c
j = i
return c

See also

*Nonzero-rule
*Jordan curve theorem
*Complex polygon
*Tessellation
*Polygon triangulation
*TrueType

References

External links

Definition of fill rules in SVG

Computer graphics algorithms
Parity (mathematics)

{{compu-prog-stub