GeomPoly

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 Members #

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.

Instance Members #

@private

@private

@private

Determine if polygon is empty.

Determine number of vertices in polygon

Haxe iterator over vertices of polygon.

Haxe iterator over vertices of polygon.

Haxe iterator over vertices of polygon.

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.

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)

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)

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)

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)

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.

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.

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.

Clear all vertices from polygon.

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

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)

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.

@private

Compute area of weakly-simple polygon.

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

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.

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.

Determine if polygon is clockwise wound.

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

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.

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.
|   \ \_|
\__/
_______
|   |   |
|  /_\  | <-- weakly simple polygon.
\_____/
____
| __/
X_  __   <-- complex polygon.
|  \/  \
\__/\__|

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Determine bounds of polygon.

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.

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.

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.

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.

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.

Metadata #