Misplaced Pages

Even–odd rule

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Even-odd rule) Algorithm in vector-based graphic software
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 (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:

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.

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.

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(x: int, y: int, poly: list]) -> 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(len(poly)):
        ax, ay = poly
        bx, by = poly
        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

References

  1. 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.
  2. , w3c.org, retrieved 2019-03-28
  3. "PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF)".

External links


Stub icon

This computer-programming-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: