Initializing 3D Canvas...

The Polygon

1 min read•1 page

Polygon

If a line is the smallest geometry you can build by using points, and polyline is a collection of points (or segments), the polygon is the particular polyline that is always closed, therefore defining a contained area.

The Boundary Representation: In algorithmic architecture, a polygon is fundamentally a boundary. It does not contain "mass" or "area" physically — its mathematical perimeter impliesan area.
Sides
5.00
1 min read•1 page

Data structure

A Polygon is stored in memory as an ordered array of Point3d objects (vertices). The most critical rule of a computational polygon is that it must be Closed. The last point in the array must connect back to the first point, forming a continuous loop.

python
1class Polygon:
2    def __init__(self, vertices: list):
3        if len(vertices) < 3:
4            raise ValueError("A polygon requires at least 3 vertices.")
5        self.Vertices = vertices
6        
7        # Ensure it is explicitly closed
8        if not self.Vertices[0].EpsilonEquals(self.Vertices[-1], 0.001):
9            self.Vertices.append(self.Vertices[0])
2 min read•1 page

WindingOrder:

Winding order is the direction (Clockwise vs Counter-Clockwise) of the vertices. Winding order is crucial for calculating normal vectors, determining interior space, and performing correct boolean operations.
python
1def DetermineWindingOrder(pts: list['Point3d']) -> str:
2    """Calculates winding order of a 2D polygon using the Shoelace formula."""
3    area = 0.0
4    n = len(pts)
5    for i in range(n):
6        j = (i + 1) % n
7        # Accumulate cross product
8        area += (pts[i].X * pts[j].Y) - (pts[j].X * pts[i].Y)
9        
10    # CCW has positive signed area, CW has negative
11    if area > 0.0:
12        return "Counter-Clockwise (CCW)"
13    elif area < 0.0:
14        return "Clockwise (CW)"
15    return "Degenerate / Collinear"
Clockwise vs Counter-Clockwise
5 min read•2 pages

Convexity & Convex Hull:

A polygon is Convex if all its interior angles are less than 180° and any line segment between two interior points lies entirely inside the shape. Otherwise, it is Concave. The Convex Hull is the smallest convex boundary enclosing all vertices (like a rubber band wrapped around them).
python
1def IsConvex(pts: list['Point3d']) -> bool:
2    """Checks if a simple 2D polygon is convex."""
3    n = len(pts)
4    if n < 3: return False
5    
6    sign = 0
7    for i in range(n):
8        p1 = pts[i]
9        p2 = pts[(i + 1) % n]
10        p3 = pts[(i + 2) % n]
11        
12        # Cross product of consecutive edges
13        cross = (p2.X - p1.X) * (p3.Y - p2.Y) - (p2.Y - p1.Y) * (p3.X - p2.X)
14        if abs(cross) > 1e-9:
15            current_sign = 1 if cross > 0 else -1
16            if sign == 0:
17                sign = current_sign
18            elif sign != current_sign:
19                return False
20    return True

The most classic algorithm to calculate the Convex Hull is the Jarvis March (Gift Wrapping) method:

python
1def ConvexHull2D(pts: list['Point3d']) -> list['Point3d']:
2    """Computes the convex hull of 2D points using Jarvis March."""
3    n = len(pts)
4    if n < 3: return pts
5    
6    leftmost = 0
7    for i in range(1, n):
8        if pts[i].X < pts[leftmost].X:
9            leftmost = i
10            
11    hull = []
12    p = leftmost
13    while True:
14        hull.append(pts[p])
15        q = (p + 1) % n
16        for i in range(n):
17            # Check if point i is to the left of p-q line
18            cross = (pts[i].X - pts[p].X) * (pts[q].Y - pts[p].Y) - (pts[i].Y - pts[p].Y) * (pts[q].X - pts[p].X)
19            if cross < 0:
20                q = i
21        p = q
22        if p == leftmost:
23            break
24            
25    hull.append(hull[0])  # Close path
26    return hull
Vertex 3
2.00
2 min read•1 page

Area/Centroid:

A polygon's properties are derived from its vertex sequence.
The most common properties are Area (often calculated via the Shoelace Formula) and Centroid (the geometric center).
python
1class Polygon:
2    @property
3    def Area(self) -> float:
4        """Calculates area using the Shoelace Formula."""
5        n = len(self.Vertices)
6        area2 = 0.0
7        for i in range(n):
8            j = (i + 1) % n
9            area2 += self.Vertices[i].X * self.Vertices[j].Y - self.Vertices[j].X * self.Vertices[i].Y
10        return abs(area2) / 2.0
11

12    @property
13    def Centroid(self) -> Point3d:
14        """The geometric center (average of vertices)."""
15        return Point3d.Average(self.Vertices)
2 min read•1 page

Signed Area:

Calculates the area of a polygon where the mathematical sign (+/-) reveals the winding direction.

python
1# RhinoCommon handles this internally via Curve.ClosedCurveOrientation()
2# But the underlying math is the Shoelace formula:
3

4def SignedArea(pts: list[Point3d]) -> float:
5    """Calculates area. Positive = CCW, Negative = CW."""
6    n = len(pts)
7    area2 = 0.0
8    for i in range(n):
9        j = (i + 1) % n
10        # Cross product of 2D coordinates
11        area2 += pts[i].X * pts[j].Y - pts[j].X * pts[i].Y
12    
13    return area2 / 2.0
The famous "Shoelace Formula" computes area by summing the 2D cross products of adjacent vertices. Because the cross product is direction-sensitive, the final sum will be Positive if the vertices wind Counter-Clockwise, and Negative if they wind Clockwise.

This is a failry common method to determine if a polygon is a "hole" (CW) or an "outer boundary" (CCW).

Toggle Direction
2 min read•1 page

Contains(Point3d):

Determines if a test point lies inside or outside the polygon boundary.
python
1class Polygon:
2    def Contains(self, test_point: Point3d) -> bool:
3        """Point-in-Polygon (PIP) Raycasting Algorithm."""
4        n = len(self.Vertices)
5        inside = False
6        px, py = test_point.X, test_point.Y
7        
8        j = n - 1
9        for i in range(n):
10            xi, yi = self.Vertices[i].X, self.Vertices[i].Y
11            xj, yj = self.Vertices[j].X, self.Vertices[j].Y
12            
13            if (yi > py) != (yj > py):
14                if px < (xj - xi) * (py - yi) / (yj - yi) + xi:
15                    inside = not inside
16            j = i
17            
18        return inside
Test Point X
0.00
Test Point Y
0.00
The Raycasting Algorithm is the industry standard for determining if a point lives inside or outside a polygon. It works by shooting an infinite ray in one direction from the test point and counting how many edges it crosses. An odd number of crossings means "Inside", while an even number means "Outside".
1 min read•1 page

Move(Vector3d):

Translates a polygon by moving all its vertices by a common displacement vector.
python
1class Polygon:
2    def Move(self, vector: Vector3d) -> 'Polygon':
3        """Translates all vertices by the given vector."""
4        return Polygon([v.Move(vector) for v in self.Vertices])
Transforming a polygon is simple because it is built from points. Moving a polygon means iterating through its vertex list and moving each point by the same vector.
Move X
2.00
Move Y
1.00
1 min read•1 page

Scale(factor, center):

Scales a polygon relative to a specified center point (usually its centroid).
python
1class Polygon:
2    def Scale(self, factor: float, center: Point3d) -> 'Polygon':
3        """Scales all vertices relative to a center point."""
4        return Polygon([v.Scale(factor, center) for v in self.Vertices])
Scaling a polygon typically happens from its Centroid. Just like moving, we iterate through the vertices and apply a scaling transformation to each one relative to the chosen center point.
Scale Factor
1.50
1 min read•1 page

Rotate(angle, axis, center):

Rotates a polygon by a given angle around an axis and pivot point.
python
1class Polygon:
2    def Rotate(self, angle: float, axis: Vector3d, center: Point3d) -> 'Polygon':
3        """Rotates all vertices around an axis and center."""
4        return Polygon([v.Rotate(angle, axis, center) for v in self.Vertices])
Rotating a polygon is a vertex-level operation. By spinning each vertex around a central axis (usually the centroid), the entire boundary preserves its shape while changing orientation.
Angle
45.00
2 min read•1 page

Offset:

Offsetting is the process of creating a new polygon boundary that is a fixed distance away from the original. This is computationally intense because it requires calculatingMiters at every vertex — finding the bisector of the angle to ensure the offset distance remains constant.

python
1class Polygon:
2    def offset(self, distance: float) -> 'Polygon':
3        """Calculates an expanded or contracted boundary."""
4        offset_vertices = []
5        n = len(self.vertices)
6        for i in range(n):
7            prev = self.vertices[i - 1]
8            curr = self.vertices[i]
9            next = self.vertices[(i + 1) % n]
10            
11            # Edge normals
12            e1 = (curr - prev).normalized()
13            e2 = (next - curr).normalized()
14            n1 = Vector2(-e1.y, e1.x)
15            n2 = Vector2(-e2.y, e2.x)
16            
17            # Miter vector
18            miter = (n1 + n2).normalized()
19            miter_len = 1.0 / max(0.2, miter.dot(n1))
20            
21            offset_vertices.append(curr + miter * (distance * miter_len))
22            
23        return Polygon(offset_vertices)
This is a naive implementation for a proper one use the Clipper2 library
Distance
0.50
7 min read•2 pages

Union:

Boolean Union merges two or more overlapping closed polygons into a single combined boundary. It is commonly used in space planning to merge adjacent rooms, zones, or structural boundaries.

python
1import math
2"""Naive approach"""
3class Point2D:
4    def __init__(self, x: float, y: float):
5        self.x = x
6        self.y = y
7

8def is_point_inside(pt: Point2D, poly: list[Point2D]) -> bool:
9    """Raycasting Point-in-Polygon (PIP) check."""
10    inside = False
11    n = len(poly)
12    for i in range(n):
13        p1, p2 = poly[i], poly[(i + 1) % n]
14        if p1.y > pt.y != p2.y > pt.y:
15            if pt.x < (p2.x - p1.x) * (pt.y - p1.y) / (p2.y - p1.y) + p1.x:
16                inside = not inside
17    return inside
18

19def get_intersection(p1: Point2D, p2: Point2D, q1: Point2D, q2: Point2D) -> Point2D | None:
20    """Calculates intersection point of segment p1p2 and q1q2."""
21    denom = (q2.y - q1.y) * (p2.x - p1.x) - (q2.x - q1.x) * (p2.y - p1.y)
22    if abs(denom) < 1e-9:
23        return None  # Parallel
24    ua = ((q2.x - q1.x) * (p1.y - q1.y) - (q2.y - q1.y) * (p1.x - q1.x)) / denom
25    ub = ((p2.x - p1.x) * (p1.y - q1.y) - (p2.y - p1.y) * (p1.x - q1.x)) / denom
26    if 0.0 <= ua <= 1.0 and 0.0 <= ub <= 1.0:
27        return Point2D(p1.x + ua * (p2.x - p1.x), p1.y + ua * (p2.y - p1.y))
28    return None
29

30def polygon_union(poly_a: list[Point2D], poly_b: list[Point2D]) -> list[Point2D]:
31    """Calculates the union boundary of two overlapping polygons."""
32    intersections = []
33    na, nb = len(poly_a), len(poly_b)
34    
35    # 1. Find all edge-edge intersections
36    for i in range(na):
37        p1, p2 = poly_a[i], poly_a[(i + 1) % na]
38        for j in range(nb):
39            q1, q2 = poly_b[j], poly_b[(j + 1) % nb]
40            intersect = get_intersection(p1, p2, q1, q2)
41            if intersect:
42                intersections.append(intersect)
43                
44    # 2. Collect outer boundary points
45    outer_points = []
46    for p in poly_a:
47        if not is_point_inside(p, poly_b):
48            outer_points.append(p)
49    for p in poly_b:
50        if not is_point_inside(p, poly_a):
51            outer_points.append(p)
52            
53    # 3. Combine and reconstruct the boundary
54    boundary = outer_points + intersections
55    if not boundary:
56        return []
57        
58    cx = sum(p.x for p in boundary) / len(boundary)
59    cy = sum(p.y for p in boundary) / len(boundary)
60    boundary.sort(key=lambda p: math.atan2(p.y - cy, p.x - cx))
61    
62    return boundary
Polygons must be oriented consistently (typically counter-clockwise for outer loops) to ensure Boolean operations succeed.
This is a naive implementation for a proper one use the Clipper2 library
Move Poly B (X)
1.00
Move Poly B (Y)
0.50
8 min read•2 pages

Difference:

Boolean Difference subtracts the region of one polygon (B) from another (A), written as A - B. It is essential for cutting holes, carving recesses, or creating setbacks in architectural layouts.

python
1def polygon_difference(poly_a: list[Point2D], poly_b: list[Point2D]) -> list[Point2D]:
2    """Naive approach - Calculates the difference (A - B) of two overlapping rectangles analytically."""
3    xMinA, xMaxA = min(p.x for p in poly_a), max(p.x for p in poly_a)
4    yMinA, yMaxA = min(p.y for p in poly_a), max(p.y for p in poly_a)
5    
6    xMinB, xMaxB = min(p.x for p in poly_b), max(p.x for p in poly_b)
7    yMinB, yMaxB = min(p.y for p in poly_b), max(p.y for p in poly_b)
8    
9    # Overlap region coordinates
10    x1, x2 = max(xMinA, xMinB), min(xMaxA, xMaxB)
11    y1, y2 = max(yMinA, yMinB), min(yMaxA, yMaxB)
12    
13    if x1 >= x2 or y1 >= y2:
14        # No overlap, returns original polygon A
15        return poly_a
16        
17    touches_left = abs(x1 - xMinA) < 1e-4
18    touches_right = abs(x2 - xMaxA) < 1e-4
19    touches_bottom = abs(y1 - yMinA) < 1e-4
20    touches_top = abs(y2 - yMaxA) < 1e-4
21    
22    if touches_left and touches_right and touches_bottom and touches_top:
23        return [] # B fully covers A
24        
25    if touches_left and touches_right and touches_bottom:
26        return [Point2D(xMinA, y2), Point2D(xMaxA, y2), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA)]
27    if touches_left and touches_right and touches_top:
28        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, y1), Point2D(xMinA, y1)]
29    if touches_left and touches_bottom and touches_top:
30        return [Point2D(x2, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(x2, yMaxA)]
31    if touches_right and touches_bottom and touches_top:
32        return [Point2D(xMinA, yMinA), Point2D(x1, yMinA), Point2D(x1, yMaxA), Point2D(xMinA, yMaxA)]
33        
34    if touches_left and touches_bottom:
35        return [Point2D(xMinA, y2), Point2D(x2, y2), Point2D(x2, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA)]
36    if touches_right and touches_bottom:
37        return [Point2D(xMinA, yMinA), Point2D(x1, yMinA), Point2D(x1, y2), Point2D(xMaxA, y2), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA)]
38    if touches_left and touches_top:
39        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(x2, yMaxA), Point2D(x2, y1), Point2D(xMinA, y1)]
40    if touches_right and touches_top:
41        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, y1), Point2D(x1, y1), Point2D(x1, yMaxA), Point2D(xMinA, yMaxA)]
42        
43    if touches_left:
44        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA), Point2D(xMinA, y2), Point2D(x2, y2), Point2D(x2, y1), Point2D(xMinA, y1)]
45    if touches_right:
46        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, y1), Point2D(x1, y1), Point2D(x1, y2), Point2D(xMaxA, y2), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA)]
47    if touches_bottom:
48        return [Point2D(xMinA, yMinA), Point2D(x1, yMinA), Point2D(x1, y2), Point2D(x2, y2), Point2D(x2, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(xMinA, yMaxA)]
49    if touches_top:
50        return [Point2D(xMinA, yMinA), Point2D(xMaxA, yMinA), Point2D(xMaxA, yMaxA), Point2D(x2, yMaxA), Point2D(x2, y1), Point2D(x1, y1), Point2D(x1, yMaxA), Point2D(xMinA, yMaxA)]
51        
52    return poly_a
Move Poly B (X)
1.00
Move Poly B (Y)
0.50
This is a naive implementation for a proper one use the Clipper2 library
7 min read•2 pages

Intersection:

Boolean Intersection finds the common overlapping region between two or more closed polygons. It is used to find common zone clearances, setbacks, or conflict areas between multiple planning boundaries.

Intersection operations return empty lists if there is no spatial overlap between boundaries.
python
1import math
2"""Naive approach"""
3class Point2D:
4    def __init__(self, x: float, y: float):
5        self.x = x
6        self.y = y
7

8def is_point_inside(pt: Point2D, poly: list[Point2D]) -> bool:
9    """Raycasting Point-in-Polygon (PIP) check."""
10    inside = False
11    n = len(poly)
12    for i in range(n):
13        p1, p2 = poly[i], poly[(i + 1) % n]
14        if p1.y > pt.y != p2.y > pt.y:
15            if pt.x < (p2.x - p1.x) * (pt.y - p1.y) / (p2.y - p1.y) + p1.x:
16                inside = not inside
17    return inside
18

19def get_intersection(p1: Point2D, p2: Point2D, q1: Point2D, q2: Point2D) -> Point2D | None:
20    """Calculates intersection point of segment p1p2 and q1q2."""
21    denom = (q2.y - q1.y) * (p2.x - p1.x) - (q2.x - q1.x) * (p2.y - p1.y)
22    if abs(denom) < 1e-9:
23        return None  # Parallel
24    ua = ((q2.x - q1.x) * (p1.y - q1.y) - (q2.y - q1.y) * (p1.x - q1.x)) / denom
25    ub = ((p2.x - p1.x) * (p1.y - q1.y) - (p2.y - p1.y) * (p1.x - q1.x)) / denom
26    if 0.0 <= ua <= 1.0 and 0.0 <= ub <= 1.0:
27        return Point2D(p1.x + ua * (p2.x - p1.x), p1.y + ua * (p2.y - p1.y))
28    return None
29

30def polygon_intersection(poly_a: list[Point2D], poly_b: list[Point2D]) -> list[Point2D]:
31    """Calculates the intersection boundary of two overlapping polygons."""
32    intersections = []
33    na, nb = len(poly_a), len(poly_b)
34    
35    # 1. Find all edge-edge intersections
36    for i in range(na):
37        p1, p2 = poly_a[i], poly_a[(i + 1) % na]
38        for j in range(nb):
39            q1, q2 = poly_b[j], poly_b[(j + 1) % nb]
40            intersect = get_intersection(p1, p2, q1, q2)
41            if intersect:
42                intersections.append(intersect)
43                
44    # 2. Collect boundary points for A ∩ B: points of A inside B, and B inside A
45    boundary_pts = []
46    for p in poly_a:
47        if is_point_inside(p, poly_b):
48            boundary_pts.append(p)
49    for p in poly_b:
50        if is_point_inside(p, poly_a):
51            boundary_pts.append(p)
52            
53    # 3. Combine with intersections and sort radially around centroid
54    boundary = boundary_pts + intersections
55    if not boundary:
56        return []
57        
58    cx = sum(p.x for p in boundary) / len(boundary)
59    cy = sum(p.y for p in boundary) / len(boundary)
60    boundary.sort(key=lambda p: math.atan2(p.y - cy, p.x - cx))
61    
62    return boundary
This is a naive implementation for a proper one use the Clipper2 library
Move Poly B (X)
1.00
Move Poly B (Y)
0.50
8 min read•2 pages

Triangulation:

Triangulation is the process of breaking a complex polygon down into simple triangles. Because rendering engines (like GPUs) only know how to draw triangles, every polygon you see on screen is secretly triangulated under the hood.

python
1class Point2D:
2    def __init__(self, x: float, y: float):
3        self.x = x
4        self.y = y
5

6def is_ccw(a: Point2D, b: Point2D, c: Point2D) -> bool:
7    """Checks if three points form a counter-clockwise turn."""
8    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0
9

10def point_in_triangle(p: Point2D, a: Point2D, b: Point2D, c: Point2D) -> bool:
11    """Checks if point p lies inside the triangle abc using barycentric coordinates."""
12    denom = (b.y - c.y) * (a.x - c.x) + (c.x - b.x) * (a.y - c.y)
13    if abs(denom) < 1e-9:
14        return False
15    u = ((b.y - c.y) * (p.x - c.x) + (c.x - b.x) * (p.y - c.y)) / denom
16    v = ((c.y - a.y) * (p.x - c.x) + (a.x - c.x) * (p.y - c.y)) / denom
17    w = 1 - u - v
18    return u >= 0 and v >= 0 and w >= 0
19

20def is_ear(poly: list[Point2D], i: int) -> bool:
21    """Checks if vertex i is a valid 'ear' of the polygon to clip."""
22    n = len(poly)
23    prev_idx = (i - 1) % n
24    next_idx = (i + 1) % n
25    
26    a, b, c = poly[prev_idx], poly[i], poly[next_idx]
27    
28    # 1. Ear must be convex (pointing outwards)
29    if not is_ccw(a, b, c):
30        return False
31        
32    # 2. No other vertices of the polygon should lie inside the triangle abc
33    for j in range(n):
34        if j in (i, prev_idx, next_idx):
35            continue
36        if point_in_triangle(poly[j], a, b, c):
37            return False
38            
39    return True
40

41def triangulate_polygon(vertices: list[Point2D]) -> list[tuple[int, int, int]]:
42    """
43    Triangulates a simple polygon using the Ear Clipping algorithm.
44    Returns a list of triangles, each defined by three vertex indices.
45    """
46    n = len(vertices)
47    indices = list(range(n))
48    triangles = []
49    
50    # Ensure winding order is CCW
51    area = 0.0
52    for i in range(n):
53        p1, p2 = vertices[i], vertices[(i + 1) % n]
54        area += p1.x * p2.y - p2.x * p1.y
55    if area < 0:
56        vertices = vertices[::-1]
57        
58    # Clip ears until only 1 triangle remains
59    while len(indices) > 3:
60        ear_found = False
61        for i in range(len(indices)):
62            curr_poly = [vertices[idx] for idx in indices]
63            if is_ear(curr_poly, i):
64                prev_idx = indices[(i - 1) % len(indices)]
65                curr_idx = indices[i]
66                next_idx = indices[(i + 1) % len(indices)]
67                
68                triangles.append((prev_idx, curr_idx, next_idx))
69                indices.pop(i)  # Clip the ear
70                ear_found = True
71                break
72                
73        if not ear_found:
74            break  # Fallback for degenerate cases
75            
76    if len(indices) == 3:
77        triangles.append((indices[0], indices[1], indices[2]))
78        
79    return triangles
2 min read•1 page

Closest Point:

Finding the Closest Point on a polygon boundary is a search operation. The algorithm decomposes the polygon into a series of line segments, projects the test point onto every segment, and returns the result with the shortest absolute distance.

python
1class Polygon:
2    def closest_point(self, test_point: Point3d) -> Point3d:
3        """Finds the nearest point on the boundary."""
4        min_dist = float('inf')
5        best_point = self.vertices[0]
6        n = len(self.vertices)
7        
8        for i in range(n):
9            a = self.vertices[i]
10            b = self.vertices[(i + 1) % n]
11            
12            # Project test_point onto segment ab
13            ab = b - a
14            ab_len_sq = ab.length_squared()
15            if ab_len_sq == 0:
16                proj = a
17            else:
18                t = max(0.0, min(1.0, (test_point - a).dot(ab) / ab_len_sq))
19                proj = a + ab * t
20                
21            dist = (test_point - proj).length()
22            if dist < min_dist:
23                min_dist = dist
24                best_point = proj
25                
26        return best_point
Test Point X
3.00
Test Point Y
3.00
4 min read•1 page

Is Simple:

A polygon is considered simple if its boundary does not cross itself. Self-intersecting (complex) polygons break many common algorithms like triangulation and offset, making simplicity verification a critical validation step.

python
1def is_simple_polygon(polygon: Polyline) -> bool:
2    """
3    Checks if a polygon is simple (no self-intersections).
4    Uses a naive O(N^2) check or Bentley-Ottmann sweep-line algorithm.
5    """
6    pts = polygon.points
7    n = len(pts)
8    if n < 3:
9        return False
10        
11    def line_intersection(p1, p2, p3, p4):
12        # Standard line segment intersection test
13        d = (p2.X - p1.X) * (p4.Y - p3.Y) - (p2.Y - p1.Y) * (p4.X - p3.X)
14        if d == 0:
15            return None # Parallel
16        u = ((p3.X - p1.X) * (p4.Y - p3.Y) - (p3.Y - p1.Y) * (p4.X - p3.X)) / d
17        v = ((p3.X - p1.X) * (p2.Y - p1.Y) - (p3.Y - p1.Y) * (p2.X - p1.X)) / d
18        if 0 < u < 1 and 0 < v < 1:
19            return Point3d(p1.X + u * (p2.X - p1.X), p1.Y + u * (p2.Y - p1.Y), 0)
20        return None
21

22    # Compare every pair of non-adjacent segments
23    for i in range(n):
24        for j in range(i + 2, n):
25            if i == 0 and j == n - 1:
26                continue # Adjacent segments share a vertex
27            pt = line_intersection(pts[i], pts[(i+1)%n], pts[j], pts[(j+1)%n])
28            if pt is not None:
29                return False # Self-intersection found!
30    return True
Non-simple polygons often cause geometry kernels to crash or yield invalid geometries when processing operations like offsets or booleans.
Self Intersection
0.50
3 min read•1 page

Contains Polygon:

A polygon A contains another polygon B if all points of B lie within the region of A. This requires checking that all of B's vertices are inside A and that their boundaries do not intersect.

python
1def contains_polygon(poly_a: Polyline, poly_b: Polyline) -> bool:
2    """
3    Checks if polygon A completely contains polygon B.
4    All vertices of B must lie inside or on the boundary of A,
5    and no edges of B may intersect the edges of A.
6    """
7    # 1. Check if all vertices of B are inside A
8    for pt in poly_b.points:
9        if not poly_a.contains_point(pt, include_boundary=True):
10            return False
11            
12    # 2. Verify no edge intersections between A and B
13    for i in range(len(poly_a.points)):
14        edge_a = (poly_a.points[i], poly_a.points[(i+1)%len(poly_a.points)])
15        for j in range(len(poly_b.points)):
16            edge_b = (poly_b.points[j], poly_b.points[(j+1)%len(poly_b.points)])
17            if segments_intersect(edge_a, edge_b):
18                return False
19                
20    return True
Containment is a foundational tool for layout validation, spatial grouping, and nesting optimization in CAD systems.
Move Poly B (X)
0.00
Move Poly B (Y)
0.00