quadedge

package
v0.0.4 Latest Latest
Warning

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

 Go to latest Published: Oct 31, 2023 License: MIT Imports: 11 Imported by: 0

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

View Source 
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
)
View Source 
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")
)
View Source 
const (
	Rot = Operation(iota)
	InvRot
	Sym
	ONext
	OPrev
	DNext
	DPrev
	LNext
	LPrev
	RNext
	RPrev
)

Variables

This section is empty.

Functions

func Delete 

func Delete(e *Edge)

Delete will remove the edge from the ring

func OnEdge 

func OnEdge(pt geom.Point, e *Edge) bool

OnEdge determines if the point x is on the edge e.

func RightOf 

func RightOf(yflip bool, x geom.Point, e *Edge) bool

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.

func Swap 

func Swap(e *Edge)

Swap Essentially turns edge e counterclockwise inside its enclosing quadrilateral. The data pointers are modified accordingly.

func Validate 

func Validate(e *Edge, order winding.Order) (err1 error)

Validate check to se if the edges in the edges are correctly oriented

Types

type Edge 

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

Edge describes a directional edge in a quadedge

func BuildEdgeGraphAroundPoint 

func BuildEdgeGraphAroundPoint(ocoord geom.Point, dcoords ...geom.Point) *Edge

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 

func Connect(a, b *Edge, order winding.Order) *Edge

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 New 

func New() *Edge

New will return a new edge that is part of an QuadEdge

func NewWithEndPoints 

func NewWithEndPoints(a, b *geom.Point) *Edge

NewWithEndPoints creates a new edge with the given end points

func ResolveEdge 

func ResolveEdge(order winding.Order, gse *Edge, odest geom.Point) (*Edge, error)

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 

func (e *Edge) Apply(ops ...Operation) *Edge

Apply will return the edge after the given operation have been applied to the Edge

func (*Edge) AsLine 

func (e *Edge) AsLine() geom.Line

AsLine returns the Edge as a geom.Line

func (*Edge) DNext 

func (e *Edge) DNext() *Edge

DNext returns the next ccw edge around (into) the destination of the current edge.

func (*Edge) DPrev 

func (e *Edge) DPrev() *Edge

DPrev returns the next cw edge around (into) the destination of the current edge.

func (*Edge) Dest 

func (e *Edge) Dest() *geom.Point

Dest returns the destination end point

func (*Edge) DumpAllEdges 

func (e *Edge) DumpAllEdges() string

DumpAllEdges dumps all the edges as a multiline string

func (*Edge) EndPoints 

func (e *Edge) EndPoints(org, dest *geom.Point)

EndPoints sets the end points of the Edge

func (*Edge) FindONextDest 

func (e *Edge) FindONextDest(dest geom.Point) *Edge

FindONextDest will look for and return a ccw edge the given dest point, if it exists.

func (*Edge) InvRot 

func (e *Edge) InvRot() *Edge

InvRot returns the dual of the current edge, directed from its left to its right.

func (*Edge) IsEqual 

func (e *Edge) IsEqual(e1 *Edge) bool

IsEqual checks to see if the edges are the same

func (*Edge) LNext 

func (e *Edge) LNext() *Edge

LNext returns the ccw edge around the left face following the current edge.

func (*Edge) LPrev 

func (e *Edge) LPrev() *Edge

LPrev returns the ccw edge around the left face before the current edge.

func (*Edge) ONext 

func (e *Edge) ONext() *Edge

ONext returns the next ccw edge around (from) the origin of the current edge

func (*Edge) OPrev 

func (e *Edge) OPrev() *Edge

OPrev returns the next cw edge around (from) the origin of the current edge.

func (*Edge) Orig 

func (e *Edge) Orig() *geom.Point

Orig returns the origin end point

func (*Edge) QEdge 

func (e *Edge) QEdge() *QuadEdge

QEdge returns the quadedge this edge is part of

func (*Edge) RNext 

func (e *Edge) RNext() *Edge

RNext returns the edge around the right face ccw following the current edge.

func (*Edge) RPrev 

func (e *Edge) RPrev() *Edge

RPrev returns the edge around the right face ccw before the current edge.

func (*Edge) Rot 

func (e *Edge) Rot() *Edge

Rot returns the dual of the current edge, directed from its right to its left.

func (*Edge) Sym 

func (e *Edge) Sym() *Edge

Sym returns the edge from the destination to the origin of the current edge.

func (*Edge) WalkAllONext 

func (e *Edge) WalkAllONext(fn func(*Edge) (loop bool))

func (*Edge) WalkAllOPrev 

func (e *Edge) WalkAllOPrev(fn func(*Edge) (loop bool))

type ErrInvalid 

type ErrInvalid []string

ErrInvalid is returned when the type is invalid and the reason why it's invalid

func (ErrInvalid) Error 

func (err ErrInvalid) Error() string

Error fullfils the errorer interface

type Operation 

type Operation uint8

Operation defines QuadEdge Algebra Operation that can be done

type QType 

type QType uint

QType describes the classification of a point to a line

func Classify 

func Classify(a, b, c geom.Point) QType

Classify returns where b is in realation to a and c.

func (QType) String 

func (q QType) String() string

type QuadEdge 

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

QuadEdge describes a quadedge object. Which is made up of four directional edges

func NewQEdge 

func NewQEdge() *QuadEdge

NewQEdge create a new quad edge object

func (*QuadEdge) Init 

func (qe *QuadEdge) Init()

type Stack 

type Stack []*Edge

Stack is a stack of edges

func (Stack) Length 

func (s Stack) Length() int

Length will return the length of the stack

func (*Stack) Pop 

func (s *Stack) Pop() (e *Edge)

Pop will return the last edge added and remove it from the stack.

func (*Stack) Push 

func (s *Stack) Push(e *Edge)

Push will add an edge to the stack

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.