poly2tri

package
v0.0.0-...-a60ced3 Latest Latest
Warning

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

 Go to latest Published: Feb 24, 2024 License: Apache-2.0 Imports: 4 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	PI_3div4 = 3 * math.Pi / 4
	PI_div2  = 1.57079632679489661923
	EPSILON  = 1e-12
)

Variables

This section is empty.

Functions

func InScanArea 

func InScanArea(pa, pb, pc, pd *Point) bool

func PointCmp 

func PointCmp(a, b *Point) bool

Types

type AdvancingFront 

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

func NewAdvancingFront 

func NewAdvancingFront(head, tail *Node) *AdvancingFront

func (*AdvancingFront) AdvancingFront 

func (ad *AdvancingFront) AdvancingFront(head, tail *Node)

func (*AdvancingFront) FindSearchNode 

func (ad *AdvancingFront) FindSearchNode(x float64) *Node

func (*AdvancingFront) Head 

func (ad *AdvancingFront) Head() *Node

func (*AdvancingFront) LocateNode 

func (ad *AdvancingFront) LocateNode(x float64) *Node

func (*AdvancingFront) LocatePoint 

func (ad *AdvancingFront) LocatePoint(point *Point) *Node

func (*AdvancingFront) Search 

func (ad *AdvancingFront) Search() *Node

func (*AdvancingFront) Set_head 

func (ad *AdvancingFront) Set_head(node *Node)
func (ad *AdvancingFront) Set_search(node *Node)

func (*AdvancingFront) Set_tail 

func (ad *AdvancingFront) Set_tail(node *Node)

func (*AdvancingFront) Tail 

func (ad *AdvancingFront) Tail() *Node

type Basin 

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

func NewBasin 

func NewBasin() *Basin

func (*Basin) Clear 

func (b *Basin) Clear()

type CDT 

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

func NewCDT 

func NewCDT(polyline []*Point) *CDT

func (*CDT) AddHole 

func (cdt *CDT) AddHole(polyline []*Point)

func (*CDT) AddPoint 

func (cdt *CDT) AddPoint(point *Point)

func (*CDT) GetMap 

func (cdt *CDT) GetMap() list.List

func (*CDT) GetTriangles 

func (cdt *CDT) GetTriangles() []*Triangle

func (*CDT) Triangulate 

func (cdt *CDT) Triangulate()

type Edge 

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

Represents a simple polygon's edge

func NewEdge 

func NewEdge(p1, p2 *Point) *Edge

type EdgeEvent 

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

type Node 

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

func NewNode 

func NewNode(p *Point) *Node

func NewNodeWithTriangle 

func NewNodeWithTriangle(p *Point, t *Triangle) *Node

type Orientation 

type Orientation int
const (
	CW Orientation = iota
	CCW
	COLLINEAR
)

func Orient2d 

func Orient2d(pa, pb, pc *Point) Orientation

*

  • Forumla to calculate signed area<br>
  • Positive if CCW<br>
  • Negative if CW<br>
  • 0 if collinear<br>
  • <pre>
  • A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
  • = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
  • </pre>

type Point 

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

func NewPoint 

func NewPoint(x, y float64) *Point

func (*Point) Add 

func (p *Point) Add(v *Point)

func (*Point) Length 

func (p *Point) Length() float64

func (*Point) Mul 

func (p *Point) Mul(a float64)

func (*Point) Negative 

func (p *Point) Negative() *Point

func (*Point) Normalize 

func (p *Point) Normalize() float64

func (*Point) SetPoint 

func (p *Point) SetPoint(x, y float64)

func (*Point) SetZero 

func (p *Point) SetZero()

func (*Point) Sub 

func (p *Point) Sub(v *Point)

type Sweep 

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

func NewSweep 

func NewSweep() *Sweep

func (*Sweep) Angle 

func (s *Sweep) Angle(origin, pa, pb *Point) float64

func (*Sweep) AngleExceeds90Degrees 

func (s *Sweep) AngleExceeds90Degrees(origin, pa, pb *Point) bool

func (*Sweep) AngleExceedsPlus90DegreesOrIsNegative 

func (s *Sweep) AngleExceedsPlus90DegreesOrIsNegative(origin, pa, pb *Point) bool

func (*Sweep) BasinAngle 

func (s *Sweep) BasinAngle(node *Node) float64

func (*Sweep) EdgeEvent 

func (s *Sweep) EdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) EdgeEvent1 

func (s *Sweep) EdgeEvent1(tcx *SweepContext, ep, eq *Point, triangle *Triangle, point *Point)

func (*Sweep) Fill 

func (s *Sweep) Fill(tcx *SweepContext, node *Node)

func (*Sweep) FillAdvancingFront 

func (s *Sweep) FillAdvancingFront(tcx *SweepContext, n *Node)

func (*Sweep) FillBasin 

func (s *Sweep) FillBasin(tcx *SweepContext, node *Node)

func (*Sweep) FillBasinReq 

func (s *Sweep) FillBasinReq(tcx *SweepContext, node *Node)

func (*Sweep) FillEdgeEvent 

func (s *Sweep) FillEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillLeftAboveEdgeEvent 

func (s *Sweep) FillLeftAboveEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillLeftBelowEdgeEvent 

func (s *Sweep) FillLeftBelowEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillLeftConcaveEdgeEvent 

func (s *Sweep) FillLeftConcaveEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillLeftConvexEdgeEvent 

func (s *Sweep) FillLeftConvexEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillRightAboveEdgeEvent 

func (s *Sweep) FillRightAboveEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillRightBelowEdgeEvent 

func (s *Sweep) FillRightBelowEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillRightConcaveEdgeEvent 

func (s *Sweep) FillRightConcaveEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FillRightConvexEdgeEvent 

func (s *Sweep) FillRightConvexEdgeEvent(tcx *SweepContext, edge *Edge, node *Node)

func (*Sweep) FinalizationPolygon 

func (s *Sweep) FinalizationPolygon(tcx *SweepContext)

func (*Sweep) FlipEdgeEvent 

func (s *Sweep) FlipEdgeEvent(tcx *SweepContext, ep, eq *Point, t *Triangle, p *Point)

func (*Sweep) FlipScanEdgeEvent 

func (s *Sweep) FlipScanEdgeEvent(tcx *SweepContext, ep, eq *Point, flip_triangle *Triangle,
	t *Triangle, p *Point)

func (*Sweep) HoleAngle 

func (s *Sweep) HoleAngle(node *Node) float64

func (*Sweep) Incircle 

func (s *Sweep) Incircle(pa, pb, pc, pd *Point) bool

func (*Sweep) IsEdgeSideOfTriangle 

func (s *Sweep) IsEdgeSideOfTriangle(triangle *Triangle, ep, eq *Point) bool

func (*Sweep) IsShallow 

func (s *Sweep) IsShallow(tcx *SweepContext, node *Node) bool

func (*Sweep) LargeHole_DontFill 

func (s *Sweep) LargeHole_DontFill(node *Node) bool

True if HoleAngle exceeds 90 degrees.

func (*Sweep) Legalize 

func (s *Sweep) Legalize(tcx *SweepContext, t *Triangle) bool

func (*Sweep) NewFrontTriangle 

func (s *Sweep) NewFrontTriangle(tcx *SweepContext, point *Point, node *Node) *Node

func (*Sweep) NextFlipPoint 

func (s *Sweep) NextFlipPoint(ep, eq *Point, ot *Triangle, op *Point) *Point

func (*Sweep) NextFlipTriangle 

func (s *Sweep) NextFlipTriangle(tcx *SweepContext, o Orientation, t, ot *Triangle, p, op *Point) *Triangle

func (*Sweep) PointEvent 

func (s *Sweep) PointEvent(tcx *SweepContext, point *Point) *Node

func (*Sweep) RotateTrianglePair 

func (s *Sweep) RotateTrianglePair(t *Triangle, p *Point, ot *Triangle, op *Point)

func (*Sweep) SweepPoints 

func (s *Sweep) SweepPoints(tcx *SweepContext)

func (*Sweep) Triangulate 

func (s *Sweep) Triangulate(tcx *SweepContext)

Triangulate simple polygon with holes

type SweepContext 

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

func NewSweepContext 

func NewSweepContext(polyline []*Point) *SweepContext

func (*SweepContext) AddHole 

func (s *SweepContext) AddHole(polyline []*Point)

func (*SweepContext) AddPoint 

func (s *SweepContext) AddPoint(point *Point)

func (*SweepContext) AddToMap 

func (s *SweepContext) AddToMap(triangle *Triangle)

func (*SweepContext) CreateAdvancingFront 

func (s *SweepContext) CreateAdvancingFront(nodes []*Node)

func (*SweepContext) Front 

func (s *SweepContext) Front() *AdvancingFront

func (*SweepContext) GetMap 

func (s *SweepContext) GetMap() list.List

func (*SweepContext) GetPoint 

func (s *SweepContext) GetPoint(index int) *Point

func (*SweepContext) GetTriangles 

func (s *SweepContext) GetTriangles() []*Triangle

func (*SweepContext) Head 

func (s *SweepContext) Head() *Point

func (*SweepContext) InitEdges 

func (s *SweepContext) InitEdges(polyline []*Point)

func (*SweepContext) InitTriangulation 

func (s *SweepContext) InitTriangulation()

func (*SweepContext) LocateNode 

func (s *SweepContext) LocateNode(point *Point) *Node

func (*SweepContext) MapTriangleToNodes 

func (s *SweepContext) MapTriangleToNodes(t *Triangle)

func (*SweepContext) MeshClean 

func (s *SweepContext) MeshClean(triangle *Triangle)

func (*SweepContext) RemoveFromMap 

func (s *SweepContext) RemoveFromMap(triangle *Triangle)

func (*SweepContext) Set_tail 

func (s *SweepContext) Set_tail(p1 *Point)

func (*SweepContext) Tail 

func (s *SweepContext) Tail() *Point

type Triangle 

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

func NewTriangle 

func NewTriangle(a, b, c *Point) *Triangle

func (*Triangle) Add 

func (tri *Triangle) Add(a, b *Point) *Point

func (*Triangle) Clear 

func (tri *Triangle) Clear()

*

  • Clears all references to all other triangles and points

func (*Triangle) ClearDelunayEdges 

func (tri *Triangle) ClearDelunayEdges()

func (*Triangle) ClearNeighbor 

func (tri *Triangle) ClearNeighbor(triangle *Triangle)

func (*Triangle) ClearNeighbors 

func (tri *Triangle) ClearNeighbors()

func (*Triangle) ContainsEdge 

func (tri *Triangle) ContainsEdge(e *Edge) bool

func (*Triangle) ContainsPoint 

func (tri *Triangle) ContainsPoint(p *Point) bool

func (*Triangle) ContainsPoints 

func (tri *Triangle) ContainsPoints(p *Point, q *Point) bool

func (*Triangle) Cross 

func (tri *Triangle) Cross(a, b *Point) float64

/ Perform the cross product on two vectors. In 2D this produces a scalar.

func (*Triangle) Cross1 

func (tri *Triangle) Cross1(a *Point, s float64) *Point

/ Perform the cross product on a point and a scalar. In 2D this produces / a point.

func (*Triangle) Cross2 

func (tri *Triangle) Cross2(s float64, a *Point) *Point

/ Perform the cross product on a scalar and a point. In 2D this produces / a point.

func (*Triangle) DebugPrint 

func (tri *Triangle) DebugPrint()

func (*Triangle) Dot 

func (tri *Triangle) Dot(a, b *Point) float64

/ Peform the dot product on two vectors.

func (*Triangle) EdgeIndex 

func (tri *Triangle) EdgeIndex(p1, p2 *Point) int

func (*Triangle) GetConstrainedEdgeCCW 

func (tri *Triangle) GetConstrainedEdgeCCW(p *Point) bool

func (*Triangle) GetConstrainedEdgeCW 

func (tri *Triangle) GetConstrainedEdgeCW(p *Point) bool

func (*Triangle) GetDelunayEdgeCCW 

func (tri *Triangle) GetDelunayEdgeCCW(p *Point) bool

func (*Triangle) GetDelunayEdgeCW 

func (tri *Triangle) GetDelunayEdgeCW(p *Point) bool

func (*Triangle) GetNeighbor 

func (tri *Triangle) GetNeighbor(index int) *Triangle

func (*Triangle) GetPoint 

func (tri *Triangle) GetPoint(index int) *Point

func (*Triangle) Index 

func (tri *Triangle) Index(p *Point) int

func (*Triangle) IsInterior 

func (tri *Triangle) IsInterior() bool

func (*Triangle) Legalize 

func (tri *Triangle) Legalize(point *Point)

Legalized triangle by rotating clockwise around point(0)

func (*Triangle) Legalize1 

func (tri *Triangle) Legalize1(opoint *Point, npoint *Point)

Legalize triagnle by rotating clockwise around oPoint

func (*Triangle) MarkConstrainedEdge 

func (tri *Triangle) MarkConstrainedEdge(p, q *Point)

Mark edge as constrained

func (*Triangle) MarkConstrainedEdgeEdge 

func (tri *Triangle) MarkConstrainedEdgeEdge(edge *Edge)

func (*Triangle) MarkConstrainedEdgeIndex 

func (tri *Triangle) MarkConstrainedEdgeIndex(index int)

func (*Triangle) MarkNeighbor 

func (tri *Triangle) MarkNeighbor(t *Triangle)

Exhaustive search to update neighbor pointers

func (*Triangle) MarkNeighborPointers 

func (tri *Triangle) MarkNeighborPointers(p1, p2 *Point, t *Triangle)

Update neighbor pointers

func (*Triangle) Mul 

func (tri *Triangle) Mul(s float64, a *Point) *Point

func (*Triangle) NeighborAcross 

func (tri *Triangle) NeighborAcross(opoint *Point) *Triangle

The neighbor across to given point

func (*Triangle) NeighborCCW 

func (tri *Triangle) NeighborCCW(point *Point) *Triangle

The neighbor counter-clockwise to given point

func (*Triangle) NeighborCW 

func (tri *Triangle) NeighborCW(point *Point) *Triangle

The neighbor clockwise to given point

func (*Triangle) OppositePoint 

func (tri *Triangle) OppositePoint(t *Triangle, p *Point) *Point

func (*Triangle) PointCCW 

func (tri *Triangle) PointCCW(point *Point) *Point

The point counter-clockwise to given point

func (*Triangle) PointCW 

func (tri *Triangle) PointCW(point *Point) *Point

The point counter-clockwise to given point

func (*Triangle) SetConstrainedEdgeCCW 

func (tri *Triangle) SetConstrainedEdgeCCW(p *Point, ce bool)

func (*Triangle) SetConstrainedEdgeCW 

func (tri *Triangle) SetConstrainedEdgeCW(p *Point, ce bool)

func (*Triangle) SetDelunayEdgeCCW 

func (tri *Triangle) SetDelunayEdgeCCW(p *Point, e bool)

func (*Triangle) SetDelunayEdgeCW 

func (tri *Triangle) SetDelunayEdgeCW(p *Point, e bool)

func (*Triangle) SetInterior 

func (tri *Triangle) SetInterior(b bool)

func (*Triangle) Sub 

func (tri *Triangle) Sub(a, b *Point) *Point

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.