dcel

README

dcel

dcel is a Golang implementation of the doubly connected edge list (DCEL) data structure and is used to represent planar graphs in a plane.

This implementation is intended to be used in 2D space only and was initially created for use by the voronoi package for generation of voronoi diagrams with Fortune's algorithm.

Documentation

Overview

Package dcel implements a doubly connected edge list data structure, and is used to represent planar graphs in a plane. This implementation is intended to be used in 2D space only.

Index

• type DCEL
  • func NewDCEL() *DCEL
  • func (d *DCEL) NewEdge(face1, face2 *Face, vertex *Vertex) (*HalfEdge, *HalfEdge)
  • func (d *DCEL) NewFace() *Face
  • func (d *DCEL) NewHalfEdge(face *Face, vertex *Vertex, twin *HalfEdge) *HalfEdge
  • func (d *DCEL) NewVertex(x, y int) *Vertex
• type Face
  • func (f *Face) String() string
• type HalfEdge
  • func (he *HalfEdge) IsClosed() bool
  • func (he *HalfEdge) String() string
• type Vertex
  • func (v *Vertex) String() string

Types

type DCEL

type DCEL struct {
	Vertices  []*Vertex
	Faces     []*Face
	HalfEdges []*HalfEdge
}

DCEL stores the state of the data structure and provides methods for linking of three sets of objects: vertecies, edges and faces.

func NewDCEL

func NewDCEL() *DCEL

NewDCEL creates a new DCEL data structure.

func (*DCEL) NewEdge

func (d *DCEL) NewEdge(face1, face2 *Face, vertex *Vertex) (*HalfEdge, *HalfEdge)

NewEdge creates a pair of half-edges, one of them starting at the given vertex.

func (*DCEL) NewFace

func (d *DCEL) NewFace() *Face

NewFace creates a new face and stores it in the DCEL structure.

func (*DCEL) NewHalfEdge

func (d *DCEL) NewHalfEdge(face *Face, vertex *Vertex, twin *HalfEdge) *HalfEdge

NewHalfEdge creates a new half-edge starting at the given vertex and stores it in the structure.

func (*DCEL) NewVertex

func (d *DCEL) NewVertex(x, y int) *Vertex

NewVertex creates a new vertex with the given coordinates and stores it in the structure.

type Face

type Face struct {
	HalfEdge *HalfEdge
	ID       int64
	Data     interface{}
}

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.

func (*Face) String

func (f *Face) String() string

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.

func (*HalfEdge) IsClosed

func (he *HalfEdge) IsClosed() bool

IsClosed returns true if both half-edges in the pair have a target vertex.

func (*HalfEdge) String

func (he *HalfEdge) String() string

type Vertex

type Vertex struct {
	X, Y     int
	HalfEdge *HalfEdge
	Data     interface{}
}

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.

func (*Vertex) String

func (v *Vertex) String() string