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.

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

@private

Methods

area():Float

Compute area of weakly-simple polygon.

For complex polygons, this function will return an underestimate to the true area.

Returns:

The area of the polygon.

Throws:

#

If this GeomPoly has been disposed.

inlinebackwardsIterator():GeomVertexIterator

Haxe iterator over vertices of polygon.

Returns:

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

Throws:

#

If this GeomPoly has been disposed.

bottom():Vec2

Find bottom 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 bottom most vertex.

Throws:

#

If polygon is empty.

#

If this GeomPoly has been disposed.

bounds():AABB

Determine bounds of polygon.

Returns:

A new AABB representing bounds of polygon.

Throws:

#

If polygon is empty.

#

If this GeomPoly has been disposed.

clear():GeomPoly

Clear all vertices from polygon.

All of the vertices will be released to the global object pool.

Returns:

A reference to this polygon.

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.

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.