Even–odd rule explained

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]

Implementation

Below is a partial example implementation in Python,[3] by using a ray to the right of the point being checked:def is_point_in_path(x: int, y: int, poly: list[tuple[int, int]]) -> 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""" c = False for i in range(len(poly)): ax, ay = poly[i] bx, by = poly[i - 1] if (x

ax) and (y

ay): # point is a corner return True if (ay > y) != (by > y): slope = (x - ax) * (by - ay) - (bx - ax) * (y - ay) if slope

0: # point is on boundary return True if (slope < 0) != (by < ay): c = not c return c

See also

External links

Notes and References

  1. J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principles and Practice. The SystemsProgramming Series. Addison-Wesley, Reading, 2nd edition, 1990.
  2. https://www.w3.org/TR/SVG/painting.html#WindingRule
  3. Web site: PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF).