delaunay

package
v0.29.2 Latest Latest
Warning

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

Go to latest
Published: Sep 29, 2021 License: BSD-3-Clause Imports: 4 Imported by: 0

Documentation

Overview

package delaunay contains functions to compute a Delaunay Triangulation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Delaunay

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

Delaunay holds necessary information for the delaunay triangulation.

func HierarchicalDelaunay

func HierarchicalDelaunay() *Delaunay

HierarchicalDelaunay creates a Delaunay Triangulation using the delaunay hierarchy.

The worst case time complexity is O(n*log(n)).

The three root points (-2^30,-2^30), (2^30,-2^30) and (0,2^30) can't be in the circumcircle of any three non-collinear points in the triangulation. Additionally all points have to be inside the Triangle formed by these three points. If any of these conditions doesn't apply use the WalkDelaunay function instead. 2^30 = 1,073,741,824

To locate a point this algorithm uses a Directed Acyclic Graph with a single root. All triangles in the current triangulation are leaf triangles. To find the triangle which contains the point, the algorithm follows the graph until a leaf is reached.

Duplicate points don't get inserted, but the nearest neighbor is set to the corresponding point. When a duplicate point is removed nothing happens.

func WalkDelaunay

func WalkDelaunay(points []*Point, r *rand.Rand) *Delaunay

func (*Delaunay) Insert

func (d *Delaunay) Insert(p *Point) (updatedNearestNeighbor []*Point)

Insert inserts the point into the triangulation. It returns the points whose nearest neighbor changed due to the insertion. The slice may contain duplicates.

func (*Delaunay) Remove

func (d *Delaunay) Remove(p *Point) (updatedNearestNeighbor []*Point)

Remove removes the point from the triangulation. It returns the points whose nearest neighbor changed due to the removal. The slice may contain duplicates.

func (*Delaunay) Triangles

func (d *Delaunay) Triangles() []*Triangle

Triangles returns the triangles that form the delaunay triangulation.

func (*Delaunay) VoronoiCell

func (d *Delaunay) VoronoiCell(p *Point) ([]*Point, float64)

VoronoiCell returns the Vornoi points of a point in clockwise order and the area those points enclose.

If a point is on the border of the Delaunay triangulation the area will be Infinity and the first and last point of the cell will be part of a root triangle. The function will panic if the number of adjacent triangles is < 3.

type Point

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

Point in the X-Y Plane.

It holds dynamic information about the adjacent triangles, the nearest neighbor and the distance to that neighbor.

One should use the Equal method of Point to test whether 2 points are equal.

func NewPoint

func NewPoint(x, y float64) *Point

NewPoint returns Point for the given x,y coordinates

func (*Point) Coordinates

func (p *Point) Coordinates() (x, y float64)

Coordinates returns the x,y coordinates of a Point.

func (*Point) Equals

func (p *Point) Equals(v *Point) bool

Equals checks whether two points are the same.

func (*Point) ID

func (p *Point) ID() int

ID returns the ID of the point. It is a unique identifier that is incrementally assigned to a point on insertion.

func (*Point) NearestNeighbor

func (p *Point) NearestNeighbor() (*Point, float64)

NearestNeighbor returns the nearest neighbor and the distance to that neighbor.

func (*Point) SecondNearestNeighbor

func (p *Point) SecondNearestNeighbor() (*Point, float64)

SecondNearestNeighbor looks at all adjacent points of p and returns the second nearest one and the distance to that point.

func (*Point) String

func (p *Point) String() string

type Triangle

type Triangle struct {

	// A,B,C are the CCW-oriented points that make up the triangle
	A, B, C *Point
	// contains filtered or unexported fields
}

Triangle is a set of three points that make up a triangle. It stores hierarchical information to find triangles.

func NewTriangle

func NewTriangle(a, b, c *Point) *Triangle

NewTriangle returns a triangle formed out of the three given points.

func (*Triangle) Equals

func (t *Triangle) Equals(s *Triangle) bool

Equals checks whether two triangles are the same.

func (*Triangle) String

func (t *Triangle) String() string

Jump to

Keyboard shortcuts

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