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 (*Delaunay) Insert ¶
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 ¶
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) VoronoiCell ¶
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 (*Point) Coordinates ¶
Coordinates returns the x,y coordinates of a Point.
func (*Point) ID ¶
ID returns the ID of the point. It is a unique identifier that is incrementally assigned to a point on insertion.
func (*Point) NearestNeighbor ¶
NearestNeighbor returns the nearest neighbor and the distance to that neighbor.
func (*Point) SecondNearestNeighbor ¶
SecondNearestNeighbor looks at all adjacent points of p and returns the second nearest one and the distance to that point.
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 ¶
NewTriangle returns a triangle formed out of the three given points.
Source Files