poly2tri

package module
v0.0.0-...-d102ad9 Latest Latest
Warning

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

 Go to latest Published: Jul 16, 2017 License: BSD-3-Clause Imports: 3 Imported by: 12

README

poly2tri-go

Golang port of poly2tri.js

The license of poly2tri-go is the same as poly2tri.js; consult it here https://github.com/r3mi/poly2tri.js/blob/master/LICENSE.txt

Usage example : (triangulation of "Dude with 2 holes", taken from here: http://r3mi.github.io/poly2tri.js/)

package main

import (
	"fmt"
	"github.com/netgusto/poly2tri-go"
)

func main() {
	contour := []*poly2tri.Point{
		poly2tri.NewPoint(280.35714, 648.79075),
		poly2tri.NewPoint(286.78571, 662.8979),
		poly2tri.NewPoint(263.28607, 661.17871),
		poly2tri.NewPoint(262.31092, 671.41548),
		poly2tri.NewPoint(250.53571, 677.00504),
		poly2tri.NewPoint(250.53571, 683.43361),
		poly2tri.NewPoint(256.42857, 685.21933),
		poly2tri.NewPoint(297.14286, 669.50504),
		poly2tri.NewPoint(289.28571, 649.50504),
		poly2tri.NewPoint(285.0, 631.6479),
		poly2tri.NewPoint(285.0, 608.79075),
		poly2tri.NewPoint(292.85714, 585.21932),
		poly2tri.NewPoint(306.42857, 563.79075),
		poly2tri.NewPoint(323.57143, 548.79075),
		poly2tri.NewPoint(339.28571, 545.21932),
		poly2tri.NewPoint(357.85714, 547.36218),
		poly2tri.NewPoint(375.0, 550.21932),
		poly2tri.NewPoint(391.42857, 568.07647),
		poly2tri.NewPoint(404.28571, 588.79075),
		poly2tri.NewPoint(413.57143, 612.36218),
		poly2tri.NewPoint(417.14286, 628.07647),
		poly2tri.NewPoint(438.57143, 619.1479),
		poly2tri.NewPoint(438.03572, 618.96932),
		poly2tri.NewPoint(437.5, 609.50504),
		poly2tri.NewPoint(426.96429, 609.86218),
		poly2tri.NewPoint(424.64286, 615.57647),
		poly2tri.NewPoint(419.82143, 615.04075),
		poly2tri.NewPoint(420.35714, 605.04075),
		poly2tri.NewPoint(428.39286, 598.43361),
		poly2tri.NewPoint(437.85714, 599.68361),
		poly2tri.NewPoint(443.57143, 613.79075),
		poly2tri.NewPoint(450.71429, 610.21933),
		poly2tri.NewPoint(431.42857, 575.21932),
		poly2tri.NewPoint(405.71429, 550.21932),
		poly2tri.NewPoint(372.85714, 534.50504),
		poly2tri.NewPoint(349.28571, 531.6479),
		poly2tri.NewPoint(346.42857, 521.6479),
		poly2tri.NewPoint(346.42857, 511.6479),
		poly2tri.NewPoint(350.71429, 496.6479),
		poly2tri.NewPoint(367.85714, 476.6479),
		poly2tri.NewPoint(377.14286, 460.93361),
		poly2tri.NewPoint(385.71429, 445.21932),
		poly2tri.NewPoint(388.57143, 404.50504),
		poly2tri.NewPoint(360.0, 352.36218),
		poly2tri.NewPoint(337.14286, 325.93361),
		poly2tri.NewPoint(330.71429, 334.50504),
		poly2tri.NewPoint(347.14286, 354.50504),
		poly2tri.NewPoint(337.85714, 370.21932),
		poly2tri.NewPoint(333.57143, 359.50504),
		poly2tri.NewPoint(319.28571, 353.07647),
		poly2tri.NewPoint(312.85714, 366.6479),
		poly2tri.NewPoint(350.71429, 387.36218),
		poly2tri.NewPoint(368.57143, 408.07647),
		poly2tri.NewPoint(375.71429, 431.6479),
		poly2tri.NewPoint(372.14286, 454.50504),
		poly2tri.NewPoint(366.42857, 462.36218),
		poly2tri.NewPoint(352.85714, 462.36218),
		poly2tri.NewPoint(336.42857, 456.6479),
		poly2tri.NewPoint(332.85714, 438.79075),
		poly2tri.NewPoint(338.57143, 423.79075),
		poly2tri.NewPoint(338.57143, 411.6479),
		poly2tri.NewPoint(327.85714, 405.93361),
		poly2tri.NewPoint(320.71429, 407.36218),
		poly2tri.NewPoint(315.71429, 423.07647),
		poly2tri.NewPoint(314.28571, 440.21932),
		poly2tri.NewPoint(325.0, 447.71932),
		poly2tri.NewPoint(324.82143, 460.93361),
		poly2tri.NewPoint(317.85714, 470.57647),
		poly2tri.NewPoint(304.28571, 483.79075),
		poly2tri.NewPoint(287.14286, 491.29075),
		poly2tri.NewPoint(263.03571, 498.61218),
		poly2tri.NewPoint(251.60714, 503.07647),
		poly2tri.NewPoint(251.25, 533.61218),
		poly2tri.NewPoint(260.71429, 533.61218),
		poly2tri.NewPoint(272.85714, 528.43361),
		poly2tri.NewPoint(286.07143, 518.61218),
		poly2tri.NewPoint(297.32143, 508.25504),
		poly2tri.NewPoint(297.85714, 507.36218),
		poly2tri.NewPoint(298.39286, 506.46932),
		poly2tri.NewPoint(307.14286, 496.6479),
		poly2tri.NewPoint(312.67857, 491.6479),
		poly2tri.NewPoint(317.32143, 503.07647),
		poly2tri.NewPoint(322.5, 514.1479),
		poly2tri.NewPoint(325.53571, 521.11218),
		poly2tri.NewPoint(327.14286, 525.75504),
		poly2tri.NewPoint(326.96429, 535.04075),
		poly2tri.NewPoint(311.78571, 540.04075),
		poly2tri.NewPoint(291.07143, 552.71932),
		poly2tri.NewPoint(274.82143, 568.43361),
		poly2tri.NewPoint(259.10714, 592.8979),
		poly2tri.NewPoint(254.28571, 604.50504),
		poly2tri.NewPoint(251.07143, 621.11218),
		poly2tri.NewPoint(250.53571, 649.1479),
		poly2tri.NewPoint(268.1955, 654.36208),
	}

	swctx := poly2tri.NewSweepContext(contour, false)
	swctx.AddHole([]*poly2tri.Point{
		poly2tri.NewPoint(325, 437),
		poly2tri.NewPoint(320, 423),
		poly2tri.NewPoint(329, 413),
		poly2tri.NewPoint(332, 423),
	})

	swctx.AddHole([]*poly2tri.Point{
		poly2tri.NewPoint(320.72342, 480),
		poly2tri.NewPoint(338.90617, 465.96863),
		poly2tri.NewPoint(347.99754, 480.61584),
		poly2tri.NewPoint(329.8148, 510.41534),
		poly2tri.NewPoint(339.91632, 480.11077),
		poly2tri.NewPoint(334.86556, 478.09046),
	})

	swctx.Triangulate()
	triangles := swctx.GetTriangles()

	fmt.Println(triangles)
}

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var EPSILON = 0.00001
View Source 
var Orientation = map[string]int{
	"CW":       1,
	"CCW":      -1,
	"COLINEAR": 0,
}

Functions

func Assert 

func Assert(condition bool, message string)

func EdgeEventByEdge 

func EdgeEventByEdge(tcx *SweepContext, edge *Edge, node *Node)

func EdgeEventByPoints 

func EdgeEventByPoints(tcx *SweepContext, ep *Point, eq *Point, triangle *Triangle, point *Point)

func Fill 

func Fill(tcx *SweepContext, node *Node)

func FillAdvancingFront 

func FillAdvancingFront(tcx *SweepContext, n *Node)

func FillBasin 

func FillBasin(tcx *SweepContext, node *Node)

func FillBasinReq 

func FillBasinReq(tcx *SweepContext, node *Node)

func FillEdgeEvent 

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

func FillLeftAboveEdgeEvent 

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

func FillLeftBelowEdgeEvent 

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

func FillLeftConcaveEdgeEvent 

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

func FillLeftConvexEdgeEvent 

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

func FillRightAboveEdgeEvent 

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

func FillRightBelowEdgeEvent 

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

func FillRightConcaveEdgeEvent 

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

func FillRightConvexEdgeEvent 

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

func FinalizationPolygon 

func FinalizationPolygon(tcx *SweepContext)

func FlipEdgeEvent 

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

func FlipScanEdgeEvent 

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

func InCircle 

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

func InScanArea 

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

func IsAngleObtuse 

func IsAngleObtuse(pa, pb, pc *Point) bool

func IsBasinAngleRight 

func IsBasinAngleRight(node *Node) bool

func IsEdgeSideOfTriangle 

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

func IsShallow 

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

func Legalize 

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

func Orient2d 

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

func PointCompare 

func PointCompare(a, b *Point) float64

func PointCross 

func PointCross(a, b *Point)

func PointDot 

func PointDot(a, b XYInterface) float64

func PointEquals 

func PointEquals(a, b *Point) bool

func PointString 

func PointString(a *Point) string

func RotateTrianglePair 

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

func SweepPoints 

func SweepPoints(tcx *SweepContext)

func Triangulate 

func Triangulate(tcx *SweepContext)

func XYCompare 

func XYCompare(a, b XYInterface) float64

func XYCompareFloat 

func XYCompareFloat(a, b float64) float64

func XYEquals 

func XYEquals(a, b XYInterface) bool

func XYEqualsFloat 

func XYEqualsFloat(a, b float64) bool

func XYString 

func XYString(a XYInterface) string

Types

type AdvancingFront 

type AdvancingFront struct {
	Head       *Node
	Tail       *Node
	SearchNode *Node
}

func NewAdvancingFront 

func NewAdvancingFront(head, tail *Node) *AdvancingFront

func (*AdvancingFront) FindSearchNode 

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

func (*AdvancingFront) GetHead 

func (af *AdvancingFront) GetHead() *Node

func (*AdvancingFront) GetSearch 

func (af *AdvancingFront) GetSearch() *Node

func (*AdvancingFront) GetTail 

func (af *AdvancingFront) GetTail() *Node

func (*AdvancingFront) LocateNode 

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

func (*AdvancingFront) LocatePoint 

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

func (*AdvancingFront) SetHead 

func (af *AdvancingFront) SetHead(node *Node)

func (*AdvancingFront) SetSearch 

func (af *AdvancingFront) SetSearch(node *Node)

func (*AdvancingFront) SetTail 

func (af *AdvancingFront) SetTail(node *Node)

type Basin 

type Basin struct {
	LeftNode    *Node
	BottomNode  *Node
	RightNode   *Node
	Width       float64
	LeftHighest bool
}

func NewBasin 

func NewBasin() *Basin

type Edge 

type Edge struct {
	P *Point
	Q *Point
}

func NewEdge 

func NewEdge(p1, p2 *Point) *Edge

type EdgeEvent 

type EdgeEvent struct {
	ConstrainedEdge *Edge
	Right           bool
}

func NewEdgeEvent 

func NewEdgeEvent() *EdgeEvent

type Node 

type Node struct {
	Point    *Point
	Triangle *Triangle
	Next     *Node
	Prev     *Node
	Value    float64
}

func NewFrontTriangle 

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

func NewNode 

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

func PointEvent 

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

type Point 

type Point struct {
	X     float64
	Y     float64
	Edges []*Edge
}

func NewPoint 

func NewPoint(x, y float64) *Point

func NextFlipPoint 

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

func PointAdd 

func PointAdd(a, b *Point) *Point

func PointMul 

func PointMul(a, b *Point) *Point

func PointNegate 

func PointNegate(p *Point) *Point

func PointSub 

func PointSub(a, b *Point) *Point

func (*Point) Add 

func (p *Point) Add(n XYInterface) *Point

func (*Point) Clone 

func (p *Point) Clone() *Point

func (*Point) Equals 

func (p *Point) Equals(p2 XYInterface) bool

func (*Point) GetX 

func (p *Point) GetX() float64

func (*Point) GetY 

func (p *Point) GetY() float64

func (*Point) Length 

func (p *Point) Length() float64

func (*Point) Mul 

func (p *Point) Mul(n XYInterface) *Point

func (*Point) Negate 

func (p *Point) Negate() *Point

func (*Point) Normalize 

func (p *Point) Normalize() float64

func (*Point) Set 

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

func (*Point) SetZero 

func (p *Point) SetZero() *Point

func (*Point) String 

func (p *Point) String() string

func (*Point) Sub 

func (p *Point) Sub(n XYInterface) *Point

func (*Point) ToJSON 

func (p *Point) ToJSON() string

type SortablePointsCollection 

type SortablePointsCollection []*Point

func (SortablePointsCollection) Len 

func (c SortablePointsCollection) Len() int

func (SortablePointsCollection) Less 

func (c SortablePointsCollection) Less(i, j int) bool

func (SortablePointsCollection) Swap 

func (c SortablePointsCollection) Swap(i, j int)

type SweepContext 

type SweepContext struct {
	Triangles []*Triangle
	Map       []*Triangle
	Points    []*Point
	EdgeList  []*Edge
	PMin      *Point
	PMax      *Point
	Front     *AdvancingFront
	Head      *Point
	Tail      *Point
	AfHead    *Node
	AfMiddle  *Node
	AfTail    *Node
	Basin     *Basin
	EdgeEvent *EdgeEvent
}

func NewSweepContext 

func NewSweepContext(contour []*Point, cloneArrays bool) *SweepContext

func (*SweepContext) AddHole 

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

func (*SweepContext) AddHoles 

func (sc *SweepContext) AddHoles(holes [][]*Point) *SweepContext

func (*SweepContext) AddPoint 

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

func (*SweepContext) AddPoints 

func (sc *SweepContext) AddPoints(points []*Point) *SweepContext

func (*SweepContext) AddToMap 

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

func (*SweepContext) CreateAdvancingFront 

func (sc *SweepContext) CreateAdvancingFront()

func (*SweepContext) GetBoundingBox 

func (sc *SweepContext) GetBoundingBox() (min *Point, max *Point)

func (*SweepContext) GetFront 

func (sc *SweepContext) GetFront() *AdvancingFront

func (*SweepContext) GetHead 

func (sc *SweepContext) GetHead() *Point

func (*SweepContext) GetMap 

func (sc *SweepContext) GetMap() []*Triangle

func (*SweepContext) GetPoint 

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

func (*SweepContext) GetTail 

func (sc *SweepContext) GetTail() *Point

func (*SweepContext) GetTriangles 

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

func (*SweepContext) InitEdges 

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

func (*SweepContext) InitTriangulation 

func (sc *SweepContext) InitTriangulation()

func (*SweepContext) LocateNode 

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

func (*SweepContext) MapTriangleToNodes 

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

func (*SweepContext) MeshClean 

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

func (*SweepContext) PointCount 

func (sc *SweepContext) PointCount() int

func (*SweepContext) RemoveFromMap 

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

func (*SweepContext) RemoveNode 

func (sc *SweepContext) RemoveNode(node *Node)

func (*SweepContext) SetHead 

func (sc *SweepContext) SetHead(p1 *Point)

func (*SweepContext) SetTail 

func (sc *SweepContext) SetTail(p1 *Point)

func (*SweepContext) Triangulate 

func (sc *SweepContext) Triangulate() *SweepContext

type Triangle 

type Triangle struct {
	Points          []*Point
	Neighbors       []*Triangle
	Interior        bool
	ConstrainedEdge []bool
	DelaunayEdge    []bool
}

func NewTriangle 

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

func NextFlipTriangle 

func NextFlipTriangle(tcx *SweepContext, o int, t *Triangle, ot *Triangle, p *Point, op *Point) *Triangle

func (*Triangle) ClearDelaunayEdges 

func (t *Triangle) ClearDelaunayEdges()

func (*Triangle) ClearNeighbors 

func (t *Triangle) ClearNeighbors()

func (*Triangle) ContainsEdge 

func (t *Triangle) ContainsEdge(edge *Edge) bool

func (*Triangle) ContainsPoint 

func (t *Triangle) ContainsPoint(point *Point) bool

func (*Triangle) ContainsPoints 

func (t *Triangle) ContainsPoints(p1, p2 *Point) bool

func (*Triangle) EdgeIndex 

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

func (*Triangle) GetConstrainedEdgeAcross 

func (t *Triangle) GetConstrainedEdgeAcross(p *Point) bool

func (*Triangle) GetConstrainedEdgeCCW 

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

func (*Triangle) GetConstrainedEdgeCW 

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

func (*Triangle) GetDelaunayEdgeCCW 

func (t *Triangle) GetDelaunayEdgeCCW(p *Point) bool

func (*Triangle) GetDelaunayEdgeCW 

func (t *Triangle) GetDelaunayEdgeCW(p *Point) bool

func (*Triangle) GetNeighbor 

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

func (*Triangle) GetPoint 

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

func (*Triangle) GetPoints 

func (t *Triangle) GetPoints(index int) []*Point

func (*Triangle) Index 

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

func (*Triangle) IsInterior 

func (t *Triangle) IsInterior() bool

func (*Triangle) Legalize 

func (t *Triangle) Legalize(opoint *Point, npoint *Point)

func (*Triangle) MarkConstrainedEdgeByEdge 

func (t *Triangle) MarkConstrainedEdgeByEdge(edge *Edge)

func (*Triangle) MarkConstrainedEdgeByIndex 

func (t *Triangle) MarkConstrainedEdgeByIndex(index int)

func (*Triangle) MarkConstrainedEdgeByPoints 

func (t *Triangle) MarkConstrainedEdgeByPoints(p, q *Point)

func (*Triangle) MarkNeighbor 

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

func (*Triangle) MarkNeighborPointers 

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

func (*Triangle) NeighborAcross 

func (t *Triangle) NeighborAcross(p *Point) *Triangle

func (*Triangle) NeighborCCW 

func (t *Triangle) NeighborCCW(p *Point) *Triangle

func (*Triangle) NeighborCW 

func (t *Triangle) NeighborCW(p *Point) *Triangle

func (*Triangle) OppositePoint 

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

func (*Triangle) PointCCW 

func (t *Triangle) PointCCW(p *Point) *Point

func (*Triangle) PointCW 

func (t *Triangle) PointCW(p *Point) *Point

func (*Triangle) SetConstrainedEdgeCCW 

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

func (*Triangle) SetConstrainedEdgeCW 

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

func (*Triangle) SetDelaunayEdgeCCW 

func (t *Triangle) SetDelaunayEdgeCCW(p *Point, e bool)

func (*Triangle) SetDelaunayEdgeCW 

func (t *Triangle) SetDelaunayEdgeCW(p *Point, e bool)

func (*Triangle) SetInterior 

func (t *Triangle) SetInterior(interior bool) *Triangle

func (*Triangle) String 

func (t *Triangle) String() string

type XYInterface 

type XYInterface interface {
	String() string
	GetX() float64
	GetY() float64
}

Source Files

View all Source files

Directories

Path Synopsis
cmd
example

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.