README
¶
voronoi
Golang package for generation of voronoi diagrams with Fortune's algorithm.
Work in progress. Populates a DCEL data structure, but does not connect infinite half-edges to the bounding box.
TODO:
- Connect infinite half-edges to the bounding box.
How to debug
cd cmd
go run player.go
player is a standalone tool (standalone web server) for visualization of the algorithm of github.com/quasoft/voronoi in steps:
Pressing the [Next] link advances the algorithm to the next event and updates the visualization at the left.
The graph at the right reflects the state of the binary tree with parabola arcs.
Documentation
¶
Index ¶
- 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
- func Plot(voronoi *Voronoi) *image.RGBA
- type CircleEvents
- type Event
- type EventQueue
- type EventType
- 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 Plotter
- func (p *Plotter) BeachLine(tree *Node)
- func (p *Plotter) Edges()
- func (p *Plotter) Faces()
- func (p *Plotter) Max() image.Point
- func (p *Plotter) Min() image.Point
- func (p *Plotter) Plot()
- func (p *Plotter) Site(site Site, clr color.Color)
- func (p *Plotter) Sites()
- func (p *Plotter) SweepLine(y int)
- func (p *Plotter) Vertex(x, y int)
- func (p *Plotter) Verticies()
- type Site
- type SiteSlice
- type Voronoi
- func (v *Voronoi) CloseTwins(list []*dcel.HalfEdge, vertex *dcel.Vertex)
- func (v *Voronoi) Generate()
- func (v *Voronoi) GetFaceHalfEdges(face *dcel.Face) []*dcel.HalfEdge
- func (v *Voronoi) GetFaceVertices(face *dcel.Face) []*dcel.Vertex
- func (v *Voronoi) HandleNextEvent()
- func (v *Voronoi) ReorderFaceEdges(face *dcel.Face)
- func (v *Voronoi) Reset()
Constants ¶
This section is empty.
Variables ¶
This section is empty.
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 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 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 []*dcel.HalfEdge
RightEdges []*dcel.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 Plotter ¶
type Plotter struct {
BackgroundColor color.RGBA
VertexColor color.RGBA
// contains filtered or unexported fields
}
Plotter draws the result of the voronoi diagram generator into an image.
func NewPlotter ¶
NewPlotter creates a new voronoi diagram drawer.
func (*Plotter) Faces ¶
func (p *Plotter) Faces()
Faces draws surface of faces, filling them with site colour
func (*Plotter) Plot ¶
func (p *Plotter) Plot()
Plot paints the voronoi diagram over the given image.
type Site ¶
type Site struct {
X, Y int
ID int64
Face *dcel.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 Voronoi ¶
type Voronoi struct {
Bounds image.Rectangle
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.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.
Source Files
Directories