Delaunay Triangulation
Fast Delaunay triangulation implemented in Go.
This code was ported from Mapbox's Delaunator project (JavaScript).
Installation
$ go get -u github.com/fogleman/delaunay
Documentation
https://godoc.org/github.com/fogleman/delaunay
See https://mapbox.github.io/delaunator/ for more information about the Triangles
and Halfedges
data structures.
Usage
var points []delaunay.Point
// populate points...
triangulation, err := delaunay.Triangulate(points)
// handle err...
// use triangulation.Triangles, triangulation.Halfedges
Performance
3.3 GHz Intel Core i5
# of Points | Time |
---|---|
10 | 1.559Β΅s |
100 | 37.645Β΅s |
1,000 | 485.625Β΅s |
10,000 | 5.552ms |
100,000 | 79.895ms |
1,000,000 | 1.272s |
10,000,000 | 23.481s |