Documentation
¶
Overview ¶
Package quadedge provides a way to describe and manipulate the topology of planar maps (i.e., the topology of any closed polygonal mesh).
It implements the quad-edge data structure described in:
"Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams" P. Guibas, J. Stolfi, ACM TOG, April 1985
This structure represents at the same time the primal and dual of the map, as well as their mirror images. It allows to switch from one to another in constant time.
For example, a list of quad-edges that describe the topology a Delaunay triangulation also describe the corresponding Voronoi diagram.
The structure does not hold (nor use) any geometrical information, but contains 32bit IDs that can be used to identify vertices and faces.
Note that in this package, each (undirected) edge of the map is represented by four directed Edge objects.
Index ¶
- Constants
- func Delete(e Edge)
- func Splice(a, b Edge)
- func SwapTriangles(e Edge)
- type Edge
- func (e Edge) Canonical() Edge
- func (e Edge) Dest() uint32
- func (e Edge) DestLoop(visit func(e Edge))
- func (e Edge) DestNext() Edge
- func (e Edge) DestPrev() Edge
- func (e Edge) Left() uint32
- func (e Edge) LeftLoop(visit func(e Edge))
- func (e Edge) LeftNext() Edge
- func (e Edge) LeftPrev() Edge
- func (e Edge) Orig() uint32
- func (e Edge) OrigLoop(visit func(e Edge))
- func (e Edge) OrigNext() Edge
- func (e Edge) OrigPrev() Edge
- func (e Edge) Pool() *Pool
- func (e Edge) Right() uint32
- func (e Edge) RightLoop(visit func(e Edge))
- func (e Edge) RightNext() Edge
- func (e Edge) RightPrev() Edge
- func (e Edge) Rot() Edge
- func (e Edge) SameRing(o Edge) bool
- func (e Edge) SetDest(data uint32)
- func (e Edge) SetLeft(data uint32)
- func (e Edge) SetOrig(data uint32)
- func (e Edge) SetRight(data uint32)
- func (e Edge) String() string
- func (e Edge) Sym() Edge
- func (e Edge) Tor() Edge
- func (e Edge) Walk(visit func(e Edge))
- type Pool
Constants ¶
const ( // Nil is the value used to initialize the origin, destination, left and // right fields of new Edge objects. Nil = 0xFFFFFFFF )
Variables ¶
This section is empty.
Functions ¶
func Delete ¶
func Delete(e Edge)
Delete removes the quad-edge from any edge ring it belongs to.
Note that freeing the corresponding slot in the pool is not yet implemented, so the freed edge still counts as created in regards to pool capacity.
func Splice ¶
func Splice(a, b Edge)
Splice implements the second operator from Guibas and Stolfi Quad-Edge article.
It affects the two origin edge rings of a and b, as well as their two left edge rings: if the two rings are distinct, they are combined into one; if the two rings are the same, they are broken in separate pieces.
In the origin edge rings, the change happens immediately after a.Orig() and b.Orig() (in counterclockwise order); and in the left edge rings, the change happens immediately before a.Left() and b.Left().
func SwapTriangles ¶
func SwapTriangles(e Edge)
SwapTriangles disconnects e, which must have two triangles as left and right faces, and reconnect it to the other two vertices of the quadrilateral formed by the first step. For example, if v1, v2, v3 and v4 form a quadrilateral, and e is a diagonal between v1, and v3, after the swap e will connect v2 to v4.
Types ¶
type Edge ¶
type Edge struct {
// contains filtered or unexported fields
}
An Edge identifies one of the four directed edges of a specific quad-edge. It corresponds to what Guibas and Stolfi call an edge reference. To obtain a new Edge, create a new quad-edge with Pool.New().
Note that for convenience, Edge objects contain a pointer to the pool used to create it.
func Connect ¶
Connect creates and returns a new edge connecting the destination of a to the origin of b, in such a way that a, e and b share the same left face. For convenience, it also sets the origin and destination vertex ID of the new edge (but not the right and left face ID).
func New ¶
New creates a new isolated quad-edge, and returns its canonical directed Edge. It's the MakeEdge operator from Guibas and Stolfi Quad-Edge article.
The quad-edge is set up with separate origin and destination vertices, but same left and right faces. To obtain a loop instead (same origin and destination, different left and right), use New().Rot().
func (Edge) Canonical ¶
Canonical returns the canonical representation of e. All four edges of a quad-edge return the same value.
func (Edge) DestLoop ¶
DestLoop calls visit on every edges in the destination edge-ring of e, in conter-clockwise order (starting with e).
func (Edge) DestNext ¶
DestNext returns the next counter-clockwise edge with the same destination vertex.
func (Edge) DestPrev ¶
DestPrev returns the previous counter-clockwise edge with the same destination vertex.
func (Edge) LeftLoop ¶
LeftLoop calls visit on every edges in the left edge-ring of e, in conter-clockwise order (starting with e).
func (Edge) LeftPrev ¶
LeftPrev returns the previous counter-clockwise edge with the same left face.
func (Edge) OrigLoop ¶
OrigLoop calls visit on every edges in the origin edge-ring of e, in conter-clockwise order (starting with e).
func (Edge) OrigNext ¶
OrigNext returns the next counter-clockwise edge with the same origin vertex.
func (Edge) OrigPrev ¶
OrigPrev returns the previous counter-clockwise edge with the same origin vertex.
func (Edge) RightLoop ¶
RightLoop calls visit on every edges in the right edge-ring of e, in conter-clockwise order (starting with e).
func (Edge) RightPrev ¶
RightPrev returns the previous counter-clockwise edge with the same right face.
func (Edge) Rot ¶
Rot returns the rotated version of e (counter-clockwise), i.e. the edge that belongs to the same quad-edge, but is the dual of e, directed from right to left.
func (Edge) SameRing ¶
SameRing returns true if o is in the origin edge-ring of e (i.e., if the two directed edges share the same origin).
func (Edge) SetDest ¶
SetDest changes the vertex ID of the destination of e. If there is other edges in the same destination edge ring, they will not be updated.
func (Edge) SetLeft ¶
SetLeft changes the face ID at the left of e. Note that if there is other edges with the same left face, they will not be updated.
func (Edge) SetOrig ¶
SetOrig changes the vertex ID of the origin of e. Note that if there is other edges with the same origin, they will not be updated.
func (Edge) SetRight ¶
SetRight changes the face ID at the right of e. Note that if there is other edges with the same right face, they will not be updated.
func (Edge) Sym ¶
Sym returns the symmetric of e, i.e. the edge that belongs to the same quad-edge but with opposite direction.
func (Edge) Tor ¶
Tor returns the inverse rotated version of e (so, clockwise), i.e. the edge that belongs to the same quad-edge, but is the dual of e, directed from left to right. (It is notated Rot⁻¹ in the article)
Source Files