thumb|upright=1.5|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.
În grafica digitală bidimensională regula par-impar este un algoritm implementat în software de grafică vectorială, J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, Computer Graphics: Principles and Practice, The Systems Programming Series, Addison-Wesley, Reading, 2nd edition, 1990 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.
SVG definește regula par–impar astfel:
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 .
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. , w3c.org, retrieved 2019-03-28
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
Note
Vezi și Teselare Regula indicelui de rotație nenul
Legături externe
Definition of fill rules in SVG
Categorie:Algoritmi de grafică digitală Categorie:Paritate