DEV Community: Nail Sharipov

Earcut64: Zero-Allocation Triangulation for Tiny Polygons

Nail Sharipov — Mon, 16 Jun 2025 12:24:41 +0000

Earcut looks like a textbook triangulation algorithm, yet it can outperform more complex methods on small, simple polygons.

By limiting ourselves to ≤ 64 vertices we can keep everything on the stack, encode the contour in a single u64 to get maximum performance.

Why Earcut at All?

Earcut is almost a teaching example: pick any non-self-intersecting polygon, find an "ear" (three consecutive vertices that form an empty inner triangle), cut it off, repeat.

Simple? Yes. Slow? Sometimes. But on contours with few points Earcut can be the fastest tool in the shed, as my benchmarks against iTriangle and Mapbox implementations have shown.

That observation sparked an idea: what if we crafted a micro-optimized version of Earcut specialised for single-contour shapes with ≤ 64 vertices? No heap, one bit-mask, maximum speed.

1. How Classic Earcut Works

Walk through every triple of consecutive vertices.
For each triple check:
- The triangle is oriented CCW.
- It contains no other vertices inside.
If both hold, you found an ear—remove its middle vertex and continue.

Worst-case complexity: O(N³). In practice most polygons behave better (closer to O(N²)) because ears appear quickly.

2. "Bigger-Ear" Variant

Instead of cutting one triangle at a time, we try to grow a larger convex "ear" that can be triangulated in bulk.

Why convex?

Triangulating a convex polygon is trivial.
Checking "is point inside?" is cheaper.

Empty-check methods

Even-Odd ray
Cross-product sign — faster because you can abort on the first sign flip.

All cross-products same sign - point is inside
Sign flips - point is outside

3. Finding the Maximum Ear

If the convex ear still hides internal points, rewind from the tail until they disappear.
Key trick: keep the first vertex fixed—the main sweep will revisit it anyway.

To pick the "nearest " internal point:

Build vectors from the first vertex to every candidate.
Compare them pair-wise via cross-product (arccos is both slow and imprecise).
The vector with the smallest positive angle to the first edge defines the limit.

Cut everything up to that limit and triangulate locally.

4. Speed Hacks

Bounding-box filter — drop points obviously outside the ear’s AABB.
Early rejection — if the first triangle is already dirty, skip the ear.
Heap of nearest points — we only care about the closest violators.
Incremental testing — check the next point starting from the last valid triangle.

Optimized pass — step‑by‑step

The image above illustrates how the incremental filter + heap strategy works:

Gray points — vertices discarded by the ear’s axis‑aligned bounding box.
Orange points — remaining candidates sorted by angle to the first edge(red).
Green segments — final ear triangles kept in the mesh.

Candidate 1: its vector falls inside triangle 4, yet the point itself lies outside the ear - keep scanning.

Candidate 2: tested starting from triangle 4, ends up in triangle 5 and is still outside.

Candidate 3: tested from triangle 5, reaches triangle 6 and finally lands inside — search stops.

Result: the ear is triangulated using triangles 1 – 5.

No internal point found?

Two scenarios:

All candidates examined - no obstructing vertices; cut the ear entirely.
Heap overflow - only part of the candidates checked; seen points are outside but we lack guarantees for the rest. Cut only up to the last verified triangle — safe but maybe sub‑optimal.

This compromise preserves speed without sacrificing robustness. Experiments showed that a heap of 1–5 nearest points offers the best trade-off; larger heaps slow things down without benefit.

5. Earcut64: Stack-Only, Bit-Mask Navigation

For contours of ≤ 64 points, store presence bits in a single u64

0b110111 - vertex 3 was removed

Bit math for Navigation:

impl BitMaskNav for u64 {
    #[inline(always)]
    fn ones_index_to_end(index: usize) -> Self {
        debug_assert!(index <= 64);
        let shift = index & 63;
        u64::MAX << shift   // 1-bits from index (inclusive) to the end
    }

    /// Finds the next available bit (index of vertex) after `after`, wrapping if needed
    #[inline(always)]
    fn next_wrapped_index(self, after: usize) -> usize {
        debug_assert!(after <= 63);
        let front = self & u64::ones_index_to_end(after + 1);
        if front != 0 {
            front.trailing_zeros() as usize
        } else {
            self.trailing_zeros() as usize
        }
    }
}

Filtering internal points

let candidates = available & !ear_indices;
/*
available   – all remaining vertices
ear_indices – vertices currently forming the ear
candidates  – potential internal points
*/

Zero allocations, zero copies - everything lives in registers or on the stack.

6. Benchmarks

Below are average runtimes (µs) from the first two public tests on my benchmark page. Hardware: 3 GHz 6‑core Intel i5‑8500.

Star

Count	Earcut64	Monotone	Earcut Rust	Earcut C++
8	0.28	0.5	0.73	0.42
16	0.64	1.6	1.23	0.5
32	1.61	3.9	2.6	1.2
64	4.45	8.35	5.6	3.3
128	-	17.8	12.6	8.4
256	-	37.5	29.1	22.9
512	-	79.7	80.7	72.7
1024	-	172	259	209
2048	-	388	736	641
4096	-	898	3158	2804
8192	-	1824	13435	11479
16384	-	3846	51688	44017

Spiral

Count	Earcut64	Monotone	Earcut Rust	Earcut C++
8	0.35	0.7	0.77	0.42
16	1.2	1.4	1.66	0.77
32	4.2	3.0	6.25	3.4
64	16.1	6.2	18.6	19.8
128	-	12.8	71.6	66
256	-	26.7	295	306
512	-	55.5	1230	1438
1024	-	120	5301	7595
2048	-	279	22682	50140
4096	-	685	96933	376060
8192	-	1435	416943	3.7kk
16384	-	3080	1812147	43.4kk

Note: Earcut64 and Monotone in these tables are both algorithms from my open‑source Rust library iTriangle.

Benchmark takeaway

Ear-based triangulators shine on simple shapes and quickly fall off on pathological ones — exactly what theory predicts.
Mapbox Earcut (C++) is the fastest in the 16 – 512‑point range for simple contours, which makes sense given its map‑rendering focus.
Earcut64 holds its own and even outperforms the professional library in several small‑polygon cases.
The pure‑Rust Earcut port stays surprisingly strong on very complex contours; within the Earcut family.

7. Why It Matters — and What’s Next?

Earcut64 it’s fully stack-allocated, zero-copy, and designed for maximum inlining by the compiler.

That makes it a perfect candidate for GPU porting.

But more importantly — it's part of iTriangle, an integer-based triangulation library validated against billions of randomized tests, from clean stars to extreme degeneracies.

iTriangle guarantees watertight, non-overlapping triangle meshes — no crashes, no invalid output, no surprises and it's a perfect solution for:

embedded systems
real-time rendering
EDA/CAD/GIS pipelines
and WebAssembly-based tools

Try it today:

💬 Got questions or feedback? Drop a comment below or open an issue.

Monotone Triangulation. Practical Advice.

Nail Sharipov — Sat, 10 May 2025 13:11:37 +0000

It all started innocently enough.

Back in 2009, I just wanted to port Earcut to Flash for a mini-game I was working on. And honestly? It worked — for a while. But over time, I realized that simple solutions tend to fall apart the moment you try to push them to their limits.

That’s when I dove into the theory - digging through research papers, YouTube tutorials, and whatever else I could find. One of the most helpful resources was a book by A.V. Skvortsov. Eventually, I landed on the classic approach: decomposing a polygon into monotone pieces. It seemed obvious. And oh - I hit every possible wall while trying to make it work.

The first big insight? Replace float with int. That alone got me almost there. But the algorithm was still fragile. Really fragile. Self-intersections, collinear edges, holes touching the outer contour, degenerate points — any of these could break it at any moment. It was functional, but I didn’t like it.

Years passed. I wrote iOverlay, a Boolean operations library that can clean up self-intersections and prepare input data properly. And with that tool in hand, I went back to my old triangulator — this time, with the intent to rebuild it from the ground up.

Everything went smoother. I knew what to expect. And once you can trust your input data, it's like a rainbow lights up in the sky.

Eventually, I realized that monotone partitioning is just an abstraction — and I could drop it entirely. I also polished the Delaunay condition until it shined.

That’s how my custom sweep-line triangulation was born. It's not only fast and simple — it’s incredibly stable. I’ve run over a billion randomized tests. And the output? Bit-for-bit consistent.

Let’s Get to It

As I mentioned earlier, input format is critical for this kind of algorithm. So let’s lock down the strict requirements right away:

No self-intersections
Contours may only touch each other at a single point
Outer contours must be counter-clockwise
Holes must be clockwise

These are non-negotiable. If your input doesn’t follow these rules, fix it first - iOverlay can help with that.

Step 1: Pick a Sweep Direction

Since this is a sweep-line algorithm, the first thing we need is to decide the sweep direction. I prefer a left-to-right sweep - moving the line along the X-axis.

We sort all vertices based on their coordinates:

First by x
If x is the same, then by y

Edge Case: Touching Points

One subtle problem arises when multiple contours converge at a single point - say, an outer contour and one or more holes. There can be an infinite number of variations, but they all have something in common:

The number of edges at such a point is always even,
If you walk around the point, the edges will alternate: incoming / outgoing / incoming / outgoing...

Step 2: Vertex Structure

Each vertex needs to "know" its immediate neighbors along the contour. So we store both prev and next references.

struct ChainVertex {
    index: usize,     // ID of the logical point
    this: Point,      // Coordinates of the current vertex
    next: Point,      // Next point in the contour
    prev: Point,      // Previous point in the contour
}

index: the unique ID for the logical point. Identical points across contours (e.g., touching corners) share the same index.
this: coordinates of the current vertex.
prev / next: neighbor vertices in the same contour (either outer or hole).

Step 3: Vertex Classification

Now comes a key part: classifying each vertex.
Sweep-line algorithms rely heavily on this step to decide how each vertex should be handled.

Classification depends on:

The internal angle at the vertex
The relative vertical position of neighbors
The winding direction of the contour

Here are the all types:

Start - The beginning of a monotone polygon
End - The end of a monotone polygon
Split - A vertex that splits the monotone polygon
Merge - A vertex where two monotone polygons merge back together
Join - A neutral vertex — equal to prev or next

Step 4: Sweep and On-the-Fly Triangulation

Tracking Active Sections

We represent a monotone polygon as a section, which can be:

just a point (newly started polygon)
a chain of edges.

Each section has a support edge (drawn in blue), used as a key in a balanced tree. This edge is either:

the next contour edge, or
helper edge (bridge between polygon parts)

Section structure in code:

enum Content {
    Point(IndexPoint),
    Edges(Vec<TriangleEdge>),
}

struct Section {
    sort: VSegment,     // Sorting key in the tree
    content: Content,
}

We keep all sections in a balanced tree ordered vertically by their support edge. I’ve already explained how to sort vertical segments in the article. I won’t repeat it here.

Every time we pop a vertex from the sorted list, we must decide:

Which section does it belong to?

To answer, we search the tree for the closest section below the vertex.

Example: Sections A, B, and C are active. P belongs to B.

Triangle Construction

Once we find the section, we try to form new triangles. Sections keep their edge chains in counter-clockwise order. For each edge, we test if a new triangle (with the current point) forms a counter-clockwise triangle:

if yes, we add the triangle
then update the edge chain

Example: Section has edges AC and CD. P forms triangle CDP, but not ACP. The new section contains edges AC and CP, with PE as a new support edge.

Edge structure which also retain triangle info:

struct TriangleEdge {
    a: IndexPoint,
    b: IndexPoint,
    kind: EdgeType,  // needed to find triangle neighbors
}

We will collect our triangles in a structure like:

struct Triangle {
    vertices: [IndexPoint; 3],
    neighbors: [usize; 3],
}

Each triangle is stored with its vertices in counter-clockwise order. We also track neighboring triangles — one per edge.
We store neighbors by index, in the slot opposite to the corresponding edge.

Example: Triangle ABC has neighbors [2, None, 1]

- neighbor across edge (A)BC → triangle 2
- neighbor across edge (B)CA → none
- neighbor across edge (C)AB → triangle 0

Phantom edges

Sometimes, while building triangles, an internal edge is added before it has a neighbor.
We call this a phantom edge — it temporarily "hangs" in the air.

On the first visit, such an edge is converted into a normal internal edge by connecting it to the new triangle.

Example. Edge 3–5 was added as a phantom.

Step 5 (optional): Introduction to Delaunay

At this point, we already have a valid triangulation. But if we want to improve triangle quality, we can enforce the Delaunay condition.

The Delaunay condition ensures that no vertex lies inside the circumcircle of any triangle.

The process is straightforward:

for each edge shared by two adjacent triangles, we check the Delaunay condition.
if the condition is violated, we remove the shared edge.
we then re-triangulate the four involved points by connecting the two opposite vertices (edge flip).
this process is repeated until no violations remain.

I won’t go into the geometric predicate here — I’ve already covered it in a dedicated article with animations.

Example Non-Delaunay triangles must be flipped into Delaunay triangles

Why does it work?

Each flip reduces the largest (often obtuse) angle between the triangle pair.
This makes the process monotonically convergent — it’s guaranteed to terminate.

In floating-point implementations, this is where bugs can appear.
Due to rounding errors, some flips can alternate endlessly. This is a classic issue, often referred to as the "regular hexagon problem".

But with int or fixed-point logic, the situation improves dramatically:

the Delaunay check becomes strict and exact
all operations are deterministic
no infinite loops — ever

That’s the power of integer-based geometry.

I'll Take It

If you’re interested in trying this in action, check out iTriangle — the Rust library where all of this comes together.

Beyond what I’ve covered here, it includes:

Tessellation
Convex polygon partitioning
Centroid construction
Steiner points

You can experiment with interactive demos:

And if you're curious about performance, take a look at the benchmarks results — compared against other popular triangulation libraries.

2D Polygon Boolean Operations

Nail Sharipov — Tue, 24 Sep 2024 10:27:26 +0000

Boolean operations on 2D polygons — union, intersection, difference, and XOR — are crucial for applications in computer graphics, CAD, and GIS. These operations allow us to manipulate complex shapes, but the challenge is implementing them efficiently while maintaining stability and accuracy.

Choosing the Right Arithmetic

Selecting the right arithmetic is key to balancing performance and precision in geometry algorithms. After considering the pros and cons of floating-point and fixed-point arithmetic, I opted for i32 for point coordinates. Here's why:

Fixed-Point (i32) Pros:

No rounding errors, ensuring consistent and exact values.
Simplifies comparisons like determining if a point lies on a line or if two lines are parallel.
Results are deterministic across platforms, making debugging easier.

i32 strikes a balance between memory efficiency and precision, while still allowing dot and cross products to fit comfortably into i64, avoiding overflow concerns.

Problem Statement

Imagine we have two bodies: A (red) and B (blue). Each body is defined by a group of contours - a list of successively connected vertices. These contours are always closed and can allow self-intersections.

Our goal is to compute a new body C (green), which represents one of the following Boolean combinations:

Union: C = A ∪ B
Intersection: C = A ∩ B
Exclusion: C = A ⊕ B
Difference: C = A - B or B - A

Overlay Graph

Let's start by manipulating bodies A and B to create an overlay graph that will allow us to perform Boolean operations.

The steps to construct this graph are as follows:

Split segments:
Break down all the segments of both bodies A and B so that there are no self-intersections. This ensures each contour is composed of non-intersecting segments.
Tag segments with metadata:
For each segment, store additional information indicating whether it belongs to body A, body B, or both, and record which side of the segment is part of the body.
Combine everything into a graph structure:
This graph consists of nodes and links. Each node represents a point (an intersection or endpoint), and each link represents a segment between two points, along with metadata about which body the segment belongs to.

struct OverlayGraph {
    nodes: Vec<Node>,     // A list of nodes (points) in the graph
    links: Vec<Link>      // A list of links (edges) connecting the nodes
}

struct Node {
    indices: Vec<usize>   // Indices pointing to links connected to this node
}

struct Link {
    a: IdPoint            // The start point of the segment
    b: IdPoint            // The end point of the segment
    fill: SegmentFill     // Metadata about which sides belong to body A or B
}

type SegmentFill = u8;

In this structure:

Nodes represent the points of intersection or the endpoints of segments.
Links represent the segments themselves, connecting two nodes and carrying information about whether they belong to A, B, or both.

By organizing the segments and their metadata into an overlay graph, we can now efficiently extract contours based on Boolean filters (union, intersection, difference, etc.).

You can explore this concept with an example in the online editor.

Boolean Filter

Now that we've constructed the overlay graph, let's see how different Boolean operations are applied to bodies A and B. We will extract the resulting body C for each operation based on segment properties within the overlay graph.

Difference, C = A - B

The resulting segments of C must not be inside body B and must belong to body A on one side.
The side associated solely with body A will represent the inner part of the resulting shape.

Difference, C = B - A

The resulting segments of C must not be inside body A and must belong to body B on one side.
The side associated solely with body B will represent the inner part of the resulting shape.

Union, C = A or B

The resulting segments of C must belong to either body A or body B, or to both.
The opposite side of each segment must not belong to anybody.
The side associated with one of the bodies will represent the inner part of the resulting shape.

Intersection, C = A and B

The resulting segments of C must belong to both bodies A and B.
The opposite side of each segment must not belong to both bodies simultaneously.
The side associated with both bodies A and B will represent the inner part of the resulting shape.

Exclusion, C = A xor B

The resulting segments of C must belong to either body A or body B, but not to both simultaneously.
The opposite side of each segment must either belong to both bodies or to neither.
The side associated with one of the bodies (A or B) will represent the inner part of the resulting shape.

Extract Shapes

Once we apply the desired Boolean filter to the Overlay Graph, we can begin extracting contours for the resulting shape.

Building a Contour

The algorithm follows a systematic process to build both outer and inner contours from the graph:

Start with the leftmost node:
The algorithm begins by selecting the leftmost node in the graph. From there, it looks for the topmost segment connected to this node.
Traverse along segments:
The algorithm proceeds by traversing the selected segment to the next node. At each node, the next segment is selected by rotating around the current node in a counterclockwise direction, choosing the nearest segment that hasn't been visited yet.
Mark segments as visited:
To prevent revisiting segments, each one is marked as visited when traversed.
Complete the contour:
This process continues until a full loop is formed, completing the contour. Depending on the orientation of the segments, the contour will be classified as either outer or inner.

Outer contours are extracted in a clockwise direction.
Inner contours are extracted in a counterclockwise direction.

Define Contour

A shape is defined as a group of contours, with the first contour always being an outer contour. Any subsequent contours within the shape are classified as inner contours.

To define a contour, the algorithm begins by identifying the leftmost and topmost segment in the contour. The classification of the contour is determined as follows:

If the left-top side of the segment is classified as the outer side, then the contour is an outer contour.
If the left-top side of the segment is classified as the inner side, then the contour is an inner contour.

This method ensures each contour is correctly classified based on its orientation in 2D space.

Define Shape

A shape is defined as a group of contours, where the first contour is always an outer contour, and the subsequent contours (if any) are inner contours.

Matching Contours

To match inner contours to their corresponding outer contours:

Draw a line downward from any point on the inner (target) contour.
Identify the first segment encountered along the line that does not belong to the target contour.
If the segment belongs to an outer contour, that contour is the container for the target contour.
If the segment belongs to another inner contour, the container of that inner contour is also the container for the target contour.

Define Segment under Point

To determine whether a segment AB is below a point P, one may be tempted to compute the value of ym at the point of intersection M, where a vertical line is dropped from P onto AB (i.e., xp = xm):

ym=ya−ybxa−xb⋅(xm−xa)+yay_{m} = \frac{y_{a} - y_{b}}{x_{a} - x_{b}}\cdot(x_{m} - x_{a}) + y_{a}

However, this method can introduce precision issues due to the division operation involved.

A more reliable method involves using the order of traversal around the vertices of the triangle APB. If segment AB is below point P, the vertices A, P, and B will appear in a clockwise order.

This method uses the cross product of vectors PA and PB:

\times b = a_x b_y - a_y b_x

Since this method avoids division, it eliminates precision issues, making it stable for determining whether a segment is below a point.

Selecting the Closest Segment under Point

When multiple segments are positioned below point P, the next challenge is to identify which segment is closest to point P. This scenario can be categorized into three cases based on the relative configuration of the segments:

Left Case

When both segments share a common left vertex A, we compare the positions of their right endpoints. If the vertices B0, B1, and A form a clockwise pattern, then AB0 is closer to P than AB1.

Right Case

When both segments share a common right vertex B, we check the positions of their left endpoints. If the vertices A0, A1, and B form a clockwise pattern, then A1B is closer to P than A0B.

Middle Case

In this case, one of the vertices (e.g., A1 or B0) lies inside the opposite segment. We use the point-segment comparison method to determine which of the segments is closer to P.

Final Solution

The final result of polygon Boolean operations is typically grouped by outer contours. One outer contour may contain several holes, and it is essential to match these correctly. In many cases, the direction of the vertices in outer and inner contours is opposite: the outer contour is listed in a clockwise direction, while the inner contours (holes) are listed counterclockwise.

This opposite orientation is especially useful in polygon processing algorithms like triangulation or bottleneck detection, as it simplifies the logic by removing the need to distinguish between segments belonging to outer or inner contours.

What Was Left Behind

Some important aspects were only briefly mentioned:

Constructing an Overlay Graph: The process of reliably building the graph, handling intersections, and splitting segments is complex and deserves a deeper dive in a separate article.
Graph Convergence: Ensuring the overlay graph converges correctly requires careful data handling to avoid errors during Boolean operations.
Filling Rules (EvenOdd/NonZero): The filling rule can significantly affect the outcome of polygon operations, especially in complex or overlapping shapes.

Implementing in iOverlay

These concepts are fully implemented in iOverlay, a library designed for efficient 2D polygon Boolean operations. iOverlay delivers stable, deterministic results and is available under the MIT license across multiple platforms: