dcel

package module

v0.0.0-...-0074aa0 Latest Latest Go to latest Published: Jun 24, 2018 License: MIT Imports: 2 Imported by: 2

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/quasoft/dcel

Links

Open Source Insights

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
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

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

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

Source Files ¶

View all Source files

dcel.go

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL