dcel

package module
v0.0.0-...-3161ce3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 21, 2017 License: BSD-3-Clause Imports: 2 Imported by: 1

README

This repository has been archived

dcel

Doubly-connected edge list data structure in Go

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Base 

type Base struct{}

Base implements Items interface for allocating base elements of DCEL data structure.

func (Base) NewEdge 

func (Base) NewEdge(id int) Edge

func (Base) NewFace 

func (Base) NewFace(id int) Face

func (Base) NewHalfedge 

func (Base) NewHalfedge() Halfedge

func (Base) NewNode 

func (Base) NewNode(id int) Node

type BaseEdge 

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

func NewBaseEdge 

func NewBaseEdge(id int) *BaseEdge

func (*BaseEdge) From 

func (e *BaseEdge) From() graph.Node

func (*BaseEdge) Halfedges 

func (e *BaseEdge) Halfedges() (Halfedge, Halfedge)

func (*BaseEdge) ID 

func (e *BaseEdge) ID() int

func (*BaseEdge) SetHalfedges 

func (e *BaseEdge) SetHalfedges(h1, h2 Halfedge)

func (*BaseEdge) To 

func (e *BaseEdge) To() graph.Node

func (*BaseEdge) Weight 

func (e *BaseEdge) Weight() float64

type BaseFace 

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

func NewBaseFace 

func NewBaseFace(id int) *BaseFace

func (*BaseFace) Halfedge 

func (f *BaseFace) Halfedge() Halfedge

func (*BaseFace) ID 

func (f *BaseFace) ID() int

func (*BaseFace) SetHalfedge 

func (f *BaseFace) SetHalfedge(h Halfedge)

type BaseHalfedge 

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

func NewBaseHalfedge 

func NewBaseHalfedge() *BaseHalfedge

func (*BaseHalfedge) Edge 

func (h *BaseHalfedge) Edge() Edge

func (*BaseHalfedge) Face 

func (h *BaseHalfedge) Face() Face

func (*BaseHalfedge) From 

func (h *BaseHalfedge) From() Node

func (*BaseHalfedge) Next 

func (h *BaseHalfedge) Next() Halfedge

func (*BaseHalfedge) Prev 

func (h *BaseHalfedge) Prev() Halfedge

func (*BaseHalfedge) SetEdge 

func (h *BaseHalfedge) SetEdge(e Edge)

func (*BaseHalfedge) SetFace 

func (h *BaseHalfedge) SetFace(f Face)

func (*BaseHalfedge) SetFrom 

func (h *BaseHalfedge) SetFrom(u Node)

func (*BaseHalfedge) SetNext 

func (h *BaseHalfedge) SetNext(he Halfedge)

func (*BaseHalfedge) SetPrev 

func (h *BaseHalfedge) SetPrev(he Halfedge)

func (*BaseHalfedge) SetTwin 

func (h *BaseHalfedge) SetTwin(he Halfedge)

func (*BaseHalfedge) Twin 

func (h *BaseHalfedge) Twin() Halfedge

type BaseNode 

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

func NewBaseNode 

func NewBaseNode(id int) *BaseNode

func (*BaseNode) Halfedge 

func (n *BaseNode) Halfedge() Halfedge

func (*BaseNode) ID 

func (n *BaseNode) ID() int

func (*BaseNode) SetHalfedge 

func (n *BaseNode) SetHalfedge(h Halfedge)

type Edge 

type Edge interface {
	graph.Edge

	// ID returns an edge identifier unique within the graph.
	ID() int

	// Halfedges returns the two halfedges that form the edge.
	Halfedges() (Halfedge, Halfedge)
	// SetHalfedges sets the two halfedges that form the edge.
	SetHalfedges(Halfedge, Halfedge)
}

Edge is an undirected edge in the DCEL data structure.

type Face 

type Face interface {
	// ID returns a face identifier unique within the graph.
	ID() int

	// Halfedge returns an adjacent halfedge.
	Halfedge() Halfedge
	// SetHalfedge sets an adjacent halfedge.
	SetHalfedge(Halfedge)
}

Face is a face in the DCEL data structure.

type Graph 

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

Graph implements the doubly-connected edge list data structure.

func New 

func New(items Items) *Graph

New returns a new Graph. If items is nil, Base will be used.

func (*Graph) AddFace 

func (g *Graph) AddFace(id int, nodes ...graph.Node) error

AddFace adds a new face with given ID and with vertices given by nodes. Any missing node or edge between two consecutive nodes will be added to the graph first.

If the nodes are not pair-wise distinct, if two consecutive nodes are already connected by a halfedge with an adjacent Face, or if the existing graph topology does not permit adding the face, an error will be returned.

AddFace panics if a face with the given id already exists in the graph or if the length of nodes is less than 3.

func (*Graph) AddNode 

func (g *Graph) AddNode(id int) Node

AddNode adds a new, isolated node with the given id to the graph and returns it. AddNode panics if a node with same id already exists in the graph.

func (*Graph) Edge 

func (g *Graph) Edge(x, y graph.Node) graph.Edge

Edge returns the edge between x and y or nil if the nodes are not connected.

func (*Graph) EdgeBetween 

func (g *Graph) EdgeBetween(x, y graph.Node) graph.Edge

EdgeBetween returns the edge between x and y or nil if the nodes are not connected.

func (*Graph) Edges 

func (g *Graph) Edges() []graph.Edge

Edges returns all the edges in the graph.

func (*Graph) Face 

func (g *Graph) Face(id int) Face

Face returns the face with the given id or nil if it does not exist within the graph.

func (*Graph) Faces 

func (g *Graph) Faces() []Face

Faces returns all the faces in the graph.

func (*Graph) From 

func (g *Graph) From(x graph.Node) []graph.Node

From returns all neighbors of the node x.

func (*Graph) Halfedge 

func (g *Graph) Halfedge(x, y graph.Node) Halfedge

Halfedge returns the halfedge from x to y, or nil if the nodes are not connected by an edge or at least one is isolated.

func (*Graph) HalfedgesAround 

func (g *Graph) HalfedgesAround(f Face) []Halfedge

HalfedgesAround returns all halfedges adjacent to the given face.

func (*Graph) HalfedgesFrom 

func (g *Graph) HalfedgesFrom(x graph.Node) []Halfedge

HalfedgesFrom returns all halfedges whose From node is x.

func (*Graph) HalfedgesTo 

func (g *Graph) HalfedgesTo(x graph.Node) []Halfedge

HalfedgesTo returns all halfedges whose Twin.From node is x.

func (*Graph) Has 

func (g *Graph) Has(x graph.Node) bool

Has returns whether a node with the id given by x.ID() exists within the graph.

func (*Graph) HasEdge 

func (g *Graph) HasEdge(x, y graph.Node) bool

HasEdge returns whether an edge exists between nodes x and y.

func (*Graph) HasFace 

func (g *Graph) HasFace(id int) bool

HasFace returns whether a face with the given id exists in the graph.

func (*Graph) NewFaceID 

func (g *Graph) NewFaceID() int

NewFaceID returns a new face id unique within the graph.

func (*Graph) NewNodeID 

func (g *Graph) NewNodeID() int

NewNodeID returns a new node id unique within the graph.

func (*Graph) Node 

func (g *Graph) Node(id int) Node

Node returns the node with the given id or nil if it does not exist within the graph.

func (*Graph) Nodes 

func (g *Graph) Nodes() []graph.Node

Nodes returns all the nodes in the graph.

func (*Graph) RemoveEdge 

func (g *Graph) RemoveEdge(e graph.Edge)

RemoveEdge removes the edge between nodes identified by e.From and e.To and its adjacent faces from g.

func (*Graph) RemoveFace 

func (g *Graph) RemoveFace(f Face)

RemoveFace disconnects f from g and sets its Halfedge to nil.

func (*Graph) RemoveNode 

func (g *Graph) RemoveNode(x graph.Node)

RemoveNode removes the node with ID given by x.ID() from the graph as well as any edges attached to it.

type Halfedge 

type Halfedge interface {
	// From returns the origin node.
	From() Node
	// SetFrom sets the origin node.
	SetFrom(Node)

	// Twin returns the twin halfedge in the same edge.
	Twin() Halfedge
	// SetTwin sets the twin halfedge in the same edge.
	SetTwin(Halfedge)

	// Next returns the next halfedge around the adjacent face.
	Next() Halfedge
	// SetNext sets the next halfedge around the adjacent face.
	SetNext(Halfedge)

	// Prev returns the previous halfedge around the adjacent face.
	Prev() Halfedge
	// SetPrev sets the previous halfedge around the adjacent face.
	SetPrev(Halfedge)

	// Edge returns the undirected edge to which the halfedge belongs.
	Edge() Edge
	// SetEdge sets the undirected edge to which the halfedge belongs.
	SetEdge(Edge)

	// Face returns the adjacent face.
	Face() Face
	// SetFace sets the adjacent face.
	SetFace(Face)
}

Halfedge is a an oriented edge in the DCEL data structure.

type Items 

type Items interface {
	// NewNode returns a new node with the given id.
	NewNode(int) Node
	// NewHalfedge returns a new halfedge.
	NewHalfedge() Halfedge
	// NewEdge returns a new edge with the given id.
	NewEdge(int) Edge
	// NewFace returns a new face with the given id.
	NewFace(int) Face
}

Items wraps methods for allocating graph entities that can be stored in the DCEL data structure.

type Node 

type Node interface {
	graph.Node

	// Halfedge returns the outgoing halfedge from the node. When the node is
	// isolated, the returned halfedge is nil. When the node is at a boundary,
	// the halfedge's Face is nil.
	Halfedge() Halfedge
	// SetHalfedge sets the outgoing halfedge from the node.
	SetHalfedge(Halfedge)
}

Node is a graph node in the DCEL data structure.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.