org.openimaj.math.geometry.shape

Class Polygon

java.lang.Object

org.openimaj.math.geometry.point.PointList

org.openimaj.math.geometry.shape.Polygon

All Implemented Interfaces:

Cloneable, Iterable<Point2d>, GeometricObject2d, Shape

Direct Known Subclasses:

Contour, TriangulatedPolygon

public class Polygon
extends PointList
implements Shape

A polygon, modelled as a list of vertices. Polygon extends PointList, so the vertices are the underlying PointList.points, and they are considered to be joined in order.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Field Summary

Fields inherited from class org.openimaj.math.geometry.point.PointList

points

Constructor Summary

Constructors

Constructor and Description
Polygon() Constructs an empty polygon to which vertices may be added.
Polygon(boolean representsHole) Constructs an empty polygon to which vertices may be added.
Polygon(Collection<? extends Point2d> vertices) Construct a Polygon from vertices
Polygon(Collection<? extends Point2d> vertices, boolean copy) Construct a Polygon from the vertices, possibly copying the vertices first
Polygon(Point2d... vertices) Construct a Polygon from vertices

Method Summary

Modifier and Type	Method and Description
void	addInnerPolygon(Polygon p) Add an inner polygon to this polygon.
void	addInnerPolygon(Polygon p, boolean inferOuter) Add an inner polygon to this polygon.
void	addVertex(float x, float y) Add a vertex to the polygon
void	addVertex(Point2d pt) Add a vertex to the polygon
Polygon	asPolygon() Convert the shape to a polygon representation
double	calculateArea() Calculate the area of the shape
Point2d	calculateCentroid() Calculate the centroid of the polygon.
Polygon	calculateConvexHullMelkman() Calculate convex hull using Melkman's algorithm.
double	calculateDirection() Calculates the principle direction of the connected component.
double[]	calculateFirstMoment() Treating the polygon as a continuous piecewise function, calculate exactly the first moment.
double	calculatePerimeter() Calculate the perimeter of the shape
Rectangle	calculateRegularBoundingBox() Compute the regular (oriented to the axes) bounding box of the polygon.
double[]	calculateSecondMoment() Treating the polygon as a continuous piecewise function, calculate exactly the second moment.
double[]	calculateSecondMomentCentralised() Treating the polygon as a continuous piecewise function, calculate exactly the centralised second moment.
double	calculateSignedArea() Calculate the area of the polygon.
Polygon	clone()
void	close() Close the polygon if it's not already closed
Point2d	closestPoint(Point2d pt) Find the closest point on the polygon to the given point
Polygon	difference(Polygon p) Calculates the difference between two polygons and returns a new polygon.
boolean	equals(Object obj)
boolean	equals(Polygon p) Specific equals method for polygons where the polgyons are tested for the vertices being in the same order.
Polygon	getInnerPoly(int index) Get the inner polygon at the given index.
List<Polygon>	getInnerPolys() Returns the list of inner polygons.
int	getNumInnerPoly() Returns the number of inner polygons in this polygon including this polygon.
List<Point2d>	getVertices() Get the vertices of the polygon
int	hashCode()
boolean	hasNoInnerPolygons() Test if this has no inner polygons or sub-parts
Polygon	intersect(Polygon p2) Returns the intersection of this polygon and the given polygon.
double	intersectionArea(Shape that) Calls intersectionArea(Shape, int) with 1 step per pixel dimension.
double	intersectionArea(Shape that, int nStepsPerDimension) Return an estimate for the area of the intersection of this polygon and another polygon.
boolean	isClockwise() Test (outer) polygon path direction
boolean	isClosed() Is the polygon closed (i.e.
boolean	isConvex() Test if the outer polygon is convex.
boolean	isEmpty() Return whether this polygon has no vertices or not.
boolean	isHole() Returns whether this polygon is representing a hole in another polygon.
boolean	isInside(Point2d point) Test whether the point p is inside the polygon using the winding rule algorithm.
RotatedRectangle	minimumBoundingRectangle() Compute the minimum size rotated bounding rectangle that contains this shape using the rotating calipers approach.
RotatedRectangle	minimumBoundingRectangle(boolean assumeSimple) Compute the minimum size rotated bounding rectangle that contains this shape using the rotating calipers approach.
int	nVertices() Get the number of vertices
void	open() Open the polygon if it's closed
Polygon	reduceVertices(double eps) Reduce the number of vertices in a polygon.
Polygon	roundVertices() Iterates through the vertices and rounds all vertices to round integers.
void	scale(float sc) Scale the polygon by the given amount about (0,0).
void	scale(Point2d centre, float sc) Scale the polygon by the given amount about the given point.
Polygon	scaleX(float sc) Scale the polygon only in the x-direction by the given amount about (0,0).
Polygon	scaleXY(float scx, float scy) Scale the polygon by the given amount about (0,0).
Polygon	scaleY(float sc) Scale the polygon only in the y-direction by the given amount about (0,0).
void	setIsHole(boolean isHole) Set whether this polygon represents a hole in another polygon.
Ellipse	toEllipse() Using EllipseUtilities.ellipseFromCovariance(float, float, Matrix, float) and the calculateSecondMomentCentralised() return the Ellipse best fitting the shape of this polygon.
String	toString() Displays the complete list of vertices unless the number of vertices is greater than 10 - then a sublist is shown of 5 from the start and 5 from the end separated by ellipses.
Polygon	transform(Jama.Matrix transform) Apply a 3x3 transform matrix to a copy of the polygon and return it
void	translate(float x, float y) Translate the polygons position
Polygon	union(Polygon p2) Returns the union of this polygon and the given polygon.
Polygon	xor(Polygon p2) Returns the XOR of this polygon and the given polygon.

Methods inherited from class org.openimaj.math.geometry.point.PointList

calculateConvexHull, computeIntrinsicScale, computeMean, get, getHeight, getLines, getLines, getWidth, iterator, maxX, maxY, minX, minY, rotate, rotate, scaleCentroid, size

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.openimaj.math.geometry.GeometricObject2d

getHeight, getWidth, maxX, maxY, minX, minY, scaleCentroid

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

Polygon

public Polygon()

Constructs an empty polygon to which vertices may be added.

Polygon

public Polygon(boolean representsHole)

Constructs an empty polygon to which vertices may be added. The boolean parameter determines whether this polygon will represent a hole (rather than a solid).

Parameters:

representsHole - Whether the polygon will represent a hole.

Polygon

public Polygon(Point2d... vertices)

Construct a Polygon from vertices

Parameters:

vertices - the vertices

Polygon

public Polygon(Collection<? extends Point2d> vertices)

Construct a Polygon from vertices

Parameters:

vertices - the vertices

Polygon

public Polygon(Collection<? extends Point2d> vertices,
               boolean copy)

Construct a Polygon from the vertices, possibly copying the vertices first

Parameters:

vertices - the vertices

copy - should the vertices be copied

Method Detail

getVertices

public List<Point2d> getVertices()

Get the vertices of the polygon

Returns:

the vertices

nVertices

public int nVertices()

Get the number of vertices

Returns:

the number of vertices

isClosed

public boolean isClosed()

Is the polygon closed (i.e. is the last vertex equal to the first)?

Returns:

true if closed; false if open

close

public void close()

Close the polygon if it's not already closed

open

public void open()

Open the polygon if it's closed

isInside

public boolean isInside(Point2d point)

Test whether the point p is inside the polygon using the winding rule algorithm. Also tests whether the point is in any of the inner polygons. If the inner polygon represents a hole and the point is within that polygon then the point is not within this polygon.

Specified by:

isInside in interface Shape

Parameters:

point - the point to test

Returns:

true if the point is inside; false otherwise

clone

public Polygon clone()

Specified by:

clone in interface Shape

Overrides:

clone in class PointList

Returns:

a copy of the shape

difference

public Polygon difference(Polygon p)

Calculates the difference between two polygons and returns a new polygon. It assumes that the given polygon and this polygon have the same number of vertices.

Parameters:

p - the polygon to subtract.

Returns:

the difference polygon

calculateArea

public double calculateArea()

Description copied from interface: Shape

Calculate the area of the shape

Specified by:

calculateArea in interface Shape

Returns:

the area of the shape

calculateSignedArea

public double calculateSignedArea()

Calculate the area of the polygon. This does not take into account holes in the polygon.

Returns:

the area of the polygon

intersectionArea

public double intersectionArea(Shape that)

Calls intersectionArea(Shape, int) with 1 step per pixel dimension. Subsequently this function returns the shared whole pixels of this polygon and that.

Specified by:

intersectionArea in interface Shape

Parameters:

that -

Returns:

intersection area

intersectionArea

public double intersectionArea(Shape that,
                               int nStepsPerDimension)

Return an estimate for the area of the intersection of this polygon and another polygon. For each pixel step 1 is added if the point is inside both polygons. For each pixel, perPixelPerDimension steps are taken. Subsequently the intersection is: sumIntersections / (perPixelPerDimension * perPixelPerDimension)

Specified by:

intersectionArea in interface Shape

Parameters:

that -

Returns:

normalised intersection area

asPolygon

public Polygon asPolygon()

Convert the shape to a polygon representation

Specified by:

asPolygon in interface Shape

Returns:

a polygon representation of the shape

See Also:

Shape.asPolygon()

addVertex

public void addVertex(float x,
                      float y)

Add a vertex to the polygon

Parameters:

x - x-coordinate of the vertex

y - y-coordinate of the vertex

addVertex

public void addVertex(Point2d pt)

Add a vertex to the polygon

Parameters:

pt - coordinate of the vertex

roundVertices

public Polygon roundVertices()

Iterates through the vertices and rounds all vertices to round integers. Side-affects this polygon.

Returns:

this polygon

isEmpty

public boolean isEmpty()

Return whether this polygon has no vertices or not.

Returns:

TRUE if this polygon has no vertices

getNumInnerPoly

public int getNumInnerPoly()

Returns the number of inner polygons in this polygon including this polygon.

Returns:

the number of inner polygons in this polygon.

getInnerPoly

public Polygon getInnerPoly(int index)

Get the inner polygon at the given index. Note that index 0 will return this polygon, while index i+1 will return the inner polygon i.

Parameters:

index - the index of the polygon to get

Returns:

The inner polygon at the given index.

addInnerPolygon

public void addInnerPolygon(Polygon p,
                            boolean inferOuter)

Add an inner polygon to this polygon. If there is no main polygon defined (the number of vertices is zero) then the given inner polygon will become the main polygon if the inferOuter boolean is true. If this variable is false, the inner polygon will be added to the list of inner polygons for this polygon regardless of whether a main polygon exists. When the main polygon is inferred from the given polygon, the vertices are copied into this polygon's vertex list.

Parameters:

p - The inner polygon to add

inferOuter - Whether to infer the outer polygon from this inner one

addInnerPolygon

public void addInnerPolygon(Polygon p)

Add an inner polygon to this polygon. If there is no main polygon defined (the number of vertices is zero) then the given inner polygon will become the main polygon.

Parameters:

p - The inner polygon to add

getInnerPolys

public List<Polygon> getInnerPolys()

Returns the list of inner polygons.

Returns:

the list of inner polygons

setIsHole

public void setIsHole(boolean isHole)

Set whether this polygon represents a hole in another polygon.

Parameters:

isHole - Whether this polygon is a whole.

isHole

public boolean isHole()

Returns whether this polygon is representing a hole in another polygon.

Returns:

Whether this polygon is representing a hole in another polygon.

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

See Also:

Object.equals(java.lang.Object)

equals

public boolean equals(Polygon p)

Specific equals method for polygons where the polgyons are tested for the vertices being in the same order. If the vertices are not in the vertex list in the same manner but are in the same order (when wrapped around) the method will return true. So the triangles below will return true: {[1,1],[2,2],[1,2]} and {[1,2],[1,1],[2,2]}

Parameters:

p - The polygon to test against

Returns:

TRUE if the polygons are the same.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

See Also:

Object.hashCode()

toString

public String toString()

Displays the complete list of vertices unless the number of vertices is greater than 10 - then a sublist is shown of 5 from the start and 5 from the end separated by ellipses.

Overrides:

toString in class PointList

See Also:

Object.toString()

intersect

public Polygon intersect(Polygon p2)

Returns the intersection of this polygon and the given polygon.

Parameters:

p2 - The polygon to intersect with.

Returns:

The resulting polygon intersection

union

public Polygon union(Polygon p2)

Returns the union of this polygon and the given polygon.

Parameters:

p2 - The polygon to union with.

Returns:

The resulting polygon union

xor

public Polygon xor(Polygon p2)

Returns the XOR of this polygon and the given polygon.

Parameters:

p2 - The polygon to XOR with.

Returns:

The resulting polygon

reduceVertices

public Polygon reduceVertices(double eps)

Reduce the number of vertices in a polygon. This implementation is based on a modified Ramer-Douglas–Peucker algorithm that is designed to work with polygons rather than polylines. The implementation searches for two initialisation points that are approximatatly maximally distant, then performs the polyline algorithm on the two segments, and finally ensures that the joins in the segments are consistent with the given epsilon value.

Parameters:

eps - distance value below which a vertex can be ignored

Returns:

new polygon that approximates this polygon, but with fewer vertices

transform

public Polygon transform(Jama.Matrix transform)

Apply a 3x3 transform matrix to a copy of the polygon and return it

Specified by:

transform in interface GeometricObject2d

Specified by:

transform in interface Shape

Overrides:

transform in class PointList

Parameters:

transform - 3x3 transform matrix

Returns:

the transformed polygon

calculateRegularBoundingBox

public Rectangle calculateRegularBoundingBox()

Compute the regular (oriented to the axes) bounding box of the polygon.

Specified by:

calculateRegularBoundingBox in interface GeometricObject2d

Overrides:

calculateRegularBoundingBox in class PointList

Returns:

the regular bounding box as [x,y,width,height]

translate

public void translate(float x,
                      float y)

Translate the polygons position

Specified by:

translate in interface GeometricObject2d

Overrides:

translate in class PointList

Parameters:

x - x-translation

y - y-translation

scale

public void scale(float sc)

Scale the polygon by the given amount about (0,0). Scalefactors between 0 and 1 shrink the polygon.

Specified by:

scale in interface GeometricObject2d

Overrides:

scale in class PointList

Parameters:

sc - the scale factor.

scaleX

public Polygon scaleX(float sc)

Scale the polygon only in the x-direction by the given amount about (0,0). Scale factors between 0 and 1 will shrink the polygon

Overrides:

scaleX in class PointList

Parameters:

sc - The scale factor

Returns:

this polygon

scaleY

public Polygon scaleY(float sc)

Scale the polygon only in the y-direction by the given amount about (0,0). Scale factors between 0 and 1 will shrink the polygon

Overrides:

scaleY in class PointList

Parameters:

sc - The scale factor

Returns:

this polygon

scaleXY

public Polygon scaleXY(float scx,
                       float scy)

Scale the polygon by the given amount about (0,0). Scale factors between 0 and 1 shrink the polygon.

Overrides:

scaleXY in class PointList

Parameters:

scx - the scale factor in the x direction

scy - the scale factor in the y direction.

Returns:

this polygon

scale

public void scale(Point2d centre,
                  float sc)

Scale the polygon by the given amount about the given point. Scalefactors between 0 and 1 shrink the polygon.

Specified by:

scale in interface GeometricObject2d

Overrides:

scale in class PointList

Parameters:

centre - the centre of the scaling operation

sc - the scale factor

calculateCentroid

public Point2d calculateCentroid()

Calculate the centroid of the polygon.

Specified by:

calculateCentroid in interface GeometricObject2d

Overrides:

calculateCentroid in class PointList

Returns:

calls calculateFirstMoment();

calculateFirstMoment

@Reference(author="Carsten Steger",
           title="On the Calculation of Moments of Polygons",
           type=Techreport,
           month="August",
           year="1996",
           url="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.8765&rep=rep1&type=pdf")
public double[] calculateFirstMoment()

Treating the polygon as a continuous piecewise function, calculate exactly the first moment. This follows working presented by Carsten Steger in "On the Calculation of Moments of Polygons" ,

Returns:

the first moment

calculateSecondMoment

@Reference(author="Carsten Steger",
           title="On the Calculation of Moments of Polygons",
           type=Techreport,
           month="August",
           year="1996",
           url="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.8765&rep=rep1&type=pdf")
public double[] calculateSecondMoment()

Treating the polygon as a continuous piecewise function, calculate exactly the second moment. This follows working presented by Carsten Steger in "On the Calculation of Moments of Polygons" ,

Returns:

the second moment as an array with values: (axx,axy,ayy)

calculateSecondMomentCentralised

@Reference(author="Carsten Steger",
           title="On the Calculation of Moments of Polygons",
           type=Techreport,
           month="August",
           year="1996",
           url="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.8765&rep=rep1&type=pdf")
public double[] calculateSecondMomentCentralised()

Treating the polygon as a continuous piecewise function, calculate exactly the centralised second moment. This follows working presented by Carsten Steger in "On the Calculation of Moments of Polygons" ,

Returns:

the second moment as an array with values: (axx,axy,ayy)

calculateDirection

public double calculateDirection()

Calculates the principle direction of the connected component. This is given by 0.5 * atan( (M20-M02) / 2 * M11 ) so results in an angle between -PI and +PI.

Returns:

The principle direction (-PI/2 to +PI/2 radians) of the connected component.

toEllipse

public Ellipse toEllipse()

Using EllipseUtilities.ellipseFromCovariance(float, float, Matrix, float) and the calculateSecondMomentCentralised() return the Ellipse best fitting the shape of this polygon.

Returns:

Ellipse defining the shape of the polygon

isConvex

public boolean isConvex()

Test if the outer polygon is convex.

Specified by:

isConvex in interface Shape

Returns:

true if the outer polygon is convex; false if non-convex or less than two vertices

hasNoInnerPolygons

public boolean hasNoInnerPolygons()

Test if this has no inner polygons or sub-parts

Returns:

true if this is polygon has no inner polygons; false otherwise.

See Also:

getInnerPolys()

calculatePerimeter

public double calculatePerimeter()

Description copied from interface: Shape

Calculate the perimeter of the shape

Specified by:

calculatePerimeter in interface Shape

Returns:

the perimeter of the shape

isClockwise

public boolean isClockwise()

Test (outer) polygon path direction

Returns:

true is the outer path direction is clockwise w.r.t OpenIMAJ coordinate system

calculateConvexHullMelkman

public Polygon calculateConvexHullMelkman()

Calculate convex hull using Melkman's algorithm. This is faster than the PointList.calculateConvexHull() method, but will only work for simple polygons (those that don't self-intersect)

Based on http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm, but modified (fixed) to deal with the problem of the initialisation points potentially being co-linear.

Copyright 2001, softSurfer (www.softsurfer.com) This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application.

Returns:

A polygon defining the shape of the convex hull

minimumBoundingRectangle

public RotatedRectangle minimumBoundingRectangle()

Compute the minimum size rotated bounding rectangle that contains this shape using the rotating calipers approach.

Specified by:

minimumBoundingRectangle in interface Shape

Returns:

the minimum bounding box

See Also:

Shape.minimumBoundingRectangle(), RotatingCalipers.getMinimumBoundingRectangle(Polygon, boolean)

minimumBoundingRectangle

public RotatedRectangle minimumBoundingRectangle(boolean assumeSimple)

Compute the minimum size rotated bounding rectangle that contains this shape using the rotating calipers approach.

Parameters:

assumeSimple - can the algorithm assume the polygon is simple and use an optimised (Melkman's) convex hull?

Returns:

the minimum bounding box

See Also:

RotatingCalipers.getMinimumBoundingRectangle(Polygon, boolean)

closestPoint

public Point2d closestPoint(Point2d pt)

Find the closest point on the polygon to the given point

Parameters:

pt - the point

Returns:

the closest point