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 specification says: "This rule determines the "insideness" of a point on the canvas by drawing a ray from that point to infinity in any direction and counting the number of path segments from the given shape that the ray crosses. If this number is odd, the point is inside; if even, the point is outside."
On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.
def isPointInPath(x, y, poly): """ x, y -- x and y coordinates of point poly -- a list of tuples [(x, y), (x, y), ...] """ num = len(poly) i = 0 j = num - 1 c = False for i in range(num): if ((poly[i] > y) != (poly[j] > y)) and \ (x < poly[i] + (poly[j] - poly[i]) * (y - poly[i]) / (poly[j] - poly[i])): c = not c j = i return c
- J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principles and Practice. The Systems Programming Series. Addison-Wesley, Reading, 2nd edition, 1990.
|This computer-programming-related article is a stub. You can help Wikipedia by expanding it.|