Even–odd rule
Image:Even-odd and non-zero winding fill [rules.png|thumb|A curve (top) is filled according to two rules: the even–odd rule (left), and the non-zero winding rule (right). In each case an arrow shows a ray from a point P heading out of the curve. In the even–odd case, the ray is intersected by two lines, an even number; therefore P is concluded to be 'outside' the curve. By the non-zero winding rule, the ray is intersected in a clockwise direction twice, each contributing −1 to the winding score: because the total, −2, is not zero, P is concluded to be 'inside' the curve.]
The even–odd rule is an algorithm implemented in vector-based graphic software, like the PostScript language and Scalable Vector Graphics, 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, 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.
Implementation
Below is a partial example implementation in Python, by using a ray to the right of the point being checked:def is_point_in_path -> 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
Returns:
True if the point is in the path or is a corner or on the boundary"""
c = False
for i in range:
ax, ay = poly
bx, by = poly
if and :
# point is a corner
return True
if != :
slope = * - *
if slope 0:
# point is on boundary
return True
if != :
c = not c
return c