Winding Rules

1# Winding number definition
2# For a point P and curve C, the winding number represents 
3# the number of times C wraps around P.
4class PolygonWinding:
5    def __init__(self, vertices):
6        self.vertices = vertices

1# Determine if ray from P in direction D intersects edge AB
2def ray_intersect_edge(p, d, a, b):
3    # Solve system: P + t*D = A + u*(B-A)
4    # Return u in [0, 1] and t > 0
5    v1 = p - a
6    v2 = b - a
7    v3 = [-d[1], d[0]] # Perpendicular direction
8    
9    dot = v2[0] * v3[0] + v2[1] * v3[1]
10    if abs(dot) < 1e-9:
11        return None # Parallel
12        
13    t = (v2[0] * v1[1] - v2[1] * v1[0]) / dot
14    u = (v1[0] * v3[0] + v1[1] * v3[1]) / dot
15    
16    if t >= 0.0 and 0.0 <= u <= 1.0:
17        return p + t * d
18    return None

1# Determine crossing direction and update winding number
2def accumulate_winding(p, a, b, winding_number):
3    # Check if edge crosses the ray Y level
4    if a[1] <= p[1]:
5        if b[1] > p[1]: # Upward crossing
6            # Check if point is to the left of the edge
7            if is_left(a, b, p) > 0:
8                winding_number += 1
9    else:
10        if b[1] <= p[1]: # Downward crossing
11            if is_left(a, b, p) < 0:
12                winding_number -= 1
13    return winding_number
14
15def is_left(a, b, c):
16    # > 0 for c left of line ab, < 0 for right, 0 on line
17    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

1# Even-Odd Rule containment check
2def is_inside_even_odd(p, polygon):
3    winding = 0
4    # Loop over edges and count intersections
5    for i in range(len(polygon)):
6        a = polygon[i]
7        b = polygon[(i + 1) % len(polygon)]
8        
9        # Simple crossing check
10        if ((a[1] > p[1]) != (b[1] > p[1])) and \
11           (p[0] < (b[0] - a[0]) * (p[1] - a[1]) / (b[1] - a[1] + 1e-9) + a[0]):
12            winding += 1
13            
14    # Odd count is inside, Even is outside
15    return (winding % 2) != 0

1# Non-Zero Rule containment check
2def is_inside_non_zero(p, polygon):
3    winding = 0
4    for i in range(len(polygon)):
5        a = polygon[i]
6        b = polygon[(i + 1) % len(polygon)]
7        
8        # Track edge direction to accumulate signed crossings
9        if a[1] <= p[1]:
10            if b[1] > p[1] and is_left(a, b, p) > 0:
11                winding += 1
12        else:
13            if b[1] <= p[1] and is_left(a, b, p) < 0:
14                winding -= 1
15                
16    # Non-zero winding score is inside
17    return winding != 0
18
19def is_left(a, b, c):
20    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

1# Positive winding rule
2def is_inside_positive(p, polygon):
3    """Inside if winding number > 0 (positive direction only)."""
4    winding = compute_winding_number(p, polygon)
5    return winding > 0
6
7# Useful in font rendering and SVG path filling.
8# Only regions wrapped in the positive (CCW) direction
9# are considered interior. CW holes become exterior.

1# Negative winding rule
2def is_inside_negative(p, polygon):
3    """Inside if winding number < 0 (clockwise direction only)."""
4    winding = compute_winding_number(p, polygon)
5    return winding < 0
6
7# Opposite of positive rule. Only regions with net
8# clockwise wrapping are considered filled.
9# Useful for specific CAD kernel implementations.

1# Compare winding rule results on self-intersecting polygon
2def compare_rules(p, polygon):
3    winding = compute_winding_number(p, polygon)
4    crossings = count_crossings(p, polygon)
5    
6    results = {
7        'even_odd':  (crossings % 2) != 0,
8        'non_zero':  winding != 0,
9        'positive':  winding > 0,
10        'negative':  winding < 0,
11    }
12    return results
13
14# The star polygon highlights where rules differ:
15# - Even-Odd: center is outside (two crossings)
16# - Non-Zero: center is inside (winding = 2)