Even–odd rule-Cedar Herald Index

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:

Even–odd rule

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.

Even–odd rule

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

Even–odd rule

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 a partial example implementation in Python: def is_point_in_path(x: int, y: int, poly) -> bool: # Determine if the point is on the path, corner, or boundary of 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[i][0]) and (y == poly[i][1]): # point is a corner return True if ((poly[i][1] > y) != (poly[j][1] > y)): slope = (x-poly[i][0])*(poly[j][1]-poly[i][1])-(poly[j][0]-poly[i][0])*(y-poly[i][1]) if slope == 0: # point is on boundary return True if (slope < 0) != (poly[j][1] < poly[i][1]): c = not c j = i return c