nape.geom.GeomPoly - HaxeFlixel API

Polygon class with various geometric methods

This class represents a general Polygon, rather than the Polygon class which is physics shape.

Internally this polygon is stored as a circularly linked list of special vertex types that are exposed via a Vec2 that is lazily constructed whenever necessary to the API.

Static methods

`@:has_untyped@:value({ vertices : null })staticget(?vertices:Dynamic):GeomPoly`

Allocate GeomPoly from object pool.

The vertices argument is typed Dynamic (* in AS3), and is permitted to be one of: Array<Vec2>, flash.Vector<Vec2>, Vec2List, GeomPoly

The input will be used to initialise the vertices of the polygon with the head of the polygon pointing to the first vertex in input with vertices inserted in forward order.

Parameters:

`vertices`	Vertex data to initialise polygon, or null for empty polygon.

Returns:

New GeomPoly representing input vertex data, allocated from object pool.

Throws:

`#`	If input data is not of an expected Type.

Constructor

`@:has_untyped@:value({ vertices : null })new(?vertices:Dynamic)`

Create a new GeomPoly polygon.

The vertices argument is typed Dynamic (* in AS3), and is permitted to be one of: Array<Vec2>, flash.Vector<Vec2>, Vec2List, GeomPoly

The input will be used to initialise the vertices of the polygon with the head of the polygon pointing to the first vertex in input with vertices inserted in forward order.

You should use the static 'get' method in preference to make use of object pool.

Parameters:

`vertices`	Vertex data to initialise polygon, or null for empty polygon.

Returns:

New GeomPoly representing input vertex data.

Throws:

`#`	If input data is not of an expected Type.

Variables

`zpp_disp:Bool`

@private

`@:value(null)zpp_inner:ZPP_GeomPoly = null`

@private

`@:value(null)zpp_pool:GeomPoly = null`

Throws:

`#`	If this GeomPoly has been disposed.

`contains(point:Vec2):Bool`

Determine if point is contained in polygon.

Polygon containment is performed with a ray cast through polygon from the vertex and counting the number of intersections. In this way containment will be defined for self-intersecting polygons based on how such a polygon would be rendered with areas of self-intersection treat as being 'outside' the polygon.

This algorithm operates in O(n) time.

Parameters:

`point`	The point to test for containment.

Returns:

True if point is contained in the polygon.

Throws:

`#`	If point is null or has been disposed.
`#`	If this GeomPoly has been disposed.

`@:value({ output : null, delaunay : false })convexDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList`

Produce a decomposition of weakly-simple polygon into convex components.

This algorithm 'should' be 100% robust and has been well test on for example, the output of the Marching Squars utility which produces many degenerate cases of weakly-simple polygons that have not yet broken this algorithm!.

This algorithm operates in O(n.log(n)) time and will produce no more than 4 times the number of convex poylgons in a minimal decomposition in the worst case scenario.

Vertices may be stripped from the polygon that are found to not be necessary as part of making this algorithm robust.

Parameters:

`delaunay`	This algorithm first performs a triangulation, if this field is true, then this triangulation will be made delaunay and may produce better convex polygons resultanly (default false).
`output`	If supplied, polygons will be appended to this list via 'add' instead of a new list being constructed.

Returns:

A Nape list of GeomPoly's defining the decomposition.

Throws:

`#`	If polygon is degenerate.
`#`	If this GeomPoly has been disposed.

`copy():GeomPoly`

Copy this polygon.

The copy will have its vertices in the same order as 'this' polygon. It will also have its current vertex at head, as the same vertex this polygon has.

This polygon will not be modified in any way.

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly2 = poly.copy();
poly2 := -> A' <-> B' <-> C' <-> D' <-> E' <-
             (head)

Returns:

The new GeomPoly representing the copy.

Throws:

`#`	If this GeomPoly has been disposed.

`inlinecurrent():Vec2`

Current vertex at head of polygon.

The current vertex will not be changed by this access.

This function returns a Vec2 which will be intrinsically tied to the values of the internal vertex so that modifications to this Vec2 will be reflected in the vertex of the polygon.

If invoked again with the head of the polygon pointing to the same vertex, then the same Vec2 will be returned; this Vec2 is not able to be disposed of.

Returns:

A Vec2 representing the current vertex of polygon.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`@:value({ output : null, boundedEnd : false, boundedStart : false })cut(start:Vec2, end:Vec2, boundedStart:Bool = false, boundedEnd:Bool = false, ?output:GeomPolyList):GeomPolyList`

Cut simple polygon with line.

The result of this operation will be a list of new GeomPoly representing the connected regions of the polygon after an imaginary cut is made.

(Result of cut assuming
boundedStart = true)       
/\    _             /\   / \
/  \  / \           /  \ '---'
/ o--\/---\-->  =>  /    \,---,
\/         \_/

This algorithm runs in average case O(n.log(n)) time and worst case O(n^2). For convex polygons, this algorithm runs in guaranteed O(n) time.

Parameters:

`start`	The start point for line segment
`end`	The end point for line segment.
`boundedStart`	If true, then the cut will not extend beyond the start of the line segment. (default false)
`boundedEnd`	If true, then the cut will not extend beyond the end of the line segment. (default false)
`output`	A GeomPolyList to append results to if supplied, otherwise a new list is created (default null)

Returns:

A list of GeomPoly representing the result of the cut.

Throws:

`#`	If polygon is not simple.
`#`	If start or end Vec2 are null or disposed of.
`#`	If this GeomPoly has been disposed.

`dispose():Void`

Release this GeomPoly to global object pool.

Once disposed this GeomPoly will be accessible to Nape internals for re-allocation and should not be touched (Good practice would be to set any references to this GeomPoly to null to help ensure this).

In debug mode, should you attempt to access this GeomPoly after disposal and the GeomPoly is still in the object pool, you will be given an Error. The object pool operates on a First-In-Last-Out principal in debug mode to help catch these sort of errors.

Throws:

`#`	If this GeomPoly has already been disposed.

`inlineempty():Bool`

Determine if polygon is empty.

Returns:

True if polygon is empty.

Throws:

`#`	If this GeomPoly has been disposed.

`erase(count:Int):GeomPoly`

Erase count number of elements

For positive values of count, this is equivalent to successive unshift operations.

For negative values of count, this is equivalent to successive pop operations.

poly := -> A <-> B <-> C <-> D <-> E <-> F <-> G <-
           (head)

poly.erase(2);
poly := -> A <-> D <-> E <-> F <-> G <-
           (head)

poly.erase(-3);
poly := -> E <-> F <-
           (head)

In this case that the specified number of elements to erase is greater than the size of the polygon, the method will simply terminate with the polygon being empty.

Parameters:

`count`	The number of vertices to erase, with sign indicating the direction for erasing.

Returns:

A reference to this polygon.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineforwardIterator():GeomVertexIterator`

Haxe iterator over vertices of polygon.

Returns:

A Haxe iterator over the vertices of the polygon. Iterating in a forward direction.

Throws:

`#`	If this GeomPoly has been disposed.

`inflate(inflation:Float):GeomPoly`

Inflate/Deflate polygon.

This algorithm does not attempt to deal with any self-intersections which may result from the process. Gaps are joined with a miter joint.

This algorithm will work for self-intersecting polygons, though the results may not be what you expect; some parts will be inflated, and some deflated depending on the local winding. You should probably avoid using this on self-intersecting polygons.

Parameters:

`inflation`	The number of pixels to inflate polygon by. To deflate use a negative value.

Returns:

The inflated polygon.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineisClockwise():Bool`

Determine if polygon is clockwise wound.

This is equivalent to poly.winding() == Winding.CLOCKWISE.

Returns:

True if polygon is clockwise wound.

Throws:

`#`	If this GeomPoly has been disposed.

`isConvex():Bool`

Determine if weakly-simple polygon is convex.

This algorithm assumes that the polygon is weakly-simple. Otherwise it may fail (It is very easy to construct a self intersecting polygon which will return True for isConvex()).

You may wish to instead use isSimple() && isConvex() if you cannot be sure of the polygon being simple, noting that this will of course return false in the case of a weakly-simple polygon.



|     |
|     |  <-- convex
|/

|  \_
|     /  <-- concave
|/

This algorithm operates in O(n) time.

Returns:

True if polygon is found to be convex.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineisDegenerate():Bool`

Determine if weakly-simple polygon is degenerate.

Degeneracy is determined by having a zero area, if polygon is complex, then this function may report degeneracy erroneously.

Returns:

True if polygon is degenerate.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineisMonotone():Bool`

Determine if polygon is y-monotone.

To be classed as y-monotone, the polygon must be such that any horizontal line intersects the polygon in at most 2 intersections.



|   |
|   |  <-- y-monotone
|___|
|\
| \/|  <-- not y-monotone, offending vertex at bottom of the V.
|___|

This algorithm operates in O(n) time.

Returns:

True if polygon is y-monotone.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineisSimple():Bool`

Determine if polygon is strictly simple.

By strict simplicity, we refer to not permitting 'glancing' self intersections (where boundary of polygon 'touches' but does not pass through another area of the polygon's boundary). This property is instead referred to as being 'weakly simple' for which there is no easy test!


__ <-- strictly simple polygon.

|   \ \_|
\__/

\_/

| /
X_     <-- complex polygon.
|  \/  \
\/\|

This algorithm operates in O(n.log(n)) time.

Returns:

True if polygon is strictly simple.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineiterator():GeomVertexIterator`

Haxe iterator over vertices of polygon.

Returns:

A Haxe iterator over the vertices of the polygon.

Throws:

`#`	If this GeomPoly has been disposed.

`left():Vec2`

Find left most vertex of polygon.

If there is more than one such vertex then the result is indeterminate.

The Vec2 returned is intrinsically tied to the inner vertex like that returned by current(). This method will not alter the current vertex. This Vec2 is not able to be disposed of.

Returns:

A Vec2 representing the left most vertex.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`@:value({ output : null })monotoneDecomposition(?output:GeomPolyList):GeomPolyList`

Produce a decomposition of weakly-simple polygon into monotone components.

This algorithm 'should' be 100% robust and has been well tested on for example, the output of the Marching Squares utility which produces many degenerate cases of weakly-simple polygons that have not yet broken this algorithm!.

This algorithm operates in O(n.log(n)) time and may strip vertices from the polygon in degenerate cases where vertex is not needed to define the polygon.

This algorithm is an improved version of the one presented in: Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.

Parameters:

`output`	If supplied, polygons will be appended to this list via 'add' instead of a new list being constructed.

Returns:

A Nape list of GeomPoly's defining the decomposition.

Throws:

`#`	If polygon is degenerate.
`#`	If this GeomPoly has been disposed.

`pop():GeomPoly`

Pop vertex from polygon.

Pop the current vertex at head of polygon, retreating the 'current' vertex to point to the previous vertex in polygon. This inner vertex will be released to the global object pool.

In this way a pop which follows a push will act to reset the push.

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.pop();
poly := -> A <-> C <-> D <-> E <-
     (head)

Returns:

A reference to this polygon.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`push(vertex:Vec2):GeomPoly`

Push vertex to polygon.

A vertex will be allocated from a global object pool, and initialised with the values of the given Vec2.

This vertex will be inserted after the current head, and the head advanced to the newly inserted vertex, in this way successive pushes will insert elements in order.

Note that the Vec2 supplied as argument is only used to initialise the inner Vertex.

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.push(X);
poly := -> A <-> B <-> X <-> C <-> D <-> E <-
                 (head)

Parameters:

`vertex`	The Vec2 to be used in initialising the inner vertex.

Returns:

A reference to this polygon.

Throws:

`#`	If Vec2 is null, or has been disposed.
`#`	If this GeomPoly has been disposed.

`right():Vec2`

Find right most vertex of polygon.

If there is more than one such vertex then the result is indeterminate.

The Vec2 returned is intrinsically tied to the inner vertex like that returned by current(). This method will not alter the current vertex. This Vec2 is not able to be disposed of.

Returns:

A Vec2 representing the right most vertex.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`shift():GeomPoly`

Shift vertex from polygon.

Shift the current vertex at head of polygon, advancing the 'current' vertex to point to the next vertex in polygon. This inner vertex will be released to the global object pool.

In this way a shift which follows an unshift will act to reset the unshift operation.

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.shift();
poly := -> A <-> C <-> D <-> E <-
           (head)

Returns:

A reference to this polygon.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`@:value({ output : null })simpleDecomposition(?output:GeomPolyList):GeomPolyList`

Produce a decomposition of complex polygon into simple components.

WARNING: This method is 'not' 100% robust. It may fail!

Produce a decomposition of a self intersecting, complex polygon into a set of weakly-simple components.

This algorithm operates in O(n.log(n)) time and is based on the Bentley-Ottmann algorithm.

Parameters:

`output`	If supplied, polygons will be appended to this list via 'add' instead of a new list being constructed.

Returns:

A Nape list of GeomPoly's representing the decomposition.

Throws:

`#`	If polygon is degenerate.
`#`	Any other error may be thrown if algorithm has failed, even in release builds!
`#`	If this GeomPoly has been disposed.

`simplify(epsilon:Float):GeomPoly`

Simplify polygon.

Simplification is performed with an implementation of the Ramer-Douglas-Peucker algorithm. The output polygon is formed via subset of the vertices in the input polygon such that any discarded vertex is at most 'epsilon' pixels away from the local output polygon.

This algorithm works on both simple and complex polygons, but please note that this algorithm makes no guarantees on a simple polygon remaining simple after simplification. This should not generally be a problem unless the epsilon value is large with respect to the size of the features on the polygon.

Many of the geometric algorithms will mark vertices as important, such that they will be guaranteed to exist after simplification (Such as preventing gaps from opening up in marching squares when simplifying output polygons).

The average runtime of this algorithm is O(n.log(n)). This algorithm is not stable in the sense that adding a new vertex to the polygon may drastically change the result of simplifying the polygon.

Parameters:

`epsilon`	The distance from polygon at which vertices are ignored.

Returns:

A new GeomPoly representing the result of the simplification.

Throws:

`#`	If epsilon is <= 0.
`#`	If this GeomPoly has been disposed.

`size():Int`

Determine number of vertices in polygon

Returns:

The number of vertices.

Throws:

`#`	If this GeomPoly has been disposed.

`inlineskipBackwards(times:Int):GeomPoly`

Advance head of polygon backwards.

The current head of polygon will be moved backwards the given number of times, with a negative value being equivalent to performing a forwards advance.

poly.skip_backwards(times) is equivalent to poly.skip_forwards(-times)

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.skipBackwards(2);
poly := -> A <-> B <-> C <-> D <-> E <-
                             (head)

@params times The number of times to advance head backwards.

          This value can be negative indicating a forwards
          advance.

Returns:

A reference to this polygon.

Throws:

`#`	If this GeomPoly has been disposed.

`skipForward(times:Int):GeomPoly`

Advance head of polygon forward.

The current head of polygon will be moved forwards the given number of times, with a negative value being equivalent to performing a backwards advance.

poly.skip_forwards(times) is equivalent to poly.skip_backwards(-times)

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.skipForwards(2);
poly := -> A <-> B <-> C <-> D <-> E <-
                       (head)

@params times The number of times to advance head forward.

          This value can be negative indicating a backwards
          advance.

Returns:

A reference to this polygon.

Throws:

`#`	If this GeomPoly has been disposed.

`@:keeptoString():String`

@private

`top():Vec2`

Find top most vertex of polygon.

If there is more than one such vertex then the result is indeterminate.

The Vec2 returned is intrinsically tied to the inner vertex like that returned by current(). This method will not alter the current vertex. This Vec2 is not able to be disposed of.

Returns:

A Vec2 representing the top most vertex.

Throws:

`#`	If polygon is empty.
`#`	If this GeomPoly has been disposed.

`transform(matrix:Mat23):GeomPoly`

Transform polygon by given matrix.

Any transformation (not just equiorthogonal ones) are permitted, though a transformation that causes polygon to be come degenerate is a bit pointless.

Parameters:

`matrix`	The matrix to transform polygon by.

Returns:

A reference to this polygon.

Throws:

`#`	If matrix is null.
`#`	If this GeomPoly has been disposed.

`@:value({ output : null, delaunay : false })triangularDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList`

Produce a decomposition of weakly-simple polygon into triangles.

This algorithm 'should' be 100% robust and has been well test on for example, the output of the Marching Squars utility which produces many degenerate cases of weakly-simple polygons that have not yet broken this algorithm!.

This algorithm operates in O(n.log(n)) time.

Vertices may be stripped from the polygon that are found to not be necessary as part of making this algorithm robust.

Parameters:

`delaunay`	If true, then an O(n^2) pass will be made to mutate the original triangulation to push it into a delanuay triangulation. (default false)
`output`	If supplied, polygons will be appended to this list via 'add' instead of a new list being constructed.

Returns:

A Nape list of GeomPoly's defining the decomposition.

Throws:

`#`	If polygon is degenerate.
`#`	If this GeomPoly has been disposed.

`unshift(vertex:Vec2):GeomPoly`

Unshift vertex to polygon.

A vertex will be allocated from a global object pool, and initialised with the values of the given Vec2.

This vertex will be inserted before the current head, and the head retreated to the newly inserted vertex, in this way successive unshifts will insert elements in the expected reverse order.

Note that the Vec2 supplied as argument is only used to initialise the inner Vertex.

poly := -> A <-> B <-> C <-> D <-> E <-
           (head)

poly.unshift(X);
poly := -> A <-> X <-> B <-> C <-> D <-> E <-
           (head)

Parameters:

`vertex`	The Vec2 to be used in initialising the inner vertex.

Returns:

A reference to this polygon.

Throws:

`#`	If Vec2 is null, or has been disposed.
`#`	If this GeomPoly has been disposed.

`winding():Winding`

Compute the winding order for this polygon.

The winding order can be conceptualised by thinking of an analog clock face, if your polygon is the numbers on the clock then a clockwise winding would have your polygon's vertices in numerical order.

In the case of a non-simple polygon with self intersections then the winding order is decided by how 'much' of the polygon is locally clockwise wound, and how much is locally anti-clockwise wound.
(Think of a figure 8 style polygon where one loop is larger than the other. This larger loop will dictate the winding of the polygon.)

If no winding can be computed, then Winding.UNDEFINED will be returned.

Returns:

The winding of the polygon.

Throws:

`#`	If this GeomPoly has been disposed.

final class GeomPoly

package nape.geom

Static methods

@:has_untyped@:value({ vertices : null })staticget(?vertices:Dynamic):GeomPoly

Constructor

@:has_untyped@:value({ vertices : null })new(?vertices:Dynamic)

Variables

zpp_disp:Bool

@:value(null)zpp_inner:ZPP_GeomPoly = null

@:value(null)zpp_pool:GeomPoly = null

Methods

area():Float

inlinebackwardsIterator():GeomVertexIterator

bottom():Vec2

bounds():AABB

clear():GeomPoly

contains(point:Vec2):Bool

@:value({ output : null, delaunay : false })convexDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList

copy():GeomPoly

inlinecurrent():Vec2

@:value({ output : null, boundedEnd : false, boundedStart : false })cut(start:Vec2, end:Vec2, boundedStart:Bool = false, boundedEnd:Bool = false, ?output:GeomPolyList):GeomPolyList

dispose():Void

inlineempty():Bool

erase(count:Int):GeomPoly

inlineforwardIterator():GeomVertexIterator

inflate(inflation:Float):GeomPoly

inlineisClockwise():Bool

isConvex():Bool

inlineisDegenerate():Bool

inlineisMonotone():Bool

inlineisSimple():Bool

inlineiterator():GeomVertexIterator

left():Vec2

@:value({ output : null })monotoneDecomposition(?output:GeomPolyList):GeomPolyList

pop():GeomPoly

push(vertex:Vec2):GeomPoly

right():Vec2

shift():GeomPoly

@:value({ output : null })simpleDecomposition(?output:GeomPolyList):GeomPolyList

simplify(epsilon:Float):GeomPoly

size():Int

inlineskipBackwards(times:Int):GeomPoly

skipForward(times:Int):GeomPoly

@:keeptoString():String

top():Vec2

transform(matrix:Mat23):GeomPoly

@:value({ output : null, delaunay : false })triangularDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList

unshift(vertex:Vec2):GeomPoly

winding():Winding

`@:has_untyped@:value({ vertices : null })staticget(?vertices:Dynamic):GeomPoly`

`@:has_untyped@:value({ vertices : null })new(?vertices:Dynamic)`

`zpp_disp:Bool`

`@:value(null)zpp_inner:ZPP_GeomPoly = null`

`@:value(null)zpp_pool:GeomPoly = null`

`area():Float`

`inlinebackwardsIterator():GeomVertexIterator`

`bottom():Vec2`

`bounds():AABB`

`clear():GeomPoly`

`contains(point:Vec2):Bool`

`@:value({ output : null, delaunay : false })convexDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList`

`copy():GeomPoly`

`inlinecurrent():Vec2`

`@:value({ output : null, boundedEnd : false, boundedStart : false })cut(start:Vec2, end:Vec2, boundedStart:Bool = false, boundedEnd:Bool = false, ?output:GeomPolyList):GeomPolyList`

`dispose():Void`

`inlineempty():Bool`

`erase(count:Int):GeomPoly`

`inlineforwardIterator():GeomVertexIterator`

`inflate(inflation:Float):GeomPoly`

`inlineisClockwise():Bool`

`isConvex():Bool`

`inlineisDegenerate():Bool`

`inlineisMonotone():Bool`

`inlineisSimple():Bool`

`inlineiterator():GeomVertexIterator`

`left():Vec2`

`@:value({ output : null })monotoneDecomposition(?output:GeomPolyList):GeomPolyList`

`pop():GeomPoly`

`push(vertex:Vec2):GeomPoly`

`right():Vec2`

`shift():GeomPoly`

`@:value({ output : null })simpleDecomposition(?output:GeomPolyList):GeomPolyList`

`simplify(epsilon:Float):GeomPoly`

`size():Int`

`inlineskipBackwards(times:Int):GeomPoly`

`skipForward(times:Int):GeomPoly`

`@:keeptoString():String`

`top():Vec2`

`transform(matrix:Mat23):GeomPoly`

`@:value({ output : null, delaunay : false })triangularDecomposition(delaunay:Bool = false, ?output:GeomPolyList):GeomPolyList`

`unshift(vertex:Vec2):GeomPoly`

`winding():Winding`