> ## Documentation Index
> Fetch the complete documentation index at: https://docs.opengeometry.io/llms.txt
> Use this file to discover all available pages before exploring further.

# Triangulate

> Convert polygons with holes into triangle meshes using ear-clipping algorithm

## Overview

The triangulate operation decomposes complex polygons (including those with holes) into a set of triangles. This is essential for rendering, collision detection, and finite element analysis. OpenGeometry uses the robust ear-clipping (earcut) algorithm with automatic projection to handle 3D polygons.

## Function Signature

```rust theme={null}
pub fn triangulate_polygon_with_holes(
    face_vertices: &Vec<Vector3>,
    holes: &Vec<Vec<Vector3>>,
) -> Vec<[usize; 3]>
```

Triangulates a polygon with optional holes into a set of triangles.

<ParamField path="face_vertices" type="&Vec<Vector3>" required>
  The outer boundary vertices of the polygon in order (either clockwise or counter-clockwise). Must have at least 3 vertices to form a valid polygon.
</ParamField>

<ParamField path="holes" type="&Vec<Vec<Vector3>>" required>
  A vector of hole polygons, each defined by its own ordered vertex list. Holes must be entirely contained within the outer boundary. Pass an empty vector if there are no holes.
</ParamField>

## Return Type

Returns `Vec<[usize; 3]>` - a vector of triangle indices, where each `[usize; 3]` array contains three indices into the combined vertex list (outer boundary vertices followed by all hole vertices).

### Index Mapping

* Indices `0..face_vertices.len()` refer to outer boundary vertices
* Indices `face_vertices.len()..` refer to hole vertices in order

Example:

* Outer boundary: 5 vertices (indices 0-4)
* Hole 1: 4 vertices (indices 5-8)
* Hole 2: 3 vertices (indices 9-11)

## How It Works

1. **Normal Calculation**: Computes the average normal of the polygon using Newell's method
2. **Projection Selection**: Chooses the best 2D projection plane based on the dominant axis:
   * If |Z| is dominant: Project to XY plane
   * If |X| is dominant: Project to YZ plane
   * Otherwise: Project to XZ plane
3. **Vertex Flattening**: Converts all 3D vertices to 2D coordinates in the chosen plane
4. **Hole Index Tracking**: Records the starting index of each hole in the flattened array
5. **Earcut Algorithm**: Runs the robust ear-clipping triangulation
6. **Winding Order Correction**: Automatically reverses triangles if needed for consistent orientation

## Code Examples

### Simple Triangle

```rust theme={null}
use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

let triangle = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(1.0, 0.0, 0.0),
    Vector3::new(0.5, 0.0, 1.0),
];

let triangles = triangulate_polygon_with_holes(&triangle, &vec![]);

assert_eq!(triangles.len(), 1);
assert_eq!(triangles[0], [0, 1, 2]);
```

### Quadrilateral Triangulation

```rust theme={null}
use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Rectangle
let quad = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(2.0, 0.0, 0.0),
    Vector3::new(2.0, 0.0, 2.0),
    Vector3::new(0.0, 0.0, 2.0),
];

let triangles = triangulate_polygon_with_holes(&quad, &vec![]);

// Quadrilateral splits into 2 triangles
assert_eq!(triangles.len(), 2);

// Example output:
// [[0, 1, 2], [0, 2, 3]]
```

### Polygon with a Hole

```rust theme={null}
use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Outer square
let outer = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(4.0, 0.0, 0.0),
    Vector3::new(4.0, 0.0, 4.0),
    Vector3::new(0.0, 0.0, 4.0),
];

// Inner square hole
let hole = vec![
    Vector3::new(1.0, 0.0, 1.0),
    Vector3::new(3.0, 0.0, 1.0),
    Vector3::new(3.0, 0.0, 3.0),
    Vector3::new(1.0, 0.0, 3.0),
];

let holes = vec![hole];
let triangles = triangulate_polygon_with_holes(&outer, &holes);

// Returns multiple triangles that avoid the hole
assert!(triangles.len() >= 8); // Minimum for a square with square hole

// Indices 0-3 are outer vertices, 4-7 are hole vertices
```

### Complex Polygon with Multiple Holes

```rust theme={null}
use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

fn create_hexagon(center: Vector3, radius: f64) -> Vec<Vector3> {
    let mut vertices = Vec::new();
    for i in 0..6 {
        let angle = (i as f64) * std::f64::consts::PI / 3.0;
        vertices.push(Vector3::new(
            center.x + radius * angle.cos(),
            center.y,
            center.z + radius * angle.sin(),
        ));
    }
    vertices
}

let outer = create_hexagon(Vector3::new(0.0, 0.0, 0.0), 5.0);
let hole1 = create_hexagon(Vector3::new(-1.5, 0.0, 0.0), 0.8);
let hole2 = create_hexagon(Vector3::new(1.5, 0.0, 0.0), 0.8);

let triangles = triangulate_polygon_with_holes(&outer, &vec![hole1, hole2]);

// Complex triangulation avoiding both holes
println!("Generated {} triangles", triangles.len());
```

### 3D Non-Planar Polygon (Auto-Projected)

```rust theme={null}
use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Polygon on a tilted plane
let tilted_polygon = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(1.0, 0.2, 0.0),
    Vector3::new(1.0, 0.3, 1.0),
    Vector3::new(0.0, 0.1, 1.0),
];

let triangles = triangulate_polygon_with_holes(&tilted_polygon, &vec![]);

// Automatically projects to best 2D plane and triangulates
assert_eq!(triangles.len(), 2);
```

## Visual Examples

```
Simple Polygon:                     Polygon with Hole:

    v3────v2                           v3────v2
    │╲     │                           │ ╲    │
    │  ╲   │        →                  │  h3─h2
    │    ╲ │                           │  │╲ ││
    v0────v1                           │  h0─h1
                                       │╱     │
    Triangles:                         v0────v1
    [0,1,2], [0,2,3]
                                       Triangles avoid hole


Multiple Holes:

    Outer                              Result
   ┌──────────┐                    ┌──────────┐
   │  h1   h2 │                    │╱╲╱╲╱╲╱╲╱│
   │  ○    ○  │       →            │╲╱╲╱╲╱╲╱╲│
   │          │                    │╱╲╱╲╱╲╱╲╱│
   └──────────┘                    └──────────┘
```

## Winding Order

The function automatically corrects winding order:

* Analyzes the first triangle's orientation
* Reverses all triangles if winding is inconsistent
* Ensures consistent face normals for rendering

## Implementation Details

### Source Location

`~/workspace/source/main/opengeometry/src/operations/triangulate.rs:3`

### Algorithm

Uses the **earcutr** library, which implements:

* Fast ear-clipping triangulation
* Robust handling of self-touching vertices
* Support for complex polygons with holes

### Projection Axis Selection

```rust theme={null}
if normal.z.abs() > normal.x.abs() && normal.z.abs() > normal.y.abs() {
    // Project to XY plane (indices 0, 1)
} else if normal.x.abs() > normal.y.abs() {
    // Project to YZ plane (indices 1, 2)
} else {
    // Project to XZ plane (indices 0, 2)
}
```

### Normal Calculation (Newell's Method)

```rust theme={null}
for i in 0..vertices.len() {
    let p1 = &vertices[i];
    let p2 = &vertices[(i + 1) % vertices.len()];
    normal.x += (p1.y - p2.y) * (p1.z + p2.z);
    normal.y += (p1.z - p2.z) * (p1.x + p2.x);
    normal.z += (p1.x - p2.x) * (p1.y + p2.y);
}
```

## Edge Cases

* **Insufficient Vertices**: Returns empty vector if outer boundary has \< 3 vertices
* **Degenerate Polygons**: May produce no triangles or unexpected results
* **Self-Intersecting**: Earcut algorithm handles some cases but behavior is undefined
* **Holes Outside Boundary**: Results are undefined; ensure holes are contained
* **Non-Planar Polygons**: Automatically projected, but significant non-planarity may cause artifacts

## Performance Considerations

* Time Complexity: O(n log n) average case for earcut algorithm
* Memory: O(n) for vertex storage and triangle output
* Efficient for polygons with hundreds of vertices
* Minimal overhead from projection

## Common Use Cases

* **Rendering**: Convert arbitrary polygons to GPU-compatible triangle meshes
* **Physics**: Generate collision meshes from polygon boundaries
* **CAD/CAM**: Prepare geometry for manufacturing or simulation
* **GIS**: Triangulate geographic regions with exclusion zones
* **Architecture**: Process floor plans with room boundaries and obstacles

## See Also

<CardGroup cols={2}>
  <Card title="Extrude" icon="arrows-up-down" href="/OpenGeometry/api/operations/extrude">
    Often used after triangulation to create 3D geometry
  </Card>

  <Card title="Sweep" icon="route" href="/OpenGeometry/api/operations/sweep">
    Creates surfaces that may need triangulation
  </Card>
</CardGroup>