Regula par–impar

În grafica digitală bidimensională regula par-impar este un algoritm implementat în software de grafică vectorială, precum limbajul PostScript și Scalable Vector Graphics (SVG), care determină modul în care va fi umplută o formă grafică înconjurată de mai mult de un contur închis. Spre deosebire de algoritmul regula indicelui de rotație nenul, acest algoritm va colora alternativ și va lăsa necolorate formele definite de curbele închise imbricate, indiferent de modul lor de înfășurare.

Interiorul unei curbe (sus) este umplut în conformitate cu două reguli: regula par–impar (în stânga) și regula indicelui de rotație nenul (dreapta). În fiecare caz este trasată o săgeată (rază) dintr-un punct P spre exteriorul curbei. În cazul în care săgeata intersectează curba de două ori, un număr par, se consideră că P este „în exteriorul” curbei. După regula indicelui de rotație nenul, raza este intersectată în sensul acelor de ceasornic de două ori, fiecare intersecție contribuind cu −1 la scorul indicelui de rotație (a numărului de înfășurări); deoarece totalul, −2, nu este zero, se trage concluzia că P se află „în interiorul” curbei.

SVG definește regula par–impar astfel:

„Această regulă determină că un punct de pe suprafață este „în interior”, desenând o rază din acel punct spre infinit în orice direcție și numărând numărul de segmente de curbă ale formei date pe care le traversează raza. Dacă acest număr este impar, punctul este în interior; dacă este par, punctul este în exterior.”

Regula poate fi implementată efectiv în multe programe de grafică vectorială (cum ar fi Macromedia FreeHand sau Adobe Illustrator), unde o autointersectare a unui contur determină umplerea formelor în moduri ciudate.

La o curbă simplă, regula par–impar se reduce la un algoritm de decizie pentru problema „punct în poligon”^⁠(d).

Standardul vectorial de grafică digitală SVG poate fi configurat să folosească regula par–impar la desenarea poligoanelor, dar implicit folosește regula indicelui de rotație nenul.

Implementare

Mai jos este un exemplu parțial de implementare în Python, folosind o rază spre dreapta punctului verificat:

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

Vezi și

• Teselare
• Regula indicelui de rotație nenul

Legături externe

• en Definition of fill rules in SVG