0
# Geometry Processing and Generation
1

2
Pymunk provides advanced geometry processing capabilities for automatic shape generation, convex hull calculation, polygon simplification, and bitmap-to-geometry conversion using marching squares algorithms.
3

4
## Autogeometry Module
5

6
The `pymunk.autogeometry` module contains functions for automatic geometry generation and processing, particularly useful for converting images or bitmap data into physics collision shapes.
7

8
### Polyline Processing
9

10
Functions for processing and simplifying polylines (sequences of connected points).
11

12
```python { .api }
13
def is_closed(polyline: list[tuple[float, float]]) -> bool:
14
    """
15
    Test if a polyline is closed (first vertex equals last vertex).
16
    
17
    Args:
18
        polyline: List of (x, y) coordinate tuples
19
        
20
    Returns:
21
        True if polyline forms a closed loop
22
        
23
    Example:
24
        open_line = [(0, 0), (10, 0), (10, 10)]
25
        closed_line = [(0, 0), (10, 0), (10, 10), (0, 0)]
26
        
27
        print(is_closed(open_line))   # False
28
        print(is_closed(closed_line)) # True
29
    """
30

31
def simplify_curves(polyline: list[tuple[float, float]], tolerance: float) -> list[Vec2d]:
32
    """
33
    Simplify a polyline using the Douglas-Peucker algorithm.
34
    
35
    Excellent for smooth or gently curved shapes, removes redundant vertices
36
    while preserving overall shape within tolerance.
37
    
38
    Args:
39
        polyline: List of (x, y) coordinate tuples
40
        tolerance: Maximum allowed deviation from original shape
41
        
42
    Returns:
43
        Simplified polyline as list of Vec2d points
44
        
45
    Example:
46
        # Smooth curve with many points
47
        curve = [(i, math.sin(i * 0.1) * 10) for i in range(100)]
48
        simplified = pymunk.autogeometry.simplify_curves(curve, tolerance=1.0)
49
        print(f"Reduced from {len(curve)} to {len(simplified)} points")
50
    """
51

52
def simplify_vertexes(polyline: list[tuple[float, float]], tolerance: float) -> list[Vec2d]:
53
    """
54
    Simplify a polyline by discarding "flat" vertices.
55
    
56
    Excellent for straight-edged or angular shapes, removes vertices that
57
    don't significantly change direction.
58
    
59
    Args:
60
        polyline: List of (x, y) coordinate tuples  
61
        tolerance: Maximum allowed angular deviation
62
        
63
    Returns:
64
        Simplified polyline with flat vertices removed
65
        
66
    Example:
67
        # Rectangle with extra points on edges
68
        rect_with_extras = [
69
            (0, 0), (5, 0), (10, 0),     # Extra point at (5,0)
70
            (10, 5), (10, 10),           # Extra point at (10,5) 
71
            (5, 10), (0, 10),            # Extra point at (5,10)
72
            (0, 5), (0, 0)               # Extra point at (0,5)
73
        ]
74
        simplified = pymunk.autogeometry.simplify_vertexes(rect_with_extras, 0.1)
75
        # Result: [(0,0), (10,0), (10,10), (0,10), (0,0)] - clean rectangle
76
    """
77
```
78

79
### Convex Hull Generation
80

81
```python { .api }
82
def to_convex_hull(polyline: list[tuple[float, float]], tolerance: float) -> list[Vec2d]:
83
    """
84
    Calculate the convex hull of a set of points.
85
    
86
    Returns the smallest convex polygon that contains all input points.
87
    Useful for creating simplified collision shapes from complex geometry.
88
    
89
    Args:
90
        polyline: List of (x, y) coordinate tuples
91
        tolerance: Precision tolerance for hull calculation
92
        
93
    Returns:
94
        Convex hull as closed polyline (first and last points are same)
95
        
96
    Example:
97
        # Complex concave shape  
98
        points = [
99
            (0, 0), (10, 0), (5, 5),     # Triangle with internal point
100
            (15, 2), (20, 0), (25, 5),   # More complex boundary
101
            (20, 10), (10, 8), (0, 10)
102
        ]
103
        
104
        hull = pymunk.autogeometry.to_convex_hull(points, 0.1)
105
        
106
        # Create physics shape from hull
107
        hull_body = pymunk.Body(body_type=pymunk.Body.STATIC)
108
        hull_shape = pymunk.Poly(hull_body, hull[:-1])  # Exclude duplicate last point
109
        space.add(hull_body, hull_shape)
110
    """
111
```
112

113
### Convex Decomposition
114

115
```python { .api }
116
def convex_decomposition(polyline: list[tuple[float, float]], tolerance: float) -> list[list[Vec2d]]:
117
    """
118
    Decompose a complex polygon into multiple convex polygons.
119
    
120
    Breaks down concave shapes into simpler convex parts that can be
121
    used directly as Pymunk collision shapes.
122
    
123
    Args:
124
        polyline: List of (x, y) coordinate tuples forming the polygon
125
        tolerance: Approximation tolerance
126
        
127
    Returns:
128
        List of convex polygons, each as a list of Vec2d points
129
        
130
    Warning:
131
        Self-intersecting polygons may produce overly simplified results.
132
        
133
    Example:
134
        # L-shaped polygon (concave)
135
        l_shape = [
136
            (0, 0), (10, 0), (10, 5),
137
            (5, 5), (5, 10), (0, 10), (0, 0)
138
        ]
139
        
140
        convex_parts = pymunk.autogeometry.convex_decomposition(l_shape, 0.1)
141
        
142
        # Create physics shapes for each convex part
143
        body = pymunk.Body(body_type=pymunk.Body.STATIC) 
144
        for i, part in enumerate(convex_parts):
145
            shape = pymunk.Poly(body, part)
146
            shape.collision_type = i  # Different collision types if needed
147
            space.add(shape)
148
    """
149
```
150

151
### Marching Squares - Bitmap to Geometry
152

153
Convert bitmap data (images, heightmaps, etc.) into collision geometry using marching squares algorithms.
154

155
```python { .api }
156
def march_soft(
157
    bb: BB,
158
    x_samples: int, 
159
    y_samples: int,
160
    threshold: float,
161
    sample_func: Callable[[tuple[float, float]], float]
162
) -> PolylineSet:
163
    """
164
    Trace anti-aliased contours from bitmap data using marching squares.
165
    
166
    Creates smooth contours by interpolating between sample points.
167
    Excellent for organic shapes and smooth terrain generation.
168
    
169
    Args:
170
        bb: Bounding box of area to sample
171
        x_samples: Number of sample points horizontally
172
        y_samples: Number of sample points vertically  
173
        threshold: Value threshold for inside/outside determination
174
        sample_func: Function that returns sample value at (x, y) coordinate
175
        
176
    Returns:
177
        PolylineSet containing traced contour polylines
178
        
179
    Example:
180
        # Convert circular bitmap to geometry
181
        def circle_sample(point):
182
            x, y = point
183
            center = (50, 50)
184
            radius = 20
185
            distance = math.sqrt((x - center[0])**2 + (y - center[1])**2)
186
            return 1.0 if distance <= radius else 0.0
187
        
188
        bb = pymunk.BB(0, 0, 100, 100)
189
        polylines = pymunk.autogeometry.march_soft(
190
            bb, x_samples=50, y_samples=50, threshold=0.5, sample_func=circle_sample
191
        )
192
        
193
        # Create collision shapes from contours
194
        for polyline in polylines:
195
            if len(polyline) >= 3:  # Need at least 3 points for polygon
196
                body = space.static_body
197
                shape = pymunk.Poly(body, polyline)
198
                space.add(shape)
199
    """
200

201
def march_hard(
202
    bb: BB,
203
    x_samples: int,
204
    y_samples: int, 
205
    threshold: float,
206
    sample_func: Callable[[tuple[float, float]], float]
207
) -> PolylineSet:
208
    """
209
    Trace aliased (pixelated) contours from bitmap data.
210
    
211
    Creates hard-edged, pixelated contours following exact sample boundaries.
212
    Better for pixel art, tile-based games, or when exact pixel alignment is needed.
213
    
214
    Args:
215
        bb: Bounding box of area to sample
216
        x_samples: Number of sample points horizontally
217
        y_samples: Number of sample points vertically
218
        threshold: Value threshold for inside/outside determination  
219
        sample_func: Function that returns sample value at (x, y) coordinate
220
        
221
    Returns:
222
        PolylineSet containing traced contour polylines
223
        
224
    Example:
225
        # Convert pixel art to collision shapes
226
        pixel_art = [
227
            [0, 0, 0, 0, 0],
228
            [0, 1, 1, 1, 0], 
229
            [0, 1, 0, 1, 0],
230
            [0, 1, 1, 1, 0],
231
            [0, 0, 0, 0, 0]
232
        ]
233
        
234
        def pixel_sample(point):
235
            x, y = int(point[0]), int(point[1])
236
            if 0 <= x < 5 and 0 <= y < 5:
237
                return pixel_art[y][x]
238
            return 0
239
        
240
        bb = pymunk.BB(0, 0, 5, 5) 
241
        polylines = pymunk.autogeometry.march_hard(
242
            bb, x_samples=5, y_samples=5, threshold=0.5, sample_func=pixel_sample
243
        )
244
    """
245
```
246

247
### PolylineSet Class
248

249
```python { .api }
250
class PolylineSet:
251
    """
252
    Collection of polylines returned by marching squares algorithms.
253
    
254
    Provides sequence interface for easy iteration and processing.
255
    """
256
    
257
    def __init__(self) -> None:
258
        """Create empty polyline set."""
259
    
260
    def collect_segment(self, v0: tuple[float, float], v1: tuple[float, float]) -> None:
261
        """
262
        Add line segment to appropriate polyline.
263
        
264
        Automatically connects segments into continuous polylines.
265
        
266
        Args:
267
            v0: Start point of segment
268
            v1: End point of segment
269
        """
270
    
271
    # Sequence interface
272
    def __len__(self) -> int:
273
        """Return number of polylines in set."""
274
        
275
    def __getitem__(self, index: int) -> list[Vec2d]:
276
        """Get polyline at index."""
277
        
278
    def __iter__(self):
279
        """Iterate over polylines."""
280
```
281

282
## Utility Module (Deprecated)
283

284
The `pymunk.util` module contains legacy geometry utilities. These functions are deprecated in favor of `autogeometry` but remain for compatibility.
285

286
### Polygon Analysis
287

288
```python { .api }
289
import pymunk.util
290

291
def is_clockwise(points: list[tuple[float, float]]) -> bool:
292
    """
293
    Test if points form a clockwise polygon.
294
    
295
    Args:
296
        points: List of (x, y) coordinate tuples
297
        
298
    Returns:
299
        True if points are in clockwise order
300
        
301
    Example:
302
        cw_points = [(0, 0), (10, 0), (10, 10), (0, 10)]      # Clockwise  
303
        ccw_points = [(0, 0), (0, 10), (10, 10), (10, 0)]     # Counter-clockwise
304
        
305
        print(pymunk.util.is_clockwise(cw_points))   # True
306
        print(pymunk.util.is_clockwise(ccw_points))  # False
307
    """
308

309
def is_convex(points: list[tuple[float, float]]) -> bool:
310
    """
311
    Test if polygon is convex.
312
    
313
    Args:
314
        points: List of at least 3 (x, y) coordinate tuples
315
        
316
    Returns:
317
        True if polygon is convex (no internal angles > 180°)
318
        
319
    Example:
320
        square = [(0, 0), (10, 0), (10, 10), (0, 10)]
321
        l_shape = [(0, 0), (10, 0), (10, 5), (5, 5), (5, 10), (0, 10)]
322
        
323
        print(pymunk.util.is_convex(square))   # True
324
        print(pymunk.util.is_convex(l_shape)) # False  
325
    """
326

327
def is_left(p0: tuple[float, float], p1: tuple[float, float], p2: tuple[float, float]) -> int:
328
    """
329
    Test if point p2 is left, on, or right of line from p0 to p1.
330
    
331
    Args:
332
        p0: First point defining the line
333
        p1: Second point defining the line
334
        p2: Point to test
335
        
336
    Returns:
337
        > 0 if p2 is left of the line
338
        = 0 if p2 is on the line  
339
        < 0 if p2 is right of the line
340
    """
341
```
342

343
### Geometric Calculations
344

345
```python { .api }
346
import pymunk.util
347

348
def calc_center(points: list[tuple[float, float]]) -> Vec2d:
349
    """
350
    Calculate centroid (geometric center) of polygon.
351
    
352
    Args:
353
        points: Polygon vertices
354
        
355
    Returns:
356
        Center point as Vec2d
357
    """
358

359
def calc_area(points: list[tuple[float, float]]) -> float:
360
    """
361
    Calculate signed area of polygon.
362
    
363
    Returns:
364
        Positive area for counter-clockwise polygons
365
        Negative area for clockwise polygons
366
    """
367

368
def calc_perimeter(points: list[tuple[float, float]]) -> float:
369
    """Calculate perimeter (total edge length) of polygon."""
370

371
def convex_hull(points: list[tuple[float, float]]) -> list[Vec2d]:
372
    """
373
    Calculate convex hull using Graham scan algorithm.
374
    
375
    Returns:
376
        Convex hull vertices in counter-clockwise order
377
    """
378

379
def triangulate(polygon: list[tuple[float, float]]) -> list[list[Vec2d]]:
380
    """
381
    Triangulate polygon into triangles.
382
    
383
    Args:
384
        polygon: Simple polygon vertices
385
        
386
    Returns:
387
        List of triangles, each as 3-vertex list
388
    """
389
```
390

391
## Usage Examples
392

393
### Terrain Generation from Heightmap
394

395
```python { .api }
396
import pymunk
397
import pymunk.autogeometry
398
import math
399

400
def generate_terrain_from_heightmap(heightmap, world_width, world_height):
401
    """Generate physics terrain from 2D heightmap array"""
402
    
403
    height_samples = len(heightmap)
404
    width_samples = len(heightmap[0]) if heightmap else 0
405
    
406
    def sample_height(point):
407
        x, y = point
408
        # Normalize to heightmap coordinates
409
        hx = int((x / world_width) * width_samples)
410
        hy = int((y / world_height) * height_samples)
411
        
412
        # Clamp to valid range
413
        hx = max(0, min(width_samples - 1, hx))
414
        hy = max(0, min(height_samples - 1, hy))
415
        
416
        return heightmap[hy][hx]
417
    
418
    # Define terrain bounding box
419
    bb = pymunk.BB(0, 0, world_width, world_height)
420
    
421
    # Generate contour lines at different heights
422
    terrain_shapes = []
423
    for height_level in [0.2, 0.4, 0.6, 0.8]:
424
        polylines = pymunk.autogeometry.march_soft(
425
            bb, x_samples=50, y_samples=50, 
426
            threshold=height_level, sample_func=sample_height
427
        )
428
        
429
        # Convert polylines to collision shapes
430
        for polyline in polylines:
431
            if len(polyline) >= 3:
432
                # Simplify for performance
433
                simplified = pymunk.autogeometry.simplify_curves(polyline, tolerance=2.0)
434
                if len(simplified) >= 3:
435
                    body = space.static_body
436
                    shape = pymunk.Poly(body, simplified)
437
                    shape.friction = 0.7
438
                    terrain_shapes.append(shape)
439
    
440
    return terrain_shapes
441

442
# Example heightmap (mountain shape)
443
size = 20
444
heightmap = []
445
for y in range(size):
446
    row = []
447
    for x in range(size):
448
        # Create mountain shape
449
        center_x, center_y = size // 2, size // 2
450
        distance = math.sqrt((x - center_x)**2 + (y - center_y)**2)
451
        height = max(0, 1.0 - (distance / (size // 2)))
452
        row.append(height)
453
    heightmap.append(row)
454

455
# Generate terrain
456
terrain_shapes = generate_terrain_from_heightmap(heightmap, 800, 600)
457
space.add(*terrain_shapes)
458
```
459

460
### Image-Based Collision Generation
461

462
```python { .api }
463
import pymunk
464
import pymunk.autogeometry
465
from PIL import Image  # Requires Pillow: pip install pillow
466

467
def create_collision_from_image(image_path, scale=1.0, threshold=128):
468
    """Create collision shapes from image alpha channel or brightness"""
469
    
470
    # Load image
471
    image = Image.open(image_path).convert('RGBA')
472
    width, height = image.size
473
    pixels = image.load()
474
    
475
    def sample_image(point):
476
        x, y = int(point[0] / scale), int(point[1] / scale)
477
        
478
        # Clamp coordinates
479
        x = max(0, min(width - 1, x))  
480
        y = max(0, min(height - 1, y))
481
        
482
        # Sample alpha channel (or brightness for non-alpha images)
483
        r, g, b, a = pixels[x, y]
484
        return 1.0 if a > threshold else 0.0  # Use alpha for transparency
485
    
486
    # Define sampling area
487
    bb = pymunk.BB(0, 0, width * scale, height * scale)
488
    
489
    # Generate contours
490
    polylines = pymunk.autogeometry.march_soft(
491
        bb, x_samples=width, y_samples=height,
492
        threshold=0.5, sample_func=sample_image
493
    )
494
    
495
    # Convert to physics shapes
496
    shapes = []
497
    for polyline in polylines:
498
        if len(polyline) >= 3:
499
            # Simplify contour
500
            simplified = pymunk.autogeometry.simplify_curves(polyline, tolerance=1.0)
501
            
502
            if len(simplified) >= 3:
503
                body = space.static_body
504
                shape = pymunk.Poly(body, simplified)
505
                shape.friction = 0.7
506
                shapes.append(shape)
507
    
508
    return shapes
509

510
# Usage
511
collision_shapes = create_collision_from_image("sprite.png", scale=2.0)
512
space.add(*collision_shapes)
513
```
514

515
### Complex Shape Decomposition
516

517
```python { .api }
518
import pymunk
519
import pymunk.autogeometry
520

521
def create_complex_shape(vertices, body):
522
    """Create physics shapes for complex (possibly concave) polygon"""
523
    
524
    # Check if shape is already convex
525
    if pymunk.util.is_convex(vertices):
526
        # Simple case - create single polygon
527
        shape = pymunk.Poly(body, vertices)
528
        return [shape]
529
    else:
530
        # Complex case - decompose into convex parts
531
        convex_parts = pymunk.autogeometry.convex_decomposition(vertices, tolerance=1.0)
532
        
533
        shapes = []
534
        for i, part in enumerate(convex_parts):
535
            if len(part) >= 3:
536
                shape = pymunk.Poly(body, part)
537
                shape.collision_type = i  # Different collision types for each part
538
                shapes.append(shape)
539
        
540
        return shapes
541

542
# Example: L-shaped building
543
l_building = [
544
    (0, 0), (100, 0), (100, 60),     # Main rectangle
545
    (60, 60), (60, 100), (0, 100),   # Extension  
546
    (0, 0)                           # Close polygon
547
]
548

549
building_body = pymunk.Body(body_type=pymunk.Body.STATIC)
550
building_shapes = create_complex_shape(l_building, building_body)
551

552
space.add(building_body, *building_shapes)
553
```
554

555
### Procedural Level Generation
556

557
```python { .api }
558
import pymunk
559
import pymunk.autogeometry
560
import random
561
import math
562

563
def generate_cave_system(width, height, complexity=0.1):
564
    """Generate cave system using noise-based sampling"""
565
    
566
    def cave_sample(point):
567
        x, y = point
568
        
569
        # Multiple octaves of noise for complexity
570
        noise = 0
571
        amplitude = 1
572
        frequency = complexity
573
        
574
        for octave in range(4):
575
            # Simple noise approximation (replace with proper noise library)
576
            nx = x * frequency + octave * 100
577
            ny = y * frequency + octave * 100
578
            octave_noise = (math.sin(nx * 0.02) + math.cos(ny * 0.03)) * 0.5
579
            
580
            noise += octave_noise * amplitude
581
            amplitude *= 0.5
582
            frequency *= 2
583
        
584
        # Add some randomness
585
        noise += (random.random() - 0.5) * 0.2
586
        
587
        # Threshold for cave walls
588
        return 1.0 if noise > 0.1 else 0.0
589
    
590
    # Generate cave geometry
591
    bb = pymunk.BB(0, 0, width, height)
592
    polylines = pymunk.autogeometry.march_hard(
593
        bb, x_samples=width//10, y_samples=height//10,
594
        threshold=0.5, sample_func=cave_sample
595
    )
596
    
597
    # Create collision shapes
598
    cave_shapes = []
599
    for polyline in polylines:
600
        # Simplify cave walls
601
        simplified = pymunk.autogeometry.simplify_vertexes(polyline, tolerance=5.0)
602
        
603
        if len(simplified) >= 3:
604
            body = space.static_body
605
            shape = pymunk.Poly(body, simplified)
606
            shape.friction = 0.8
607
            shape.collision_type = 1  # Cave walls
608
            cave_shapes.append(shape)
609
    
610
    return cave_shapes
611

612
# Generate procedural cave level
613
cave_walls = generate_cave_system(800, 600, complexity=0.05)
614
space.add(*cave_walls)
615
```
616

617
### Polygon Optimization Pipeline
618

619
```python { .api }
620
import pymunk
621
import pymunk.autogeometry
622

623
def optimize_polygon_for_physics(vertices, target_vertex_count=8):
624
    """Optimize polygon for physics simulation performance"""
625
    
626
    # Step 1: Remove flat vertices 
627
    simplified_vertices = pymunk.autogeometry.simplify_vertexes(vertices, tolerance=1.0)
628
    
629
    # Step 2: If still too complex, use curve simplification
630
    if len(simplified_vertices) > target_vertex_count:
631
        simplified_vertices = pymunk.autogeometry.simplify_curves(
632
            simplified_vertices, tolerance=2.0
633
        )
634
    
635
    # Step 3: If still too complex, use convex hull
636
    if len(simplified_vertices) > target_vertex_count:
637
        simplified_vertices = pymunk.autogeometry.to_convex_hull(
638
            simplified_vertices, tolerance=1.0
639
        )
640
    
641
    return simplified_vertices
642

643
# Example: Optimize complex shape for physics
644
complex_shape = [(i, math.sin(i * 0.1) * 20) for i in range(100)]  # 100 vertices
645
optimized_shape = optimize_polygon_for_physics(complex_shape, target_vertex_count=6)
646

647
print(f"Reduced from {len(complex_shape)} to {len(optimized_shape)} vertices")
648

649
# Create optimized physics shape
650
body = pymunk.Body(10, pymunk.moment_for_poly(10, optimized_shape))
651
shape = pymunk.Poly(body, optimized_shape)
652
space.add(body, shape)
653
```
654

655
Pymunk's geometry processing capabilities provide powerful tools for converting complex artwork, images, and procedural data into efficient physics collision shapes, enabling sophisticated level generation and automatic collision boundary creation for games and simulations.