A polygon of 2D-points. More...

#include <Polygon2D.hpp>

Inheritance diagram for datatypes::Polygon2D:

Public Types
typedef std::vector< Point2D >	base_class
	The base type. (Naming according to boost convention.)
typedef Point2D::value_type	floatingpoint_type
Public Member Functions
virtual const UINT32	getUsedMemory () const
	Polygon2D ()
	Constructor for an empty polygon.
	Polygon2D (const Point2D &)
	Convenience constructor for a polygon with one Point.
	Polygon2D (const Point2D &, const Point2D &)
	Convenience constructor for a polygon with two Points.
	Polygon2D (const Point2D &, const Point2D &, const Point2D &)
	Convenience constructor for a polygon with three Points.
	Polygon2D (const Point2D &, const Point2D &, const Point2D &, const Point2D &)
	Convenience constructor for a polygon with four Points.
	Polygon2D (const Line2D &)
	Convenience constructor for a polygon with the two points of a line.
	Polygon2D (const base_class &)
	Copy constructor from a std::vector.
	Polygon2D (const std::string &polygonAsString)
	Constructor for reading from a string using fromString()
std::string	toString () const
	Text output for debugging.
Set functions
See also: base_class::push_back, base_class::insert
Polygon2D &	append (const Polygon2D &other)
	Appends the points of the `other` polygon to this polygon.
Polygon2D &	append (const Point2D &point)
	Appends one point `point` to this polygon.
Polygon2D &	append (floatingpoint_type x, floatingpoint_type y)
	Appends one point with coordinates `x` and `y` to this polygon.
Accessor methods for information about this polygon
bool	isClosed () const
	Returns true if this is explicitly a closed polygon.
double	getArea () const
	Returns the area enclosed by this polygon.
Point2D	getCenterOfGravity () const
	Returns the center of gravity of this polygon.
Polygon2D	getSimplified () const
	Returns a polygon with potentially less edge points.
Box2D	getBoundingBox () const
	Returns a Box in parallel to the coordinate system that bounds this polygon.
std::pair< floatingpoint_type, floatingpoint_type >	getBoundingAngles () const
Geometrical relations to other objects
bool	containsPoint (const Point2D &point) const
	Returns true if the given Point2D is inside this polygon.
Point2D::value_type	distanceToPoint (const Point2D &point) const
	Returns the distance of a point to this polyon.
bool	isColliding (const Polygon2D &p2) const
	Returns true if the given polygon collides with this polygon.
base_class	isIntersecting (const Line2D &other) const
	Calculates all intersection points between a line and this polygon.
Static Public Member Functions
static Polygon2D	createRectangle (const Point2D &lowerLeft, const Point2D &upperRight)
static Polygon2D	fromArc (const Ellipse2D &ellipse, const floatingpoint_type startAngle, const floatingpoint_type endAngle, const UINT32 samplingPoints, const bool clockwise)
	(DEPRECATED) Create a Polygon2D approximation of the arc of an ellipse
static Polygon2D	fromArc (const Ellipse2D &ellipse, const floatingpoint_type startAngle, const floatingpoint_type endAngle, const UINT32 samplingPoints=32)
	Create a Polygon2D approximation of the arc of an ellipse.
static Polygon2D	fromCircle (const Point2D &center, const floatingpoint_type radius, const UINT32 samplingPoints=32)
	Static function to get Polygon2D from circle parameters.
static Polygon2D	fromEllipse (const Point2D &center, const floatingpoint_type a, const floatingpoint_type b, const floatingpoint_type angle, const UINT32 samplingPoints=32)
	Static function to create a Polygon2D from ellipse parameters.
static Polygon2D	fromEllipse (const Ellipse2D &ellipse, const UINT32 samplingPoints=32)
	Static function to create a Polygon2D from ellipse parameters.
static const char *	getSeparatorCharacters ()
static Polygon2D	rhombus (const Point2D &center, const floatingpoint_type radius)
	Static function to create a rhombus.

Detailed Description

A polygon of 2D-points.

The points can be accessed through the std::vector interface. Basic information available through the std::vector base class include:

empty() returns true if the polygon contains zero points
size() returns the number of points in the polygon
front() returns a reference to the first point in a non-empty polygon
back() returns a reference to the last point

To access all points, use operator[]() or begin() and end() with a Polygon2D::const_iterator or Polygon2D::iterator.

The polygon can be interpreted as closed polygon either implicitly or explicitly. For explicitly closed polygons, the final Point2D is identical to the first one and isClosed() returns true. On the other hand, several use cases of the Polygon2D assume the polygon to be closed without the explicit final point identical to the first one, so even without the additional final point the polygon is probably fine most of the time.

Definition at line 43 of file Polygon2D.hpp.

Member Typedef Documentation

typedef std::vector<Point2D> datatypes::Polygon2D::base_class

The base type. (Naming according to boost convention.)

Definition at line 48 of file Polygon2D.hpp.

typedef Point2D::value_type datatypes::Polygon2D::floatingpoint_type

The type of the stored x, y coordinates of each of the points in this polygon.

Definition at line 52 of file Polygon2D.hpp.

Constructor & Destructor Documentation

datatypes::Polygon2D::Polygon2D ( )

Constructor for an empty polygon.

Definition at line 23 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D ( const Point2D & p1 )

Convenience constructor for a polygon with one Point.

Definition at line 27 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D	(	const Point2D &	p1,
		const Point2D &	p2
	)

Convenience constructor for a polygon with two Points.

Definition at line 32 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D	(	const Point2D &	p1,
		const Point2D &	p2,
		const Point2D &	p3
	)

Convenience constructor for a polygon with three Points.

Definition at line 37 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D	(	const Point2D &	p1,
		const Point2D &	p2,
		const Point2D &	p3,
		const Point2D &	p4
	)

Convenience constructor for a polygon with four Points.

Definition at line 44 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D ( const Line2D & )

Convenience constructor for a polygon with the two points of a line.

datatypes::Polygon2D::Polygon2D ( const base_class & other_vector )

Copy constructor from a std::vector.

Definition at line 60 of file Polygon2D.cpp.

datatypes::Polygon2D::Polygon2D ( const std::string & polygonAsString )

Constructor for reading from a string using fromString()

Member Function Documentation

Polygon2D & datatypes::Polygon2D::append ( const Polygon2D & other )

Appends the points of the other polygon to this polygon.

This is identical to the std::vector method p.insert(p.end(),other.begin(),other.end());

See also:: base_class::push_back, base_class::insert

Definition at line 72 of file Polygon2D.cpp.

Polygon2D & datatypes::Polygon2D::append ( const Point2D & point )

Appends one point point to this polygon.

This is identical to the std::vector method push_back() but returns a reference to this.

See also:: base_class::push_back

Definition at line 78 of file Polygon2D.cpp.

Polygon2D & datatypes::Polygon2D::append	(	floatingpoint_type	x,
		floatingpoint_type	y
	)

Appends one point with coordinates x and y to this polygon.

This is a shortcut for creating a new point with the coordinates x and y and using std::vector's method push_back() to append the point.

See also:: base_class::push_back

Definition at line 84 of file Polygon2D.cpp.

bool datatypes::Polygon2D::containsPoint ( const Point2D & point ) const

Returns true if the given Point2D is inside this polygon.

This is a Point-in-polygon test using ray-casting algorithm (Jordan curve theorem). It is really fast and also works for non-convex and self-intersecting polygons.

However, Points which are directly on one boundary are classified as either inside or outside, depending on which edge of the polygon this is. In other words, this method cannot be used to find points which are exactly on the edge of a polygon! (Citation from the URL below: "If you want to know when a point is exactly on the boundary, you need another program. This is only one of many functions that PNPOLY lacks; it also doesn't predict tomorrow's weather. You are free to extend PNPOLY's source code.")

Algorithm: From the test point a semi-finite ray is run through the polygon. While doing so the number of edge crossings are counted. If the number of crossings is even, the test point is located outside of the polygon. If the number is odd, the point is inside. (Jordan curve theorem)

The polygon may be closed explicitly or implicitly, both will work. I.e., if the polygon contains an additional final point identical to the first one, this algorithms works correctly, but it also works correctly without such an additional final point.

As for multiple components and holes:

The polygon may contain multiple separate components, and/or holes, provided that you separate the components and holes with a (0,0) point, as follows.

First, include a (0,0) point.
Then include the first component' points, repeating its first point after the last point.
Include another (0,0) point.
Include another component or hole, repeating its first point after the last point.
Repeat the above two steps for each component and hole.
Include a final (0,0) point.

Each component or hole's points may be listed either clockwise or counter-clockwise.

If there is only one connected component, then it is optional to repeat the first point at the end. It's also optional to surround the component with zero points.

C-Code was borrowed from: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html See there for further explanation of the border cases.

Definition at line 420 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::createRectangle	(	const Point2D &	lowerLeft,
		const Point2D &	upperRight
	)		`[static]`

Static function to create a four-point rectangle from a lower left and an upper right point.

Note: The returned polygon contains the four points of the rectangle. This means isClosed() does not return true. To be closed in the sense of isClosed(), the polygon manually needs to have the first point added as the last (fifth) point as well. On the other hand, several use cases of the Polygon2D assume the polygon to be closed without the explicit final point identical to the first one, so this four-point rectangle is probably fine most of the time.

Returns:: A polygon with four points representing the edge points of a rectangle.

Definition at line 248 of file Polygon2D.cpp.

Point2D::value_type datatypes::Polygon2D::distanceToPoint ( const Point2D & point ) const

Returns the distance of a point to this polyon.

For each line segment of this polygon, this function calculates three distances: The distances to both end points of the segment and the distance of the point to its projection onto the line segment. The overall minimum distance over these three possibilities and over all line segments will be returned.

Internally, this will use Line2D::distanceFromLineSegment() for one segment and return the minimum of that over all segments.

Definition at line 535 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::fromArc	(	const Ellipse2D &	ellipse,
		const floatingpoint_type	startAngle,
		const floatingpoint_type	endAngle,
		const UINT32	samplingPoints,
		const bool	clockwise
	)		`[static]`

(DEPRECATED) Create a Polygon2D approximation of the arc of an ellipse

DEPRECATED: Use the other fromArc() function instead, because the "direction" argument is difficult to understand correctly.

Function starts at startAngle and moves to endAngle in a selectable direction.

The number of sampling points must be at least 2 (one at the start, one at the end), otherwise an empty Polygon will be returned.

Parameters:

ellipse	The ellipse center, axis length, and rotation
startAngle	The start angle from which the arc will be drawn
endAngle	The end angle until which the arc will be drawn
samplingPoints	Number of points which the resulting polygon will contain. If less then 2, an empty Polygon2D will be returned.
clockwise	If true, the arc should be plotted from the startAngle in clockwise direction to the endAngle (mathematically negative). If false, the arc is plotted from the start angle in counter-clockwise direction to the end angle (mathematically positive).

Definition at line 162 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::fromArc	(	const Ellipse2D &	ellipse,
		const floatingpoint_type	startAngle,
		const floatingpoint_type	endAngle,
		const UINT32	samplingPoints = `32`
	)		`[static]`

Create a Polygon2D approximation of the arc of an ellipse.

The function starts at startAngle and calculates sampling points on the way to the endAngle in mathematically positive direction (counter-clockwise), where the startAngle is lesser than the endAngle.

When an arc in the other direction is needed, simply specify a startAngle greater than the endAngle, which will result in an arc in mathematically negative direction (clockwise).

The resulting polygon is explicitly closed (except for rounding errors), that is, the first sampling point will be located exactly at startAngle and the last sampling point exactly at endAngle. If the angles are 0 and 2*pi, the last point will be approximately identical to the first one except for rounding errors, which means the polygon is appoximately closed but isClosed() might not be true.

(Successor of the other fromArc() function because the "direction" argument is difficult to understand correctly.)

The number of sampling points must be at least 2 (one at the start, one at the end), otherwise an empty Polygon will be returned.

Parameters:

ellipse	The ellipse center, axis length, and rotation
startAngle	The start angle from which the arc will be drawn
endAngle	The end angle until which the arc will be drawn. For an arc in mathematically positive direction (counter-clockwise), this angle needs to be greater than the startAngle, otherwise lesser. The absolute difference between start and end angle must be at most 2*pi, otherwise an exception will be thrown.
samplingPoints	Number of points which the resulting polygon will contain. If less then 2, an empty Polygon2D will be returned.

Returns:: An approximation polygon of the arc of an ellipse.

Definition at line 189 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::fromCircle	(	const Point2D &	center,
		const floatingpoint_type	radius,
		const UINT32	samplingPoints = `32`
	)		`[static]`

Static function to get Polygon2D from circle parameters.

Definition at line 138 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::fromEllipse	(	const Point2D &	center,
		const floatingpoint_type	a,
		const floatingpoint_type	b,
		const floatingpoint_type	angle,
		const UINT32	samplingPoints = `32`
	)		`[static]`

Static function to create a Polygon2D from ellipse parameters.

Definition at line 144 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::fromEllipse	(	const Ellipse2D &	ellipse,
		const UINT32	samplingPoints = `32`
	)		`[static]`

Static function to create a Polygon2D from ellipse parameters.

Definition at line 150 of file Polygon2D.cpp.

double datatypes::Polygon2D::getArea ( ) const

Returns the area enclosed by this polygon.

Note: The polyon must be a non-self-intersecting polygon, i.e. a simple polygon.

Definition at line 90 of file Polygon2D.cpp.

std::pair< Polygon2D::floatingpoint_type, Polygon2D::floatingpoint_type > datatypes::Polygon2D::getBoundingAngles ( ) const

This function calculates a low and a high boundary angle for all edges of the given polygon. The returned FloatPair has the component "first" for the lower bounding angle, and "second" for the upper bounding angle.

(Note: This ordering is swapped compared to the scan point ordering!)

Definition at line 306 of file Polygon2D.cpp.

Box2D datatypes::Polygon2D::getBoundingBox ( ) const

Returns a Box in parallel to the coordinate system that bounds this polygon.

This function calculates a bounding box to the given polygon. The returned box will have zero rotation and will be in parallel to the coordinate system.

Definition at line 277 of file Polygon2D.cpp.

Point2D datatypes::Polygon2D::getCenterOfGravity ( ) const

Returns the center of gravity of this polygon.

Based on the edges of this polygon, this function returns the center of gravity. (The returned value is simply the arithmetic mean of all edges.)

Definition at line 108 of file Polygon2D.cpp.

const char * datatypes::Polygon2D::getSeparatorCharacters ( ) [static]

Returns a string containing a list of separator characters that is accepted when parsing a string in fromString().

Definition at line 231 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::getSimplified ( ) const

Returns a polygon with potentially less edge points.

This method checks the polygon for "unnecessary" edges and returns a polygon with those edges removed. For each edge, it is checked whether they are located directly on the connection line between the edge before and after the middle edge. If this is the case, the middle edge can be removed without changing the shape of the polygon.

Definition at line 552 of file Polygon2D.cpp.

virtual const UINT32 datatypes::Polygon2D::getUsedMemory ( ) const [inline, virtual]

Implements datatypes::BasicData.

Definition at line 79 of file Polygon2D.hpp.

bool datatypes::Polygon2D::isClosed ( ) const

Returns true if this is explicitly a closed polygon.

This simply means the last point back() is equal to the first point front() of the polygon.

On the other hand, several use cases of the Polygon2D assume the polygon to be closed even without the explicit final point identical to the first one, so polygons with the return value false here are probably still fine most of the time.

An empty polygon (where empty() returns true) is not closed by definition and isClosed() will return false.

Definition at line 127 of file Polygon2D.cpp.

bool datatypes::Polygon2D::isColliding ( const Polygon2D & p2 ) const

Returns true if the given polygon collides with this polygon.

In other words, there exists an intersection region or at least one intersecting point between these two polygons.

Note: This might only work for convex polygons!

Definition at line 492 of file Polygon2D.cpp.

Polygon2D::base_class datatypes::Polygon2D::isIntersecting ( const Line2D & other ) const

Calculates all intersection points between a line and this polygon.

A line can have zero, one, or up to size() intersection points with this polygon. The returned list of points contains all those intersection points between the given line and all line segments of this polygon.

In contrast to Line2D::isIntersecting() this method considers and returns only those intersection points which are within the line segments.

Definition at line 517 of file Polygon2D.cpp.

Polygon2D datatypes::Polygon2D::rhombus	(	const Point2D &	center,
		const floatingpoint_type	radius
	)		`[static]`

Static function to create a rhombus.

Definition at line 236 of file Polygon2D.cpp.

std::string datatypes::Polygon2D::toString ( ) const

Text output for debugging.

This string can be parsed into a polygon again by using fromString().

Definition at line 584 of file Polygon2D.cpp.

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation