## delaunator

A really fast JavaScript library for Delaunay triangulation of 2D points.

## Interactive Demo

## Example

```
var points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], ...];
var delaunay = new Delaunator(points);
console.log(delaunay.triangles);
// [623, 636, 619, 636, 444, 619, ...]
```

## API Reference

#### new Delaunator(points[, getX, getY])

Constructs a delaunay triangulation object given an array of points (`[x, y]`

by default). `getX`

and `getY`

are optional functions of the form `(point) => value`

for custom point formats. Duplicate points are skipped.

#### delaunay.triangles

A flat `Int32Array`

array of triangle indices (each group of three numbers forms a triangle).

## Performance

Benchmark results against four fastest other libraries (`bench.js`

on Macbook Pro Retina mid-2012, Node v7.9.0):

#### Uniform distribution

library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000 |
---|---|---|---|---|---|---|---|

delaunator | 25ms | 32ms | 105ms | 168ms | 350ms | 974ms | 2.46s |

faster-delaunay | 78ms | 140ms | 328ms | 776ms | 1.74s | 3.87s | 6.99s |

incremental-delaunay | 81ms | 154ms | 428ms | 874ms | 1.74s | 4.3s | 9.03s |

d3-voronoi | 154ms | 250ms | 534ms | 1.19s | 2.7s | 7.37s | 18.36s |

delaunay-fast | 136ms | 386ms | 1.18s | 3.03s | 7.95s | 28.2s | 76.96s |

#### Gaussian distribution

library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000 |
---|---|---|---|---|---|---|---|

delaunator | 24ms | 27ms | 109ms | 170ms | 327ms | 941ms | 2.03s |

faster-delaunay | 76ms | 172ms | 291ms | 692ms | 1.19s | 3.46s | 6.36s |

incremental-delaunay | 74ms | 154ms | 410ms | 806ms | 1.67s | 4.27s | 8.3s |

d3-voronoi | 164ms | 264ms | 522ms | 1.16s | 2.67s | 7.64s | 18.62s |

delaunay-fast | 152ms | 340ms | 1.19s | 3.2s | 8.37s | 30.03s | 82.05s |

## Papers

The algorithm is based on ideas from the following papers:

- A simple sweep-line Delaunay triangulation algorithm, 2013, Liu Yonghe, Feng Jinming and Shao Yuehong
- S-hull: a fast radial sweep-hull routine for Delaunay triangulation, 2010, David Sinclair
- A faster circle-sweep Delaunay triangulation algorithm, 2011, Ahmad Biniaz and Gholamhossein Dastghaibyfard