internal

Documentation

Overview

The heap contains every point in the polygon Popping the heap will give you the point with the smallest angle/area a.k.a: the least significant point

helper package for determining if edges cross

Concrete implementation of VertexCollection for traversing "lines"

Concrete implementation of VertexCollection for traversing "loops"

Index

• func BuildRTreeRect(points ...s2.Point) (*rtreego.Rect, error)
• func CreatesIntersection(rtree *rtreego.Rtree, point *PointWithTriangle) []s2.Edge
• func EdgesCross(a, b s2.Edge) bool
• func PolylineSelfIntersects(polyline s2.Polyline) ([]s2.Edge, error)
• func TriangleArea(point *PointWithTriangle) float64
• func TriangleBbox(point *PointWithTriangle) (*rtreego.Rect, error)
• func Visvalingam(pointList VertexCollection, threshold float64, minPointsToKeep int, ...) (err error)
• type PointWithTriangle
  • func NewPointWithTriangle(point s2.Point) *PointWithTriangle
  • func (p PointWithTriangle) Bounds() *rtreego.Rect
  • func (p *PointWithTriangle) Next() *PointWithTriangle
  • func (p *PointWithTriangle) Prev() *PointWithTriangle
• type PointWithTriangleHeap
  • func (h PointWithTriangleHeap) Len() int
  • func (h PointWithTriangleHeap) Less(i, j int) bool
  • func (heap *PointWithTriangleHeap) Pop() (tailI interface{})
  • func (heap *PointWithTriangleHeap) Push(value interface{})
  • func (h PointWithTriangleHeap) Swap(i, j int)
• type PointWithTriangleList
  • func NewPointWithTriangleList() *PointWithTriangleList
  • func (l *PointWithTriangleList) Do(f func(*PointWithTriangle) error) error
  • func (l PointWithTriangleList) Len() int
  • func (l *PointWithTriangleList) Next(point *PointWithTriangle) *PointWithTriangle
  • func (l *PointWithTriangleList) Prev(point *PointWithTriangle) *PointWithTriangle
  • func (l *PointWithTriangleList) PushBack(e *PointWithTriangle)
  • func (l *PointWithTriangleList) Remove(e *PointWithTriangle)
• type PointWithTriangleRing
  • func NewPointWithTriangleRing(root *PointWithTriangle) *PointWithTriangleRing
  • func (r PointWithTriangleRing) Do(f func(*PointWithTriangle) error) error
  • func (r PointWithTriangleRing) Len() int
  • func (r PointWithTriangleRing) Next(point *PointWithTriangle) *PointWithTriangle
  • func (r PointWithTriangleRing) Prev(point *PointWithTriangle) *PointWithTriangle
  • func (r *PointWithTriangleRing) PushBack(e *PointWithTriangle)
  • func (r *PointWithTriangleRing) Remove(e *PointWithTriangle)
• type VertexCollection

Functions

func BuildRTreeRect

func BuildRTreeRect(points ...s2.Point) (*rtreego.Rect, error)

func CreatesIntersection

func CreatesIntersection(
	rtree *rtreego.Rtree,
	point *PointWithTriangle,
) []s2.Edge

returns the first intersection it finds when removing `point` given the triangle abc, see if the vector ac intersects with the remainder of the linked list

func EdgesCross

func EdgesCross(a, b s2.Edge) bool

Factored out because of repeated confusion around correct fn to use H.C: while `EdgeOrVertexCrossing` may look tantilizing do _not_ use it it will identify two lines that share a vertex as crossing

func PolylineSelfIntersects

func PolylineSelfIntersects(polyline s2.Polyline) ([]s2.Edge, error)

This method provided exclusively for testing uses a more straightforward but slower approach, helpful when debugging

using an rtree for efficient(ish) lookup identify if a polyline self intersects

"R-trees are balanced, so maximum tree height is guaranteed to be logarithmic in the number of entries; however, good worst-case performance is not guaranteed. Instead, a number of rebalancing heuristics are applied that perform well in practice."

https://en.wikipedia.org/wiki/R-tree

func TriangleArea

func TriangleArea(point *PointWithTriangle) float64

func TriangleBbox

func TriangleBbox(point *PointWithTriangle) (*rtreego.Rect, error)

func Visvalingam

func Visvalingam(
	pointList VertexCollection,
	threshold float64,
	minPointsToKeep int,
	avoidIntersections bool,
) (err error)

Types

type PointWithTriangle

type PointWithTriangle struct {
	Point s2.Point

	// The area this triangle occupies with
	// the triangle (point-1)(point)(point+1)
	Area      float64
	HeapIndex int
	// the bounding box of the triangle formed
	BBox *rtreego.Rect
	// contains filtered or unexported fields
}

func NewPointWithTriangle

func NewPointWithTriangle(point s2.Point) *PointWithTriangle

func (PointWithTriangle) Bounds

func (p PointWithTriangle) Bounds() *rtreego.Rect

func (*PointWithTriangle) Next

func (p *PointWithTriangle) Next() *PointWithTriangle

Defer to the list for next behaviour

func (*PointWithTriangle) Prev

func (p *PointWithTriangle) Prev() *PointWithTriangle

type PointWithTriangleHeap

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

func (PointWithTriangleHeap) Len

func (h PointWithTriangleHeap) Len() int

func (PointWithTriangleHeap) Less

func (h PointWithTriangleHeap) Less(i, j int) bool

Our heap is sorted by area

func (*PointWithTriangleHeap) Pop

func (heap *PointWithTriangleHeap) Pop() (tailI interface{})

func (*PointWithTriangleHeap) Push

func (heap *PointWithTriangleHeap) Push(value interface{})

func (PointWithTriangleHeap) Swap

func (h PointWithTriangleHeap) Swap(i, j int)

type PointWithTriangleList

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

func NewPointWithTriangleList

func NewPointWithTriangleList() *PointWithTriangleList

func (*PointWithTriangleList) Do

func (l *PointWithTriangleList) Do(f func(*PointWithTriangle) error) error

func (PointWithTriangleList) Len

func (l PointWithTriangleList) Len() int

func (*PointWithTriangleList) Next

func (l *PointWithTriangleList) Next(point *PointWithTriangle) *PointWithTriangle

func (*PointWithTriangleList) Prev

func (l *PointWithTriangleList) Prev(point *PointWithTriangle) *PointWithTriangle

func (*PointWithTriangleList) PushBack

func (l *PointWithTriangleList) PushBack(e *PointWithTriangle)

func (*PointWithTriangleList) Remove

func (l *PointWithTriangleList) Remove(e *PointWithTriangle)

type PointWithTriangleRing

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

func NewPointWithTriangleRing

func NewPointWithTriangleRing(root *PointWithTriangle) *PointWithTriangleRing

func (PointWithTriangleRing) Do

func (r PointWithTriangleRing) Do(f func(*PointWithTriangle) error) error

func (PointWithTriangleRing) Len

func (r PointWithTriangleRing) Len() int

func (PointWithTriangleRing) Next

func (r PointWithTriangleRing) Next(point *PointWithTriangle) *PointWithTriangle

func (PointWithTriangleRing) Prev

func (r PointWithTriangleRing) Prev(point *PointWithTriangle) *PointWithTriangle

func (*PointWithTriangleRing) PushBack

func (r *PointWithTriangleRing) PushBack(e *PointWithTriangle)

func (*PointWithTriangleRing) Remove

func (r *PointWithTriangleRing) Remove(e *PointWithTriangle)

type VertexCollection

type VertexCollection interface {
	Remove(*PointWithTriangle)
	Len() int
	Do(f func(*PointWithTriangle) error) error
	Prev(p *PointWithTriangle) *PointWithTriangle
	Next(p *PointWithTriangle) *PointWithTriangle
}

Interface for traversing our shape that we can implement in ring & non-ring ways please see pointlist.go and pointring.go for concrete implementations