Documentation
¶
Overview ¶
Package quadedge describes a quadedge object used to build up the triangulation A quadedge is made up of four directional edges
DO
^*
||
O*----++---->D
L D<----++----*O R
||
*V
OD
O represents the Origin
D represents the Destination
Index ¶
- Constants
- func Delete(e *Edge)
- func OnEdge(pt geom.Point, e *Edge) bool
- func RightOf(yflip bool, x geom.Point, e *Edge) bool
- func Splice(a, b *Edge)
- func Swap(e *Edge)
- func Validate(e *Edge, order winding.Order) (err1 error)
- type Edge
- func (e *Edge) Apply(ops ...Operation) *Edge
- func (e *Edge) AsLine() geom.Line
- func (e *Edge) DNext() *Edge
- func (e *Edge) DPrev() *Edge
- func (e *Edge) Dest() *geom.Point
- func (e *Edge) DumpAllEdges() string
- func (e *Edge) EndPoints(org, dest *geom.Point)
- func (e *Edge) FindONextDest(dest geom.Point) *Edge
- func (e *Edge) InvRot() *Edge
- func (e *Edge) IsEqual(e1 *Edge) bool
- func (e *Edge) LNext() *Edge
- func (e *Edge) LPrev() *Edge
- func (e *Edge) ONext() *Edge
- func (e *Edge) OPrev() *Edge
- func (e *Edge) Orig() *geom.Point
- func (e *Edge) QEdge() *QuadEdge
- func (e *Edge) RNext() *Edge
- func (e *Edge) RPrev() *Edge
- func (e *Edge) Rot() *Edge
- func (e *Edge) Sym() *Edge
- func (e *Edge) WalkAllONext(fn func(*Edge) (loop bool))
- func (e *Edge) WalkAllOPrev(fn func(*Edge) (loop bool))
- type ErrInvalid
- type Operation
- type QType
- type QuadEdge
- type Stack
Constants ¶
const ( // LEFT indicates that the point is left of the line LEFT = QType(iota) // RIGHT indicates that the point is right of the line RIGHT // BEYOND indicates that the point is beyond the line BEYOND // BEHIND indicates that the point is behind the line BEHIND // BETWEEN indicates that the point is between the endpoints of the line BETWEEN // ORIGIN indicates that the point is at the origin of the line ORIGIN // DESTINATION indicates that the point is at the destination of the line DESTINATION )
const ( // ErrInvalidStartingVertex is returned when the starting vertex is invalid ErrInvalidStartingVertex = errors.String("invalid starting vertex") // ErrInvalidEndVertex is returned when the ending vertex is invalid ErrInvalidEndVertex = errors.String("invalid ending vertex") // ErrCoincidentalEdges is returned when two edges are conincidental and not expected to be ErrCoincidentalEdges = errors.String("coincident edges") )
const ( Rot = Operation(iota) InvRot Sym ONext OPrev DNext DPrev LNext LPrev RNext RPrev )
Variables ¶
This section is empty.
Functions ¶
func RightOf ¶
RightOf indicates if the point is right of the Edge If a point is below the line it is to it's right If a point is above the line it is to it's left
func Splice ¶
func Splice(a, b *Edge)
Splice operator affects the two edge rings around the origin of a and b, and, independently, the two edge rings around the left faces of a and b. In each case, (i) if the two rings are distinct, Splace will combine them into one; (ii) if the two are the same ring, Splice will break it into two separate pieces. Thus, Splice can be used both to attach the two edges together, and to break them apart. See Guibas and Stolfi (1985) p.96 for more details and illustrations.
Types ¶
type Edge ¶
type Edge struct {
// contains filtered or unexported fields
}
Edge describes a directional edge in a quadedge
func BuildEdgeGraphAroundPoint ¶
BuildEdgeGraphAroundPoint will build an edge and it's surounding point as the points are listed. Points should be listed in counter-clockwise order for it to build a valid edge graph
func Connect ¶
Connect Adds a new edge (e) connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete. Additionally, the data pointers of the new edge are set.
func NewWithEndPoints ¶
NewWithEndPoints creates a new edge with the given end points
func ResolveEdge ¶
ResolveEdge will find the edge such that dest lies between it and it's next edge. It does this using the following table:
ab -- orientation of a to b, (a being the edge of consideration) da -- orientation of destPoint and a db -- orientation of destPoint and b ⟲ -- counter-clockwise ⟳ -- clockwise O -- colinear +----+----+----+----+ | # | ab | da | db | return - comment +----+----+----+----+ 8 | 1 | ⟲ | ⟲ | ⟲ | next 2 : 5 | 2 | ⟲ | ⟲ | ⟳ | next .3....+----6->b | 3 | ⟲ | ⟲ | O | next 1 |,,4,,, | 4 | ⟲ | ⟳ | ⟲ | a 7,,,,,, ab = ⟲ == next orientation | 5 | ⟲ | ⟳ | ⟳ | next V | 6 | ⟲ | ⟳ | O | b -- ErrColinearPoints a | 7 | ⟲ | O | ⟲ | a -- ErrColinearPoints | 8 | ⟲ | O | ⟳ | next | + | ⟲ | O | O | point is at origin : Err ,,,,,,,14,,,, | 9 | ⟳ | ⟲ | ⟲ | a ,,,,12,:,,13, | 10 | ⟳ | ⟲ | ⟳ | next .15....+----16>a | 11 | ⟳ | ⟲ | O | b -- ErrColinearPoints ,,,,9,,| 10 | 12 | ⟳ | ⟳ | ⟲ | a ,,,,,,,11 ab = ⟳ == opposite of next orientation | 13 | ⟳ | ⟳ | ⟳ | a V | 14 | ⟳ | ⟳ | O | a b | 15 | ⟳ | O | ⟲ | a | 16 | ⟳ | O | ⟳ | a -- ErrColinearPoints | + | ⟳ | O | O | point is at origin : Err ,,,,,,,18,,,,, | 17 | O | ⟲ | ⟳ | next b-19----+---19->a | 18 | O | ⟳ | ⟲ | a 17 | 19 | O | O | O | a/b -- ErrColinearPoint a/b depending on which one contains dest | 20 | O | ⟲ | ⟲ | a -- ErrCoincidentalEdges 21 | 21 | O | ⟳ | ⟳ | a -- ErrCoincidentalEdges .......+------>a,b +----+----+-----+----+ 20 if ab == O and da == O then db must be O
Only errors returned are
- nil // nothing is wrong
- ErrInvalidateEndVertex
- ErrConcidentalEdges
- geom.ErrColinearPoints
func (*Edge) Apply ¶
Apply will return the edge after the given operation have been applied to the Edge
func (*Edge) DNext ¶
DNext returns the next ccw edge around (into) the destination of the current edge.
func (*Edge) DPrev ¶
DPrev returns the next cw edge around (into) the destination of the current edge.
func (*Edge) DumpAllEdges ¶
DumpAllEdges dumps all the edges as a multiline string
func (*Edge) FindONextDest ¶
FindONextDest will look for and return a ccw edge the given dest point, if it exists.
func (*Edge) InvRot ¶
InvRot returns the dual of the current edge, directed from its left to its right.
func (*Edge) WalkAllONext ¶
func (*Edge) WalkAllOPrev ¶
type ErrInvalid ¶
type ErrInvalid []string
ErrInvalid is returned when the type is invalid and the reason why it's invalid
type QType ¶
type QType uint
QType describes the classification of a point to a line
type QuadEdge ¶
type QuadEdge struct {
// contains filtered or unexported fields
}
QuadEdge describes a quadedge object. Which is made up of four directional edges
Source Files