Earcutr

This is a port of the MapBox company's Earcut computer code ( see https://github.com/mourner, Volodymyr Agafonkin) , which triangulates polygons. Please see https://github.com/mapbox/earcut for more information about the original javascript code. This port is to the Rust computer language, and is single-threaded.

This port is not affiliated with MapBox in any way and no endorsement is implied. Also please note MapBox has their own Rust port of this code, no claim is made this is better than theirs. The goal is to have identical output to MapBox's Javascript code however several updates have been made to MapBox js and this Rust port is a few years behind.

Please also note someone made this into a Crate (not me) for convenience, please check crates.io

Usage

extern crate earcutr;
var triangles = earcutr::earcut(&vec![10,0, 0,50, 60,60, 70,10],&vec![],2);
println!("{:?}",triangles);  // [1, 0, 3, 3, 2, 1]

Signature:

earcut(vertices:&vec<f64>, hole_indices:&vec<usize>, dimensions:usize).

• vertices is a flat array of vertex coordinates like [x0,y0, x1,y1, x2,y2, ...].
• holes is an array of hole indices if any (e.g. [5, 8] for a 12-vertex input would mean one hole with vertices 5–7 and another with 8–11).
• dimensions is the number of coordinates per vertex in the input array. Dimensions must be 2.

Each group of three vertex indices in the resulting array forms a triangle.

// triangulating a polygon with a hole
earcutr::earcut(
   &vec![0.,0., 100.,0., 100.,100., 0.,100.,  20.,20., 80.,20., 80.,80., 20.,80.],
   &vec![4] , 2 );
// result: [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]

If you pass a single vertex as a hole, Earcut treats it as a Steiner point. See the 'steiner' test under ./tests/fixtures for an example input, and the test visualization under ./viz.

After getting a triangulation, you can verify its correctness with earcutr.deviation:

let deviation = earcutr.deviation(&data.vertices, &data.holes, data.dimensions, &triangles);

Deviation returns the relative difference between the total area of triangles and the area of the input polygon. 0 means the triangulation is fully correct.

Flattened vs multi-dimensional data

If your input is a multi-dimensional array you can convert it to the format expected by Earcut with earcut.flatten. For example:

let v = vec![
  vec![vec![0.,0.],vec![1.,0.],vec![1.,1.],vec![0.,1.]], // outer ring
  vec![vec![1.,1.],vec![3.,1.],vec![3.,3.]]        // hole ring
];
let (vertices,holes,dimensions) = earcutr::flatten( &v );
let triangles = earcutr::earcut(&vertices, &holes, dimensions);

The GeoJSON Polygon format uses multi-dimensional data in a text based JSON format. There is example code under tests/integration_test.rs on how to parse JSON data. The test/fixtures test files are all multi-dimensional .json files.

How it works: The algorithm

The library implements a modified ear slicing algorithm, optimized by z-order curve hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data.

It's based on ideas from FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held and Triangulation by Ear Clipping by David Eberly.

Visual example

For example a rectangle could be given in GeoJSON format like so:

[ [ [0,0],[7,0],[7,4],[0,4] ] ]

This has a single contour, or ring, with four points. The way the points are listed, it looks 'counter-clockwise' or 'anti-clockwise' on the page. This is the 'winding' and signifies that it is an 'outer' ring, or 'body' of the shape.

 _______
 |     |
 |     |
 |     |
 |_____|

Now let's add a hole to the square.:

[ 
  [ [0,0],[7,0],[7,4],[0,4] ],   
  [ [1,1],[3,1],[3,3] ] 
]

This has two contours (rings), the first with four points, the second with three points. The second has 'clockwise' winding, signifying it is a 'hole'.

_______
|     |
|  /| |
| /_| |
|_____|

After 'flattening', we end up with a single array:

data [ 0,0,7,0,7,4,0,4,1,1,3,1,3,3  ]
holeindexes: [ 4 ]
dimensions: 2

The program will interpret this sequence of data into two separate "rings", the outside ring and the 'hole'. The rings are stored using a circular doubly-linked list.

The program then "removes" the hole, by essentially adding a "cut" between the hole and the polygon, so that there is only a single "ring" cycle.

     _______
     |     |
     |  /| |
cut> |_/_| |
     |_____|

The program also automatically 'corrects' the winding of the points during input so they are all counter-clockwise.

Then, an "ear cutting" algorithm is applied. But not just any earcutting algorithm.

Normally, an ear-cutter algorithm works by finding a potential ear, or a "candidate" ear, by looking at three consecutive points on the polygon. Then, it must make sure there are no other points "inside" the ear.

In order to do this, it must iterate through every point in the polygon, so if your polygon has 15,000 points then it must go through all of them looking to see if each one is inside the potential ear. Each ear check takes a dozen or two calculations, typically using a test like the wedge product between each side of the ear, and the point to check - if the point is on the right-hand-side (Wedge is less than zero) of each side, it's inside the ear, and so the ear cannot be cut. The algorithm then moves on to the next potential ear.

Z-order curve

Z-order hashing allows the number of 'is in ear' checks to be drastically cut down. How? Instead of running the "is in ear" code on each other point in the polygon, it is able to only check points 'nearby' the ear. This is accomplished in the following manner:

Step 1: before earcut, each point of the polygon is given a coordinate on the z-order (Morton) curve through the space of the bounding box of the polygon. This is a type of space-filling curve strategy that has been explored in many geometry algorithms. Pleas see https://en.wikipedia.org/wiki/Z-order_curve

Step 2: The clever bit is that if you want to search within a limited rectangle inside the space filled by the Z-order curve, you can relatively easily figure out which points are inside that box by looking at their position on the z-order curve.. in other words their z index. The code stores the index as ".z" in each node of the linked list that represents a vertex of the polygon.

To be more specific, Z-order curves have a special thing about them, when you pick a limited rectangle inside, you can iterate along the z-curve from the "lowest" corner to the "highest" corner and be guaranteed to hit every 2d point inside that rectangle.

For example, in a 4x4 morton square, there are 16 Morton codes.

 x-----0--1--2--3-->
y|0    0  1  4  5
 |1    2  3  6  7
 |2    8  9 12 13
 |3   10 11 14 15
\|/

Going from z-code 0 to z-code 6, 0 1 2 3 4 5 6, takes us through every 2 dimensional point between 0,0, where 0 lives, and 2,1, where 6 lives. It also goes through 3,0 but nothing is perfect.

Let's say you pick 2,2 and 3,3. The z code at the lowest point is 12, and the highest is 15. So your z-iteration would be 12, 13, 14, 15, which covers the rectangle from 2,2 to 3,3.

So, that is how it gets away without checking every point in the polygon to see if they are inside the ear. It draws a rectangle around the ear, it finds the lowest and highest corner of that rectangle, and iterates through the z-curve to check every 2-d point that is 'near' the polygon ear.

As you can imagine, if 14,000 of your points in your polygon are outside this box, and only 1000 are in the box, thats quite a bit less math and calculation to be done than if you had to iterate through 15,000 points.

Additional massaging

If the straightforward earcutting fails, it also does some simple fixes,

• Filtering points - removing some collinear and equal points

• Self intersections - removing points that only tie a tiny little knot in the polygon without contributing to its overall shape (and also make it not-simple)

• Split bridge - actually split the polygon into two separate ones, and try to earcut each.

Data examples are included under tests/fixtures in json files. Visualization of test results is generated under viz/testoutput and can be viewed in a web browser by opening viz/viz.html

Coordinate number type

The coordinate type in this code is 64-bit floating point. Note that 32-bit floating point will fail the tests because the test data files have numbers that cannot be held with full precision in 32 bits, like the base 10 number 537629.886026485, which gets rounded to 537629.875 during conversion from base 10 to 32-bit base 2.

Tradeoffs

This triangulator is built primarily as an exercise in porting javascript to Rust. However some minor details of the implementation have been modified for speed optimization. The code is supposed to produce exacly the same output as the javascript version, by using the large amount of test data supplied with the original javascript code. The speed is comparable with Mapbox's C++ version of earcut, earcut.hpp, except for input of very small polygons where the speed is