incrdelaunay

Documentation

Overview

Package incrdelaunay implements a library for incremental Delaunay triangulation, with support for dynamically adding and removing points.

Index

• func Voronoi(delaunay *Delaunay, polygon func([]FloatPoint), w, h int)
• type Circumcircle
• type CircumcircleGrid
  • func NewCircumcircleGrid(cols, rows, w, h int) CircumcircleGrid
  • func (c *CircumcircleGrid) AddTriangle(t Triangle, index uint16)
  • func (c CircumcircleGrid) HasPoint(p Point, triangles []Triangle) bool
  • func (c CircumcircleGrid) IterCircumcirclesThatContain(p Point, triangles []Triangle, contains func(i uint16))
  • func (c CircumcircleGrid) IterThatHasVertex(p Point, triangles []Triangle, contains func(i uint16))
  • func (c CircumcircleGrid) RemoveCircumcirclesThatContain(p Point, triangles []Triangle, contains func(i uint16))
  • func (c CircumcircleGrid) RemoveThatHasVertex(p Point, triangles []Triangle, contains func(i uint16))
  • func (c *CircumcircleGrid) RemoveTriangle(tri Triangle, index uint16)
  • func (c *CircumcircleGrid) Set(other *CircumcircleGrid)
• type Delaunay
  • func NewDelaunay(w, h int) *Delaunay
  • func (d Delaunay) GetClosestTo(p Point) Point
  • func (d Delaunay) HasPoint(p Point) bool
  • func (d *Delaunay) Insert(p Point) bool
  • func (d Delaunay) IterTriangles(triangle func(t Triangle))
  • func (d Delaunay) NumPoints() int
  • func (d *Delaunay) Remove(p Point)
  • func (d *Delaunay) Set(other *Delaunay)
• type Edge
  • func NewEdge(a, b Point) Edge
  • func (e Edge) Equals(b Edge) bool
• type FloatPoint
• type IVoronoi
  • func NewVoronoi(w, h int) *IVoronoi
  • func (v *IVoronoi) Insert(point Point)
  • func (v *IVoronoi) IterPolygons(polygon func([]FloatPoint))
  • func (v *IVoronoi) Remove(point Point)
  • func (v *IVoronoi) Set(other *IVoronoi)
• type Point
  • func (p Point) DistSq(b Point) int64
  • func (p Point) Hash() int
• type Triangle
  • func NewSuperTriangle(w, h int) Triangle
  • func NewTriangle(a, b, c Point) Triangle
  • func (t Triangle) HasVertex(p Point) bool

Functions

func Voronoi

func Voronoi(delaunay *Delaunay, polygon func([]FloatPoint), w, h int)

Types

type Circumcircle

type Circumcircle struct {
	Radius float32
	// contains filtered or unexported fields
}

Circumcircle represents a circumcircle of a Triangle.

type CircumcircleGrid

type CircumcircleGrid struct {
	// contains filtered or unexported fields
}

CircumcircleGrid is a data structure that uses spatial partitioning to allowed fast operations involving multiple Triangle's and their Circumcircle's.

func NewCircumcircleGrid

func NewCircumcircleGrid(cols, rows, w, h int) CircumcircleGrid

NewCircumcircleGrid returns a new grid with a specified number of columns and rows.

func (*CircumcircleGrid) AddTriangle

func (c *CircumcircleGrid) AddTriangle(t Triangle, index uint16)

AddTriangle adds a Triangle with an index to the grid.

func (CircumcircleGrid) HasPoint

func (c CircumcircleGrid) HasPoint(p Point, triangles []Triangle) bool

HasPoint returns if a triangle in the grid has a point.

func (CircumcircleGrid) IterCircumcirclesThatContain

func (c CircumcircleGrid) IterCircumcirclesThatContain(p Point, triangles []Triangle, contains func(i uint16))

func (CircumcircleGrid) IterThatHasVertex

func (c CircumcircleGrid) IterThatHasVertex(p Point, triangles []Triangle, contains func(i uint16))

func (CircumcircleGrid) RemoveCircumcirclesThatContain

func (c CircumcircleGrid) RemoveCircumcirclesThatContain(p Point, triangles []Triangle, contains func(i uint16))

RemoveCircumcirclesThatContain removes all triangles whose circumcircle contain a point.

func (CircumcircleGrid) RemoveThatHasVertex

func (c CircumcircleGrid) RemoveThatHasVertex(p Point, triangles []Triangle, contains func(i uint16))

RemoveThatHasVertex removes all triangles that have a vertex.

func (*CircumcircleGrid) RemoveTriangle

func (c *CircumcircleGrid) RemoveTriangle(tri Triangle, index uint16)

RemoveTriangle removes a triangle from the grid.

func (*CircumcircleGrid) Set

func (c *CircumcircleGrid) Set(other *CircumcircleGrid)

Set sets a CircumcircleGrid to another CircumcircleGrid.

type Delaunay

type Delaunay struct {
	// contains filtered or unexported fields
}

Delaunay represents a Delaunay triangulation.

func NewDelaunay

func NewDelaunay(w, h int) *Delaunay

NewDelaunay returns a new Delaunay triangulation.

func (Delaunay) GetClosestTo

func (d Delaunay) GetClosestTo(p Point) Point

GetClosestTo returns the closest point in the triangulation to point p.

func (Delaunay) HasPoint

func (d Delaunay) HasPoint(p Point) bool

HasPoint returns whether the triangulation contains point p.

func (*Delaunay) Insert

func (d *Delaunay) Insert(p Point) bool

Insert adds a point to the Delaunay triangulation using the Bowyer-Watson algorithm. Duplicate points are kept track of.

func (Delaunay) IterTriangles

func (d Delaunay) IterTriangles(triangle func(t Triangle))

IterTriangles iterates through all the triangles in the triangulation, calling function triangle for each one.

func (Delaunay) NumPoints

func (d Delaunay) NumPoints() int

NumPoints returns the number of points in the triangulation, including duplicate points.

func (*Delaunay) Remove

func (d *Delaunay) Remove(p Point)

Remove removes a point from the Delaunay Triangulation. If there are duplicates of the point only one of the duplicates is removed.

func (*Delaunay) Set

func (d *Delaunay) Set(other *Delaunay)

Set sets the triangulation to another triangulation.

type Edge

type Edge struct {
	A, B Point
}

Edge represents an edge from point A to B.

func NewEdge

func NewEdge(a, b Point) Edge

NewEdge returns a new edge with its points sorted.

func (Edge) Equals

func (e Edge) Equals(b Edge) bool

Equals returns if the edge is equal to another.

type FloatPoint

type FloatPoint struct {
	X, Y float64
}

type IVoronoi

type IVoronoi struct {
	// contains filtered or unexported fields
}

func NewVoronoi

func NewVoronoi(w, h int) *IVoronoi

func (*IVoronoi) Insert

func (v *IVoronoi) Insert(point Point)

func (*IVoronoi) IterPolygons

func (v *IVoronoi) IterPolygons(polygon func([]FloatPoint))

func (*IVoronoi) Remove

func (v *IVoronoi) Remove(point Point)

func (*IVoronoi) Set

func (v *IVoronoi) Set(other *IVoronoi)

type Point

type Point struct {
	X, Y int16
}

Point represents a 2D point, using int16 to optimize space.

func (Point) DistSq

func (p Point) DistSq(b Point) int64

DistSq returns the distance squared to another point.

func (Point) Hash

func (p Point) Hash() int

Hash returns a hash code for the point.

type Triangle

type Triangle struct {
	A, B, C      Point
	Circumcircle Circumcircle
}

Triangle stores the vertices of a triangle as well as its circumcircle.

func NewSuperTriangle

func NewSuperTriangle(w, h int) Triangle

NewSuperTriangle returns a Triangle large enough to cover all points within (0, 0) to (w, h).

func NewTriangle

func NewTriangle(a, b, c Point) Triangle

NewTriangle return a new Triangle and calculates its circumcircle given three points.

func (Triangle) HasVertex

func (t Triangle) HasVertex(p Point) bool

HasVertex returns if the Triangle contains a specified vertex.