Английская Википедия:Even–odd rule

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Even-odd and non-zero winding fill rules.png

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:

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 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, by using a ray to the right of the point being check:

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

• Jordan curve theorem
• Complex polygon
• Tessellation
• TrueType

External links

• Definition of fill rules in SVG

Шаблон:Compu-prog-stub