voronoi

README

Voronoi diagrams in Go

A Implementation of of Steven J. Fortune's algorithm to efficiently compute Voronoi diagrams in Go language. Based on a Raymond Hill's javascript implementation (https://raw.github.com/gorhill/Javascript-Voronoi).

Usage

import "github.com/pzsz/voronoi"

func useVoronoi() {
     	// Sites of voronoi diagram
	sites := []voronoi.Vertex{
		voronoi.Vertex{4, 5},
		voronoi.Vertex{6, 5},
		...
	}

	// Create bounding box of [0, 20] in X axis
	// and [0, 10] in Y axis
	bbox := NewBBox(0, 20, 0, 10)

	// Compute diagram and close cells (add half edges from bounding box)
	diagram := NewVoronoi().Compute(sites, bbox, true)

	// Iterate over cells
	for _, cell := diagram.Cells {
		for _, hedge := cell.Halfedges {
		    ...
		}	
	}

	// Iterate over all edges
	for _, edge := diagram.Edge {
	    ...
	}
}

Documentation

Index

• Variables
• type BBox
  • func NewBBox(xl, xr, yt, yb float64) BBox
• type Beachsection
• type BeachsectionPtrs
• type Cell
• type Diagram
  • func ComputeDiagram(sites []Vertex, bbox BBox, closeCells bool) *Diagram
• type Edge
  • func (e *Edge) GetOtherCell(cell *Cell) *Cell
  • func (e *Edge) GetOtherEdgeVertex(v Vertex) EdgeVertex
• type EdgeVertex
• type Halfedge
  • func (h *Halfedge) GetEndpoint() Vertex
  • func (h *Halfedge) GetStartpoint() Vertex
• type Halfedges
  • func (s Halfedges) Len() int
  • func (s Halfedges) Swap(i, j int)
• type Vertex
• type Vertices
  • func (s Vertices) Len() int
  • func (s Vertices) Swap(i, j int)
• type VerticesByY
  • func (s VerticesByY) Less(i, j int) bool
• type Voronoi

Variables

var NO_VERTEX = Vertex{math.Inf(1), math.Inf(1)}

Vertex representing lack of vertex (or bad vertex)

Types

type BBox

type BBox struct {
	Xl, Xr, Yt, Yb float64
}

Bounding Box

func NewBBox

func NewBBox(xl, xr, yt, yb float64) BBox

Create new Bounding Box

type Beachsection

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

type BeachsectionPtrs

type BeachsectionPtrs []*Beachsection

type Cell

type Cell struct {
	// Site of the cell
	Site Vertex
	// Array of halfedges sorted counterclockwise
	Halfedges []*Halfedge
}

Cell of voronoi diagram

type Diagram

type Diagram struct {
	Cells []*Cell
	Edges []*Edge
}

func ComputeDiagram

func ComputeDiagram(sites []Vertex, bbox BBox, closeCells bool) *Diagram

Compute voronoi diagram. If closeCells == true, edges from bounding box will be included in diagram.

type Edge

type Edge struct {
	// Cell on the left
	LeftCell *Cell
	// Cell on the right
	RightCell *Cell
	// Start Vertex
	Va EdgeVertex
	// End Vertex
	Vb EdgeVertex
}

Edge structure

func (*Edge) GetOtherCell

func (e *Edge) GetOtherCell(cell *Cell) *Cell

func (*Edge) GetOtherEdgeVertex

func (e *Edge) GetOtherEdgeVertex(v Vertex) EdgeVertex

type EdgeVertex

type EdgeVertex struct {
	Vertex
	Edges []*Edge
}

type Halfedge

type Halfedge struct {
	Cell  *Cell
	Edge  *Edge
	Angle float64
}

Halfedge (directed edge)

func (*Halfedge) GetEndpoint

func (h *Halfedge) GetEndpoint() Vertex

func (*Halfedge) GetStartpoint

func (h *Halfedge) GetStartpoint() Vertex

type Halfedges

type Halfedges []*Halfedge

Sort interface for halfedges

func (Halfedges) Len

func (s Halfedges) Len() int

func (Halfedges) Swap

func (s Halfedges) Swap(i, j int)

type Vertex

type Vertex struct {
	X float64
	Y float64
}

Vertex on 2D plane

type Vertices

type Vertices []Vertex

For sort interface

func (Vertices) Len

func (s Vertices) Len() int

func (Vertices) Swap

func (s Vertices) Swap(i, j int)

type VerticesByY

type VerticesByY struct{ Vertices }

Used for sorting vertices along the Y axis

func (VerticesByY) Less

func (s VerticesByY) Less(i, j int) bool

type Voronoi

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