delaunay

package module
v0.0.0-...-63f09b4 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 10, 2018 License: MIT Imports: 3 Imported by: 20

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

Example

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL