delaunay

README

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

Documentation

Index

• type Point
  • func ConvexHull(points []Point) []Point
• type Triangulation
  • func Triangulate(points []Point) (*Triangulation, error)
  • func (t *Triangulation) Validate() error

Types

type Point

type Point struct {
	X, Y float64
}

func ConvexHull

func ConvexHull(points []Point) []Point

ConvexHull returns the convex hull of the provided points.

type Triangulation

type Triangulation struct {
	Points     []Point
	ConvexHull []Point
	Triangles  []int
	Halfedges  []int
}

func Triangulate

func Triangulate(points []Point) (*Triangulation, error)

Triangulate returns a Delaunay triangulation of the provided points.

func (*Triangulation) Validate

func (t *Triangulation) Validate() error

Validate performs several sanity checks on the Triangulation to check for potential errors. Returns nil if no issues were found. You normally shouldn't need to call this function but it can be useful for debugging.