Title:  Optimized Incremental Delaunay
Brief:  Classic triangulation algorithm to use for one by one insertion of points, with SIMD and caching.
Date:   1694711563
Tags:   Programming, Zig, Generation
CSS:    /style.css

![](/articles/incremental-delaunay/web.png)

Based on [this paper](https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect13-delaun-alg.pdf)

Full usable isolated code is [here](/articles/incremental-delaunay/incremental-delaunay.zig.txt).

### Usage example ###
```zig
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer std.debug.assert(gpa.deinit() == .ok);
var triangulator = try Delaunay.Builder.init(gpa.allocator(), Delaunay.Area{-1, -1, 1, 1});

const point_count = 128;

var prng = std.rand.DefaultPrng.init(123123);
const rng = prng.random();
for (0..point_count) |_| {
    const x = rng.float(f32) * 2 - 1;
    const y = rng.float(f32) * 2 - 1;
    try triangulator.insertAtRandom(Delaunay.Vertex{ x, y }, rng);
}

var triangles: [point_count * 2 + 2]gfx.triangle.ScreenspaceTriangle = undefined;
for (&triangles, triangulator.triangles.items) |*out, in| {
    out.a = triangulator.vertices.items[in.points[0]];
    out.b = triangulator.vertices.items[in.points[1]];
    out.c = triangulator.vertices.items[in.points[2]];
}
```