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
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
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
Methods
inlineempty():Bool
Determine if polygon is empty.
Returns:
True if polygon is empty.
Throws:
# | 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. |
---|
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. |
---|
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. |
---|
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. |
---|
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. |
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. |
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. |
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. |
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. |
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. |
---|
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. |
---|
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 <-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.(head)
poly.erase(2);
poly := -> A <-> D <-> E <-> F <-> G <-
(head)
poly.erase(-3);
poly := -> E <-> F <-
(head)
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. |
---|
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. |
---|
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. |
---|
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. |
---|
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. |
---|
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. |
---|
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. |
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.
This algorithm operates in O(n) time.
| | | | <-- convex |/ | \_ | / <-- concave |/
Returns:
True if polygon is found to be convex.
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. |
---|
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.
This algorithm operates in O(n) time.
| | | | <-- y-monotone |___|
|\ | \/| <-- not y-monotone, offending vertex at bottom of the V. |___|
Returns:
True if polygon is y-monotone.
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. |
---|
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. |
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. |
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. |
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. |
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. |
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. |
---|
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. |
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. |
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. |
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. |
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. |
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. |
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. |