delaunay

README

Delaunay Triangulation

Fast Delaunay triangulation implemented in Go.

This module has been derived from Michael Fogelman's port of the Mapbox's Delaunator project (JavaScript).

The only modifications from Mr. Fogelman's code are that the project has been updated to be a Go module, and all methods now accept and return the Point2d interface, to allow easier interoperation between this library and code that does not want to use this library's internal representation of 2d points.

Installation

$ go get -u github.com/Infinities-Within/delaunay

Documentation

https://godoc.org/github.com/Infinities-Within/delaunay

See https://mapbox.github.io/delaunator/ for more information about the Triangles and Halfedges data structures.

Usage

var points []delaunay.Point2d
// populate points...
triangulation, err := delaunay.Triangulate(points)
// handle err...
// use triangulation.Triangles, triangulation.Halfedges

Performance

2.6 GHz Intel Core i7

# 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 Point2d
  • func ConvexHull(points []Point2d) []Point2d
  • func NewPoint(x, y float64) Point2d
• type Triangulation
  • func Triangulate(points []Point2d) (*Triangulation, error)
  • func (t *Triangulation) Validate() error

Types

type Point2d

type Point2d interface {
	X() float64
	Y() float64
	SquaredDistance(b Point2d) float64
	Distance(b Point2d) float64
	Sub(b Point2d) Point2d
}

func ConvexHull

func ConvexHull(points []Point2d) []Point2d

ConvexHull returns the convex hull of the provided points.

func NewPoint

func NewPoint(x, y float64) Point2d

type Triangulation

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

func Triangulate

func Triangulate(points []Point2d) (*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.