advanced

package
v0.0.0-...-b0217b0 Latest Latest
Warning

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

 Go to latest Published: Jun 29, 2022 License: MIT Imports: 12 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	Down = iota
	Up
)
View Source 
const Epsilon = 1e-7

Variables

View Source 
var DefaultDirection = Direction{X: Left, Y: Down}

This is an arbitrary direction for when you don't really care (e.g. tests)

Functions

func Area 

func Area(s HasSignedArea) float64

func CircularIndex 

func CircularIndex(i, n int) int

Often we want to treat an array as a circular buffer. This gives the modular index given length n, but unlike the raw modulo operator, it only gives positive values

func Equal 

func Equal(a, b float64) bool

To compensate for imprecision in floats, equality is tolerance based. If we don't account for this, we'll end up shaving off absurdly thin triangles on nearly horizontal segments.

func GreaterThan 

func GreaterThan(a, b float64) bool

func HandleTriangulatePanicRecover 

func HandleTriangulatePanicRecover(r interface{}) error

func IsCCW 

func IsCCW(s HasSignedArea) bool

func IsCW 

func IsCW(s HasSignedArea) bool

func IterateGraph 

func IterateGraph(root *QueryNode) chan *QueryNode

func IterateTrapezoids 

func IterateTrapezoids(root *QueryNode) chan *Trapezoid

func LessThan 

func LessThan(a, b float64) bool

Types

type Direction 

type Direction struct {
	X XDirection
	Y YDirection
}

func (Direction) Opposite 

func (dir Direction) Opposite() Direction

type DirectionalPoint 

type DirectionalPoint struct {
	Point     *Point
	Direction Vector
}

A point with a unit vector describing a direction.

func DefaultDirectionalPoint 

func DefaultDirectionalPoint(x, y float64) DirectionalPoint

Another convenience function, same concept as PointingRight

type GraphIterator 

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

A graph iterator lets you loop over the nodes in a graph exactly once. Traversal order is not defined. Behavior is also undefined if you modify the graph during iteration.

func NewGraphIterator 

func NewGraphIterator(root *QueryNode) *GraphIterator

func (*GraphIterator) MakeChan 

func (iter *GraphIterator) MakeChan() chan *QueryNode

Create a channel using a go routine to iterate over the subgraph. This provides a nicer API for looping, and allows the graph juggling to happen in another thread when possible.

func (*GraphIterator) Next 

func (iter *GraphIterator) Next() *QueryNode

type HasSignedArea 

type HasSignedArea interface {
	// Enclosed area of the structure, positive if counterclockwise, negative if clockwise.
	SignedArea() float64
}

Several properties can be derived from any structure that can compute its signed area.

type Point 

type Point struct {
	X float64
	Y float64
}

func (*Point) Above 

func (p *Point) Above(otherPoint *Point) bool

func (*Point) Below 

func (p *Point) Below(otherPoint *Point) bool

A common convention in our geometry is that if two points have the same Y value, the one with the smallex X value is "lower". This simulates a slightly rotated coordinate system, allowing us to assume Y values are never equal.

func (*Point) PointingAt 

func (p *Point) PointingAt(other *Point) DirectionalPoint

Create a directional point pointing at another point

func (*Point) PointingRight 

func (p *Point) PointingRight() DirectionalPoint

Convenience function setting the convention for finding points when you don't care about the direction.

func (*Point) String 

func (p *Point) String() string

String functions

type PointSet 

type PointSet map[*Point]struct{}

func (PointSet) Add 

func (ps PointSet) Add(p *Point)

func (PointSet) Contains 

func (ps PointSet) Contains(p *Point) bool

func (PointSet) Equals 

func (ps PointSet) Equals(otherSet PointSet) bool

type PointStack 

type PointStack []*Point

func (*PointStack) Empty 

func (s *PointStack) Empty() bool

func (*PointStack) Peek 

func (s *PointStack) Peek() *Point

func (*PointStack) Pop 

func (s *PointStack) Pop() *Point

func (*PointStack) Push 

func (s *PointStack) Push(p *Point)

type Polygon 

type Polygon struct {
	Points []*Point
}

func (Polygon) ContainsPointByEvenOdd 

func (poly Polygon) ContainsPointByEvenOdd(p *Point) bool

Even/odd point-in-polygon. This is provided primarily for testing of the Seidel algorithm. If you are checking many points inside the same large polygon, it can be more effficient to trapezoidize it and use the resulting QueryGraph.

Note that this is winding direction agnostic, so it will give a different answer from the Seidel algorithm if you add counter-clockwise holes, or clockwise outer polygons.

func (Polygon) CrossingCount 

func (poly Polygon) CrossingCount(p *Point) int

Crossing count helper for even odd rule

func (Polygon) Reverse 

func (poly Polygon) Reverse() Polygon

func (*Polygon) SignedArea 

func (poly *Polygon) SignedArea() float64

type PolygonList 

type PolygonList []Polygon

A list of polygons which must not have crossing segments. For the purposes of Seidel triangulation, holes must run clockwise, and the outer polygons must run counter-clockwise.

func ConvertToMonotones 

func ConvertToMonotones(list PolygonList) PolygonList

Use a query graph to split a set of polygons into monotone polygons.

func (PolygonList) ContainsPointByEvenOdd 

func (l PolygonList) ContainsPointByEvenOdd(p *Point) bool

func (PolygonList) CrossingCount 

func (l PolygonList) CrossingCount(p *Point) int

func (PolygonList) Triangulate 

func (list PolygonList) Triangulate() TriangleList

type QueryGraph 

type QueryGraph struct {
	Root *QueryNode
}

func NewQueryGraph 

func NewQueryGraph(segment *Segment) *QueryGraph

Create a new graph from a single segment, and return the root node.

func (*QueryGraph) AddPolygon 

func (graph *QueryGraph) AddPolygon(poly Polygon, nondeterministic ...bool)

Add a polygon to the graph. If the polygon winds clockwise, this will end up producing a hole. Otherwise, it will be filled. The polygon must not intersect any existing segments in the graph.

By default, this process is pseudorandom, but deterministic. This is because predictable results are easier to debug. However, this raises the potential for adversarial inputs. If you are using untrusted input, you should pass "true" for proper randomization.

func (*QueryGraph) AddPolygons 

func (g *QueryGraph) AddPolygons(list PolygonList)

func (*QueryGraph) AddSegment 

func (graph *QueryGraph) AddSegment(segment *Segment)

func (*QueryGraph) ContainsPoint 

func (g *QueryGraph) ContainsPoint(point *Point) bool

Fast test for point-in-polygon using the trapezoid graph. Output is not defined for points exactly on the edge of the graph.

func (*QueryGraph) FindPoint 

func (graph *QueryGraph) FindPoint(dp DirectionalPoint) *QueryNode

func (*QueryGraph) IterateGraph 

func (g *QueryGraph) IterateGraph() chan *QueryNode

func (*QueryGraph) IterateTrapezoids 

func (g *QueryGraph) IterateTrapezoids() chan *Trapezoid

func (*QueryGraph) PrintAllTrapezoids 

func (graph *QueryGraph) PrintAllTrapezoids()

func (*QueryGraph) SplitTrapezoidHorizontally 

func (graph *QueryGraph) SplitTrapezoidHorizontally(node *QueryNode, point *Point)

Split a trapezoid horizontally, and replace its sink with a y node. node.Inner must be a sink

type QueryNode 

type QueryNode struct {
	Inner QueryNodeInner
}

func (*QueryNode) ChildNodes 

func (n *QueryNode) ChildNodes() []*QueryNode

func (*QueryNode) FindPoint 

func (n *QueryNode) FindPoint(dp DirectionalPoint) *QueryNode

type QueryNodeInner 

type QueryNodeInner interface {
	// Traverse the graph to find the sink whose trapezoid contains the point. The
	// direction argument is required to disambiguate when the point is an XNode
	// segment's endpoint.
	FindPoint(DirectionalPoint) *QueryNode

	// Child nodes is useful for iterating over a graph
	ChildNodes() []*QueryNode
	// contains filtered or unexported methods
}

Query nodes are polymorphic, and we need to be able to replace the content with a different node type in O(1) time. Therefore, we use this interface to provide a union between the different types of query node.

type Segment 

type Segment struct {
	Start *Point
	End   *Point
}

Note that all points involved with the triangulation are pointers. This means they can be used as keys. We should never modify a point value from the original polygon, since some applications require exact equality, and we cannot tolerate loss of precision.

func (*Segment) Bottom 

func (s *Segment) Bottom() *Point

func (*Segment) IsHorizontal 

func (s *Segment) IsHorizontal() bool

func (*Segment) IsLeftOf 

func (s *Segment) IsLeftOf(p *Point) bool

Is the line segment left of p. This assumes that P is vertically between the start and end of the segment

func (*Segment) IsRightOf 

func (s *Segment) IsRightOf(p *Point) bool

func (*Segment) IsVertical 

func (s *Segment) IsVertical() bool

func (*Segment) PointsDown 

func (s *Segment) PointsDown() bool

A segment points down if its start point is above its endpoint

func (*Segment) SolveForX 

func (s *Segment) SolveForX(y float64) float64

Solve the line (ignoring the bounds) for the given y value

func (*Segment) Top 

func (s *Segment) Top() *Point

func (*Segment) XDirection 

func (s *Segment) XDirection() XDirection

Determine which direction the segment points from top to bottom 

      o
    /   <- Left
  o

	o
	 \  <- Right
	  o

type SinkNode 

type SinkNode struct {
	Trapezoid *Trapezoid
	// Before a sink has been merged, it will always have a single parent, which
	// this points to. After a merge, we no longer need to know the parent, and
	// this will be nil.
	InitialParent *QueryNode
}

func (SinkNode) ChildNodes 

func (node SinkNode) ChildNodes() []*QueryNode

func (SinkNode) FindPoint 

func (node SinkNode) FindPoint(_ DirectionalPoint) *QueryNode

type Trapezoid 

type Trapezoid struct {
	Left, Right *Segment
	// The top and bottom are points, although geometrically, you can think of
	// them as the y values of those points. There are two reasons that points
	// must be used instead of y values:
	//
	// 1. A critical assumption of the algorithm is that no two points lie on the
	// same horizontal. This is simulated by lexicographic ordering, but it means
	// that _every_ Y comparison must have an X value involved to break ties.
	//
	// 2. The time will come when we ask every trapezoid "what points on your
	// boundary are vertices of the polygon"? Because of the unique Y value
	// assumption, the answer is _always_ two points. Those two points are the top
	// and bottom fields. Note that in some cases, these will be an endpoint of a
	// segment, and in some cases, they'll lie on the top or bottom of the
	// trapezoid, away from the left and right sides.
	Top, Bottom                      *Point
	TrapezoidsAbove, TrapezoidsBelow TrapezoidNeighborList
	Sink                             *QueryNode
}

func (*Trapezoid) BottomIntersectsSegment 

func (t *Trapezoid) BottomIntersectsSegment(segment *Segment) bool

Check if a segment crosses the bottom edge of the trapezoid.

func (*Trapezoid) CanMergeWith 

func (t *Trapezoid) CanMergeWith(other *Trapezoid) bool

func (*Trapezoid) DbgName 

func (t *Trapezoid) DbgName() string

func (*Trapezoid) HasPoint 

func (t *Trapezoid) HasPoint(p *Point) bool

Check if the point is any of the (up to) six points involved with the trapezoid. If it is, then it's already a line segment in the graph.

func (*Trapezoid) IsDegenerateOnSide 

func (t *Trapezoid) IsDegenerateOnSide(side YDirection) bool

Check if the trapezoid has a degenerate side (is it a triangle). If either side is nil, then it's never degenerate. Otherwise, this holds when the corresponding segment endpoints are equal IFF the corresponding side of the trapezoid is that segment's start or end.

func (*Trapezoid) IsInside 

func (t *Trapezoid) IsInside() bool

Is the trapezoid inside the polygon?

func (*Trapezoid) NonzeroOverlapWithTrapezoidAbove 

func (bottomTrapezoid *Trapezoid) NonzeroOverlapWithTrapezoidAbove(topTrapezoid *Trapezoid) bool

This is what decides if two trapezoids are neighbors.

func (*Trapezoid) SegmentForSide 

func (t *Trapezoid) SegmentForSide(side XDirection) *Segment

func (*Trapezoid) SplitBySegment 

func (t *Trapezoid) SplitBySegment(segment *Segment) (left, right *Trapezoid)

Split a trapezoid vertically with a segment, returning the two trapezoids. It is assumed that the segment fully passes through the trapezoid. The resulting left and right trapezoids will not yet be in the query graph, and they will still point to the original trapezoid's sink. This must be fixed after trapezoids with agreeing edges are merged.

func (*Trapezoid) String 

func (t *Trapezoid) String() string

type TrapezoidNeighborList 

type TrapezoidNeighborList [3]*Trapezoid

Trapezoids can have up to two neighbors above and below them in the stable state, but while splitting, they can have up to three below. This should never be the case after splitting is complete.

func (*TrapezoidNeighborList) Add 

func (tl *TrapezoidNeighborList) Add(t *Trapezoid)

Append a trapezoid to the list, if it isn't already there

func (*TrapezoidNeighborList) AnyNeighbor 

func (tl *TrapezoidNeighborList) AnyNeighbor() *Trapezoid

func (*TrapezoidNeighborList) Remove 

func (tl *TrapezoidNeighborList) Remove(t *Trapezoid)

func (*TrapezoidNeighborList) ReplaceOrAdd 

func (tl *TrapezoidNeighborList) ReplaceOrAdd(orig *Trapezoid, replacement *Trapezoid)

Replace a trapezoid with another, or append it if the original isn't there

func (*TrapezoidNeighborList) String 

func (tl *TrapezoidNeighborList) String() string

type TrapezoidSet 

type TrapezoidSet map[*Trapezoid]struct{}

type Triangle 

type Triangle struct {
	A, B, C *Point
}

func TriangulateMonotone 

func TriangulateMonotone(polygon *Polygon) []*Triangle

func (*Triangle) SignedArea 

func (t *Triangle) SignedArea() float64

type TriangleList 

type TriangleList []*Triangle

func (TriangleList) ToPolygonList 

func (triangles TriangleList) ToPolygonList() PolygonList

Helper mostly used in tests. Converts the triangles into generic polygons.

type TriangulateError 

type TriangulateError error

type Vector 

type Vector Point

func (Vector) Length 

func (v Vector) Length() float64

func (Vector) Normalize 

func (v Vector) Normalize() Vector

type XDirection 

type XDirection int
const (
	Left XDirection = iota
	Right
)

func (XDirection) Opposite 

func (dir XDirection) Opposite() XDirection

type XNode 

type XNode struct {
	Left, Right *QueryNode
	Key         *Segment
}

An X node

func (XNode) ChildNodes 

func (node XNode) ChildNodes() []*QueryNode

func (XNode) FindPoint 

func (node XNode) FindPoint(dp DirectionalPoint) *QueryNode

type YDirection 

type YDirection int

func (YDirection) Opposite 

func (dir YDirection) Opposite() YDirection

type YNode 

type YNode struct {
	Above, Below *QueryNode
	Key          *Point // Point so that we can do the lexicographic thing
}

A Y Node is a node which lets us navigate up or down

func (YNode) ChildNodes 

func (node YNode) ChildNodes() []*QueryNode

func (YNode) FindPoint 

func (node YNode) FindPoint(dp DirectionalPoint) *QueryNode

Source Files

View all Source files

Directories

Path Synopsis

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.