polygon

package
v0.0.0-...-9c88ebf Latest Latest
Warning

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

 Go to latest Published: Aug 31, 2022 License: BSD-3-Clause Imports: 11 Imported by: 2

Documentation

Index

Constants

View Source 
const (
	// Tau constant
	Tau = math.Pi * 2
	// Pi constant
	Pi = math.Pi
)

Variables

View Source 
var GrahamTolerance = cmpr.Tolerance(1e-7)

GrahamTolerance is the deviation from 0 of a cross product that will still be treated as 0.

Functions

func ConvexHull 

func ConvexHull(pts ...d2.Pt) []d2.Pt

ConvexHull is currently a wrapper around GrahamScan. A more efficient algorithm may be added later.

func GetTriangles 

func GetTriangles(triangles [][3]uint32, p Polygon) []*triangle.Triangle

GetTriangles takes triangle indexes from FindTriangles and returns a slice of triangles. This can be used to map one polygon to another with the same number of sides.

func GrahamScan 

func GrahamScan(pts ...d2.Pt) []d2.Pt

GrahamScan: https://en.wikipedia.org/wiki/Graham_scan Finds the convex hull of a set of points in O(n log n).

Types

type AssertConvexHull 

type AssertConvexHull []d2.Pt

AssertConvexHull fulfills geomtest.AssertEqualizer. It is a list of points. Given a convex hull, it checks that the hull is convex and contains all the points in it's list.

func (AssertConvexHull) AssertEqual 

func (a AssertConvexHull) AssertEqual(actual interface{}, t cmpr.Tolerance) error

AssertEqual fulfills geomtest.AssertEqualizer. It checks that actual is a slice of points that form a convex hull containing all the points in AssertConvexHull.

type AssertConvexHuller 

type AssertConvexHuller []d2.Pt

AssertConvexHuller fulfills geomtest.AssertEqualizer. It is a list of points. Given an interface that fulfills ConvexHuller, it checks that the hull is convex and contains all the points in it's list.

func (AssertConvexHuller) AssertEqual 

func (a AssertConvexHuller) AssertEqual(actual interface{}, t cmpr.Tolerance) error

AssertEqual fulfills geomtest.AssertEqualizer. It check that actual is an an instance of ConvexHuller and the ConvexHull returned is convex and contains all the points in AssertConvexHuller.

type Collision 

type Collision struct {
	PIdx, P2Idx int
	PT, P2T     float64
}

Collision between two polygons

func (Collision) P 

func (c Collision) P(p Polygon) d2.Pt

P returns the collision point using polygon P to compute.

func (Collision) P2 

func (c Collision) P2(p2 Polygon) d2.Pt

P2 returns the collision point using polygon P2 to compute.

type Collisions 

type Collisions []Collision

Collisions represent a set of collisions between two polygons.

func (Collisions) P 

func (cs Collisions) P(p Polygon) []d2.Pt

P returns the collision points using polygon P to compute.

func (Collisions) P2 

func (cs Collisions) P2(p2 Polygon) []d2.Pt

P2 returns the collision points using polygon P2 to compute.

type ConcavePolygon 

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

ConcavePolygon represents a Polygon with at least one concave angle.

func NewConcavePolygon 

func NewConcavePolygon(concave Polygon) ConcavePolygon

NewConcavePolygon converts a Polygon to a ConcavePolygon

func (ConcavePolygon) Area 

func (c ConcavePolygon) Area() float64

Area of the polygon

func (ConcavePolygon) Centroid 

func (c ConcavePolygon) Centroid() d2.Pt

Centroid returns the center of mass of the polygon

func (ConcavePolygon) Contains 

func (c ConcavePolygon) Contains(f d2.Pt) bool

Contains returns true of the point f is inside of the polygon

func (ConcavePolygon) Perimeter 

func (c ConcavePolygon) Perimeter() float64

Perimeter returns the total length of the perimeter

func (ConcavePolygon) Pt1 

func (c ConcavePolygon) Pt1(t0 float64) d2.Pt

Pt1 returns a point on the perimeter

func (ConcavePolygon) Pt2 

func (c ConcavePolygon) Pt2(t0, t1 float64) d2.Pt

Pt2 returns a point in the ConcavePolygon adhereing to the shape rules

func (ConcavePolygon) SignedArea 

func (c ConcavePolygon) SignedArea() float64

SignedArea returns the Area and may be negative depending on the polarity.

type ConvexHuller 

type ConvexHuller interface {
	ConvexHull() []d2.Pt
}

ConvexHuller is taken from shape.ConvexHuller to avoid cyclic imports.

type ErrNotConvex 

type ErrNotConvex struct{}

ErrNotConvex is return if a convex hull is not actually convex.

func (ErrNotConvex) Error 

func (ErrNotConvex) Error() string

Error fulfills error and returns the string "hull is not convex"

type LLNode 

type LLNode struct {
	PIdx, NextIdx uint32
}

LLNode is a node in a linked list polygon

type LLPolygon 

type LLPolygon struct {
	Pts   []d2.Pt
	Nodes []LLNode
	Start uint32
}

LLPolygon represents a polygon as a linked list stored in a slice. Start can be any index that is in the list. The list should be circular. This is useful when adding and removing vertexes in an algorithm.

func NewLL 

func NewLL(p Polygon) *LLPolygon

NewLL creates a linked list polygon from a regular polygon

func (*LLPolygon) Contains 

func (p *LLPolygon) Contains(pt d2.Pt) bool

Contains checks if a point in inside a linked list polygon

func (*LLPolygon) ConvexHull 

func (p *LLPolygon) ConvexHull() []d2.Pt

ConvexHull fulfills shape.ConvexHuller. Returns the convex hull of the polygon using the ConvexHull function.

func (*LLPolygon) DoesIntersect 

func (p *LLPolygon) DoesIntersect(ln line.Line) bool

DoesIntersect returns true if the line intersects any side with a parametric value between 0 and 1.

type PolarPolygon 

type PolarPolygon []d2.Polar

PolarPolygon is useful in constructing a Polygon when the order of the vertexes is not known. It does not fulfill shape.

func NewPolar 

func NewPolar(pts []d2.Pt) (polarPolygon PolarPolygon, center d2.Pt)

Create a new PolarPolygon from a set of points. The result will be translated so the center is (0,0) and the previous center returned.

func (PolarPolygon) Len 

func (p PolarPolygon) Len() int

Len returns the number of points, fulfills sort.Interface

func (PolarPolygon) Less 

func (p PolarPolygon) Less(i, j int) bool

Less fulfills sort.Interface

func (PolarPolygon) Polygon 

func (p PolarPolygon) Polygon(center d2.Pt) Polygon

Polygon converts the PolarPolygon to a Polygon

func (PolarPolygon) Sort 

func (p PolarPolygon) Sort()

Sort the PolarPolygon by angle

func (PolarPolygon) Swap 

func (p PolarPolygon) Swap(i, j int)

Swap fulfills sort.Interface

type Polygon 

type Polygon []d2.Pt

Polygon represents a Convex Polygon

func New 

func New(pts []d2.Pt) Polygon

New creates a polygon and orders the points to proceed counter clockwise.

func RectanglePointWidthLength 

func RectanglePointWidthLength(pt d2.Pt, v d2.V) Polygon

RectanglePointWidthLength takes a point and a vector and returns a rectangle

func RectangleTwoPoints 

func RectangleTwoPoints(p1, p2 d2.Pt) Polygon

RectangleTwoPoints takes two points and returns a Polygon representing a rectangle.

func RegularPolygonRadius 

func RegularPolygonRadius(center d2.Pt, radius float64, a angle.Rad, sides int) Polygon

RegularPolygonRadius constructs a regular polygon. The radius is measured from the center of each side.

func RegularPolygonSideLength 

func RegularPolygonSideLength(center d2.Pt, sideLength float64, a angle.Rad, sides int) Polygon

RegularPolygonSideLength constructs a regular polygon defined by the length of the sides.

func (Polygon) Area 

func (p Polygon) Area() float64

Area of the polygon

func (Polygon) BoundingBox 

func (p Polygon) BoundingBox() (min, max d2.Pt)

BoundingBox fulfills BoundingBoxer returning a box that contains the polygon.

func (Polygon) Centroid 

func (p Polygon) Centroid() d2.Pt

Centroid returns the center of mass of the polygon

func (Polygon) Collision 

func (p Polygon) Collision(lineSegment line.Line) (lineT float64, idx int, sideT float64)

Collision returns the first side that is intersected by the given lineSegment, returning the parametic t for the lineSegment, the index of the side and the parametric t of the side

func (Polygon) Contains 

func (p Polygon) Contains(pt d2.Pt) bool

Contains returns true of the point f is inside of the polygon. This is done with the winding number algorithm and runs in O(n).

func (Polygon) Convex 

func (p Polygon) Convex() bool

Convex returns True if the polygon contains a convex angle.

func (Polygon) ConvexHull 

func (p Polygon) ConvexHull() []d2.Pt

ConvexHull fulfills shape.ConvexHuller. Returns the convex hull of the polygon using the ConvexHull function.

func (Polygon) CountAngles 

func (p Polygon) CountAngles(out []int) (ccw int, cw int)

CountAngles returns the number of counter clockwise and clockwise angles. If ccwOut or cwOut is not nil, they will be populated with the indexes of the verticies

func (Polygon) FindTriangles 

func (p Polygon) FindTriangles() [][3]uint32

FindTriangles returns the index sets of the polygon broken up into triangles. Given a unit square it would return [[0,1,2], [0,2,3]] which means that the square can be broken up in to 2 triangles formed by the points at those indexes.

func (Polygon) LineIntersections 

func (p Polygon) LineIntersections(ln line.Line, buf []float64) []float64

LineIntersections fulfills line.LineIntersector

func (Polygon) NonIntersecting 

func (p Polygon) NonIntersecting() bool

NonIntersecting returns false if any two sides intersect. This requires O(N^2) time to check.

func (Polygon) Perimeter 

func (p Polygon) Perimeter() float64

Perimeter returngs the total length of the perimeter

func (Polygon) PolygonCollisions 

func (p Polygon) PolygonCollisions(p2 Polygon) Collisions

PolygonIntersections finds the intersection points between two polygons.

func (Polygon) Pt1 

func (p Polygon) Pt1(t0 float64) d2.Pt

Pt1 returns a point on the perimeter.

func (Polygon) Pt2 

func (p Polygon) Pt2(t0, t1 float64) d2.Pt

Pt2 returns a point in the polygon and adheres to the Shape rules.

func (Polygon) Pt2c1 

func (p Polygon) Pt2c1(t0 float64) d2.Pt1

Pt2c1 returns line.Segments as d2.Pt1 that adheres to the Shape rules

func (Polygon) Reverse 

func (p Polygon) Reverse() Polygon

Reverse the order of the points defining the polygon

func (Polygon) Side 

func (p Polygon) Side(n int) line.Line

Side n of the polygon where the side is formed by p[n] to p[n+1].

func (Polygon) Sides 

func (p Polygon) Sides() []line.Line

Sides converts the perimeter of the polygon to a slice of lines.

func (Polygon) SignedArea 

func (p Polygon) SignedArea() float64

SignedArea returns the Area and may be negative depending on the polarity.

func (Polygon) String 

func (p Polygon) String() string

String lists the points as a string.

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.