Documentation
¶
Index ¶
- Variables
- func GetParabolaABC(focus *Site, yOfDirectrix int) (float64, float64, float64)
- func GetXOfInternalNode(node *Node, directrix int) (int, error)
- func GetXOfIntersection(left *Node, right *Node, directrix int) (int, error)
- func GetYByX(focus *Site, x int, directrix int) int
- type CircleEvents
- type DCEL
- type Event
- type EventQueue
- type EventType
- type Face
- type HalfEdge
- type Node
- func (n *Node) AddLeftEvent(event *Event)
- func (n *Node) AddMiddleEvent(event *Event)
- func (n *Node) AddRightEvent(event *Event)
- func (n *Node) FirstArc() *Node
- func (n *Node) HasEvent(event *Event) bool
- func (n *Node) IsLeaf() bool
- func (n *Node) LastArc() *Node
- func (n *Node) NextArc() *Node
- func (n *Node) NextChildArc() *Node
- func (n *Node) PrevArc() *Node
- func (n *Node) PrevChildArc() *Node
- func (n *Node) RemoveEvent(event *Event)
- func (n *Node) String() string
- type Site
- type SiteSlice
- type Vertex
- type Voronoi
- func (v *Voronoi) CloseTwins(list []*HalfEdge, vertex *Vertex)
- func (v *Voronoi) Generate()
- func (v *Voronoi) GetFaceHalfEdges(face *Face) []*HalfEdge
- func (v *Voronoi) GetFaceVertices(face *Face) []*Vertex
- func (v *Voronoi) HandleNextEvent()
- func (v *Voronoi) ReorderFaceEdges(face *Face)
- func (v *Voronoi) Reset()
- func (v *Voronoi) ToPolyhedrons() []shapes.Polyhedron
Constants ¶
This section is empty.
Variables ¶
var ( ErrCircleSitesOrder = errors.New("circle sites wrong order") ErrNoCircleFoundConnectionPoints = errors.New("no circle found connecting points") )
All kind of errors
Functions ¶
func GetParabolaABC ¶
GetParabolaABC returns the a, b and c coefficients of the standard form of a parabola equation, given only x and y of the focus and y of the directrix. Math behind this is explained at https://math.stackexchange.com/q/2700061/543428.
func GetXOfInternalNode ¶
GetXOfInternalNode returns the x of the intersection of the two parabola arcs below an internal node.
func GetXOfIntersection ¶
GetXOfIntersection returns the x of the intersection of two parabola arcs.
Types ¶
type CircleEvents ¶
type CircleEvents []*Event
CircleEvents represents a list of pointers to circle events in which the node participates.
func (*CircleEvents) HasEvent ¶
func (ce *CircleEvents) HasEvent(event *Event) bool
HasEvent tests if the node has a pointer to the given event.
func (*CircleEvents) RemoveEvent ¶
func (ce *CircleEvents) RemoveEvent(event *Event)
RemoveEvent removes the given event from the list.
type DCEL ¶
DCEL stores the state of the data structure and provides methods for linking of three sets of objects: vertecies, edges and faces.
func (*DCEL) NewEdge ¶
NewEdge creates a pair of half-edges, one of them starting at the given vertex.
func (*DCEL) NewHalfEdge ¶
NewHalfEdge creates a new half-edge starting at the given vertex and stores it in the structure.
type Event ¶
type Event struct {
X, Y int // X and Y of the site, or X and Y of the bottom point of the circle.
EventType EventType // The type of the event. Site = 0 and Circle = 1.
Site *Site // Pointer to the related site. Only relevant for site events.
Node *Node // The related arc node. Only relevant for circle events.
Radius int // Radius of the circle.
// contains filtered or unexported fields
}
Event represents a site or circle event.
type EventQueue ¶
type EventQueue []*Event
A EventQueue is a priority queue that implements heap.Interface and holds Events.
func NewEventQueue ¶
func NewEventQueue(sites SiteSlice) EventQueue
NewEventQueue creates a new queue and initializes it with events for the given list of sites.
func (EventQueue) Len ¶
func (pq EventQueue) Len() int
Len returns the number of events in the queue.
func (EventQueue) Less ¶
func (pq EventQueue) Less(i, j int) bool
Less compares two events and is needed as implementation of the Sort interface.
func (*EventQueue) Pop ¶
func (pq *EventQueue) Pop() interface{}
Pop removes the last element from the queue and sets its index to -1.
func (*EventQueue) Push ¶
func (pq *EventQueue) Push(x interface{})
Push appends an item to the queue and reorders items if necessary.
func (*EventQueue) Remove ¶
func (pq *EventQueue) Remove(event *Event)
Remove removes the element with the specified index from the queue.
func (EventQueue) String ¶
func (pq EventQueue) String() string
func (EventQueue) Swap ¶
func (pq EventQueue) Swap(i, j int)
Swap swaps two events, updating their index in the slice.
type EventType ¶
type EventType int
EventType represent the type of the event - either site or circle event.
type Face ¶
Face represents a subdivision of the plane. Each face has a pointer to one of the half edges at its boundary. Faces can have user specified IDs and annotations.
type HalfEdge ¶
type HalfEdge struct {
Target *Vertex
Face *Face
Twin *HalfEdge
Next *HalfEdge
Prev *HalfEdge
Data interface{}
}
HalfEdge represents one of the half-edges in an edge pair. Each half-edge has a pointer to its target vertex (origin), the face to which it belongs, its twin edge (a reversed half-edge, pointing to a neighbour face) and pointers to the next and previous half-edges at the boundary of its face. Half-edges can also store user data.
type Node ¶
type Node struct {
// Site is the focus of the parabola arc (the site which created the parabola).
// Not used for internal nodes.
Site *Site
// Events hold pointers to circle events, in which this arc is the left most, middle or right-most arc.
// Not used for internal nodes.
LeftEvents, MiddleEvents, RightEvents CircleEvents
// Pointer to the parent node.
Parent *Node
// Left stores a subtree of arcs with smaller X values.
Left *Node
// Right stores a subtree of arcs with larger X values.
Right *Node
LeftEdges []*HalfEdge
RightEdges []*HalfEdge
}
Node represent an element in a binary tree. Each Leaf in the tree represents an arc of a parabola (part of parabola), that lies on the beach line. Leaf nodes store the site that created the arc and pointers to the circle events associated with it. Internal nodes represent intersections (breakpoints) between the arcs and store no values.
func (*Node) AddLeftEvent ¶
AddLeftEvent pushes a pointer to an event for which this is the left-most node.
func (*Node) AddMiddleEvent ¶
AddMiddleEvent pushes a pointer to an event for which this is the left-most node.
func (*Node) AddRightEvent ¶
AddRightEvent pushes a pointer to an event for which this is the left-most node.
func (*Node) IsLeaf ¶
IsLeaf returns true if the TreeNode has no left or right children. A single root node is also considered a leaf.
func (*Node) NextChildArc ¶
NextChildArc returns the node for the next arc.
func (*Node) PrevChildArc ¶
PrevChildArc returns the node for the previous arc.
func (*Node) RemoveEvent ¶
RemoveEvent removes the given event from the lists of the node.
func (*Node) String ¶
String method from https://github.com/golang/tour/blob/master/tree/tree.go
type Site ¶
type Site struct {
X, Y int
ID int64
Face *Face // Pointer to the DCEL face corresponding to this site
Data interface{}
}
Site is a prerequisute for computing a voronoi diagram. Site is the point (also called seed or generator) in a voronoi diagram, around which a cell (subset of the plane) is formed, with such a property that every point in the cell is closer to this site than any other site.
type Vertex ¶
Vertex represents a node in the DCEL structure. Each vertex has 2D coordinates and a pointer to an arbitrary half edge that has this vertex as its target (origin). Annotations (user data) can be stored in the Data field.
type Voronoi ¶
type Voronoi struct {
Bounds shapes.Box
Sites SiteSlice
EventQueue EventQueue
ParabolaTree *Node
SweepLine int // tracks the current position of the sweep line; updated when a new site is added.
DCEL *DCEL
}
Voronoi implements Fortune's algorithm for voronoi diagram generation.
func New ¶
New creates a voronoi diagram generator for a list of sites and within the specified bounds.
func NewFromPoints ¶
NewFromPoints creates a voronoi diagram generator for a list of points within the specified bounds.
func (*Voronoi) CloseTwins ¶
CloseTwins adds a vertex to the specified edges.
func (*Voronoi) Generate ¶
func (v *Voronoi) Generate()
Generate runs the algorithm for the given sites and bounds, creating a voronoi diagram.
func (*Voronoi) GetFaceHalfEdges ¶
GetFaceHalfEdges returns the half-edges that form the boundary of a face (cell).
func (*Voronoi) GetFaceVertices ¶
GetFaceVertices returns the vertices that form the boundary of a face (cell), sorted in counter-clockwise order.
func (*Voronoi) HandleNextEvent ¶
func (v *Voronoi) HandleNextEvent()
HandleNextEvent processes the next event from the internal event queue. Used from the player application while developing the algorithm.
func (*Voronoi) ReorderFaceEdges ¶
ReorderFaceEdges reorders face half-edges in a clockwise way, while also removing duplicates.
func (*Voronoi) ToPolyhedrons ¶
func (v *Voronoi) ToPolyhedrons() []shapes.Polyhedron
ToPolyhedrons return polyhedrons from given voronoi algorithm
Source Files