hep: go-hep.org/x/hep/fastjet/internal/delaunay Index | Files

package delaunay

import "go-hep.org/x/hep/fastjet/internal/delaunay"

package delaunay contains functions to compute a Delaunay Triangulation

Index

Package Files

delaunay.go doc.go point.go triangle.go

type Delaunay Uses

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

Delaunay holds necessary information for the delaunay triangulation.

func HierarchicalDelaunay Uses

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 Uses

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

func (*Delaunay) Insert Uses

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 Uses

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 Uses

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

Triangles returns the triangles that form the delaunay triangulation.

func (*Delaunay) VoronoiCell Uses

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 Uses

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 Uses

func NewPoint(x, y float64) *Point

NewPoint returns Point for the given x,y coordinates

func (*Point) Coordinates Uses

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

Coordinates returns the x,y coordinates of a Point.

func (*Point) Equals Uses

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

Equals checks whether two points are the same.

func (*Point) ID Uses

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 Uses

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

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

func (*Point) SecondNearestNeighbor Uses

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 Uses

func (p *Point) String() string

type Triangle Uses

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 Uses

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

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

func (*Triangle) Equals Uses

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

Equals checks whether two triangles are the same.

func (*Triangle) String Uses

func (t *Triangle) String() string

Package delaunay imports 4 packages (graph) and is imported by 1 packages. Updated 2018-08-02. Refresh now. Tools for package owners.