2D Booleans

2 min read•1 page

In 2D boolean clipping, a polygon is represented as an ordered sequence of 2D coordinates forming closed boundary contours.

Polygon Structure:

1. Coordinates are sequenced in clockwise or counter-clockwise order. 2. Edges are segments connecting adjacent coordinates. 3. The boundary wraps back from the last vertex to the first.

python

1# 2D Polygon Representation
2class Point2D:
3    def __init__(self, x, y):
4        self.x = x
5        self.y = y
6
7class Polygon2D:
8    def __init__(self, vertices):
9        # Ordered list of Point2D objects forming a closed boundary
10        self.vertices = vertices
11        
12    def edges(self):
13        n = len(self.vertices)
14        return [(self.vertices[i], self.vertices[(i + 1) % n]) for i in range(n)]

2 min read•1 page

Knowing loop orientation is crucial for booleans. Clockwise (CW) vs Counter-Clockwise (CCW) determines outer boundaries and internal holes.

Winding Orientation:

1. Walk along vertices summing cross products. 2. Positive signed area indicates CCW orientation. 3. Negative signed area indicates CW orientation.

python

1# Compute signed area to determine contour winding direction
2def get_polygon_signed_area(vertices):
3    area = 0.0
4    n = len(vertices)
5    for i in range(n):
6        p1 = vertices[i]
7        p2 = vertices[(i + 1) % n]
8        # Sum cross-products of coordinate coordinates
9        area += (p1.x * p2.y) - (p2.x * p1.y)
10    return 0.5 * area
11
12# CCW if area > 0, CW if area < 0
13def is_ccw(vertices):
14    return get_polygon_signed_area(vertices) > 0.0

3 min read•1 page

To merge boundaries, we locate all crossings where edges from Polygon A intersect edges of Polygon B.

Intersection Solving:

1. Loop through all edge pairs of both polygons. 2. Solve parametric equations for lines crossing. 3. Record intersection coordinate if crossing parameters t, u lie in range [0, 1].

python

1# Check segment-segment intersection in 2D
2def line_intersection(seg1, seg2):
3    p0, p1 = seg1
4    q0, q1 = seg2
5    
6    # Solve parametric equations: p0 + t*(p1-p0) == q0 + u*(q1-q0)
7    denom = (p1.x - p0.x) * (q1.y - q0.y) - (p1.y - p0.y) * (q1.x - q0.x)
8    if abs(denom) < 1e-8:
9        return None # Parallel lines
10        
11    t = ((q0.x - p0.x) * (q1.y - q0.y) - (q0.y - p0.y) * (q1.x - q0.x)) / denom
12    u = ((q0.x - p0.x) * (p1.y - p0.y) - (q0.y - p0.y) * (p1.x - p0.x)) / denom
13    
14    if 0.0 <= t <= 1.0 and 0.0 <= u <= 1.0:
15        return Point2D(p0.x + t * (p1.x - p0.x), p0.y + t * (p1.y - p0.y))
16    return None

2 min read•1 page

To stitch polygons together, we insert intersection nodes directly into the coordinate sequence, splitting original edges into segments.

Edge Splitting:

1. Identify all intersection points lying on an edge segment. 2. Sort them by distance from the segment start vertex. 3. Insert the sorted intersection points between the two original vertices in the sequence list.

python

1# Insert intersection nodes into polygon edge list
2def split_edges(polygon_vertices, intersection_points):
3    updated_vertices = []
4    n = len(polygon_vertices)
5    for i in range(n):
6        p0 = polygon_vertices[i]
7        p1 = polygon_vertices[(i + 1) % n]
8        updated_vertices.append(p0)
9        
10        # Filter intersections lying on this segment, sort by distance from p0
11        seg_hits = find_intersections_on_segment(p0, p1, intersection_points)
12        for hit in sorted(seg_hits, key=lambda h: distance(p0, h)):
13            updated_vertices.append(hit)
14            
15    return updated_vertices

1 min read•1 page

Each split segment is evaluated to determine if it lies inside, outside, or on the boundary of the other polygon.

Edge Classification:

1. Calculate the midpoint coordinate of each split segment. 2. Test containment of the midpoint against the other polygon contour. 3. Label the segment based on the result (INSIDE, OUTSIDE, BOUNDARY).

python

1# Classify segments using winding checks or ray casting
2def classify_segment(segment, other_polygon):
3    midpoint = Point2D(
4        (segment[0].x + segment[1].x) / 2,
5        (segment[0].y + segment[1].y) / 2
6    )
7    
8    if other_polygon.contains(midpoint):
9        return "INSIDE"
10    elif other_polygon.on_boundary(midpoint):
11        return "BOUNDARY"
12    else:
13        return "OUTSIDE"

3 min read•1 page

Depending on the chosen boolean operation (Union, Intersection, or Difference), we discard segments that do not meet the containment rules.

Trimming Logic:

1. Union: Keep segments classified as outside. 2. Intersection: Keep segments classified as inside. 3. Difference: Keep outside segments of shape A, and inside segments of shape B (reversing their direction).

python

1# Selectively keep segments based on the boolean operation type
2def trim_segments(segments_A, segments_B, operation):
3    trimmed = []
4    
5    if operation == "UNION":
6        # Keep outside segments of both shapes
7        trimmed.extend([s for s in segments_A if s.classification == "OUTSIDE"])
8        trimmed.extend([s for s in segments_B if s.classification == "OUTSIDE"])
9    elif operation == "INTERSECTION":
10        # Keep inside segments of both shapes
11        trimmed.extend([s for s in segments_A if s.classification == "INSIDE"])
12        trimmed.extend([s for s in segments_B if s.classification == "INSIDE"])
13    elif operation == "DIFFERENCE":
14        # Keep outside of A, and inside of B (inverted direction)
15        trimmed.extend([s for s in segments_A if s.classification == "OUTSIDE"])
16        trimmed.extend([s.inverted() for s in segments_B if s.classification == "INSIDE"])
17        
18    return trimmed

Boolean Op (0=Union, 1=Intersect, 2=Difference)

0.00

2 min read•1 page

Finally, the trimmed segments are linked head-to-tail to reconstruct closed loops, yielding the final clipped polygon geometry boundaries.

Stitching Algorithm:

1. Take a segment, start a loop path. 2. Find and pop the segment whose start point matches the loop end point. 3. Repeat until the loop wraps back to its starting coordinate.

python

1# Stitch trimmed segments into closed loops
2def stitch_loops(segments):
3    loops = []
4    while segments:
5        current_segment = segments.pop(0)
6        loop = [current_segment.start, current_segment.end]
7        
8        while True:
9            # Find next segment that shares the end coordinate of current loop
10            next_idx = find_next_segment_index(loop[-1], segments)
11            if next_idx is None:
12                break # Open loop or error
13                
14            next_seg = segments.pop(next_idx)
15            loop.append(next_seg.end)
16            
17            # Check if loop is closed back to start point
18            if distance(loop[-1], loop[0]) < 1e-8:
19                loops.append(loop[:-1])
20                break
21    return loops

2 min read•1 page

Complex polygons can have multiple disjoint parts (islands) and hollow regions (holes). We structure loops into a parent-child hierarchy to correctly define boundaries.

Hole Nesting:

1. Calculate areas and sort loops from largest to smallest. 2. Test containment of loops to establish parent-child pairings. 3. Classify even-depth loops as solid islands and odd-depth loops as hollow holes.

python

1# Determine nested parent-child island and hole tree structure
2def nest_loops(polygon_loops):
3    # Sort loops by bounding area descending
4    sorted_loops = sorted(polygon_loops, key=lambda l: polygon_area(l), reverse=True)
5    
6    tree = {root: []}
7    for loop in sorted_loops:
8        # Walk down tree to locate deepest parent loop enclosing this loop
9        parent = find_deepest_enclosing_parent(loop, tree)
10        parent.children.append(loop)
11        
12    # Loops at odd depths in the tree represent internal hollow holes
13    return tree