Polygon2 Class Reference

Polygons in the plane. More...

#include <polygon.h>

Inheritance diagram for Polygon2:

Public Member Functions
	Polygon2 ()
	Create an empty polygon.
	Polygon2 (const Vector2 &, const Vector2 &, const Vector2 &)
	Create a triangle.
	Polygon2 (const Vector2 &, const Vector2 &, const Vector2 &, const Vector2 &)
	Create a quadrangle.
	Polygon2 (const QVector< Vector > &)
	Create a polygon.
	Polygon2 (const QVector< Vector2 > &)
	Create a polygon.
	Polygon2 (const QVector< Vector2 > &, const QVector< int > &)
	Create a polygon.
	Polygon2 (const Triangle2 &)
	Create a triangle.
	Polygon2 (const Box2 &)
	Create a polygon from a box.
	Polygon2 (const Hexagon2 &)
	Create a hexagon.
	Polygon2 (const Pentagon2 &)
	Create a pentagon.
	Polygon2 (const Quadrangle2 &)
	Create a quadrangle.
	Polygon2 (const Polygonal &)
	Create a planar polygon for a polygon.
	Polygon2 (const Octogon2 &)
	Create an octogon.
	Polygon2 (const IrregularOctogon2 &)
	Create an irregular octogon.
	Polygon2 (const Ellipse2 &, int=72)
	Create a polygon approximation of an ellipse.
	Polygon2 (const Circle2 &, int=72)
	Create a polygon approximation of an circle.
double	Hausdorff (const Polygon2 &, bool=false) const
	Compute the Hausdorff distance between two polygons.
Box2	GetBox () const
	Compute the bounding box of the polygon.
OrientedBox2	GetOrientedBox () const
	Compute the oriented bounding box of the polygon.
Polygon2	Scaled (const Vector2 &) const
	Return the scaled polygon.
Polygon2	Scaled (const double &) const
	Return the scaled polygon.
Polygon2	Translated (const Vector2 &) const
	Translate the polygon by a given vector.
Polygon2	Rotated (const Matrix2 &) const
	Rotate the polygon.
Polygon2	Rotated (const double &) const
	Rotate the polygon.
Polygon2	Transformed (const Frame2 &) const
	Trasform the polygon.
Polygon2	Transformed (const FrameScaled2 &) const
	Trasform the polygon.
void	Translate (const Vector2 &)
	Translate the polygon by a given vector.
void	Scale (const double &)
	Scale the polygon by a given factor.
void	Rotate (const Matrix2 &)
	Rotate the polygon.
void	Append (const Vector2 &)
	Add a vertex to the polygon.
void	Append (const Vector2 &, int)
	Add a vertex at the given id to the polygon.
Vector2 &	Vertex (int)
	Read write access to the i-th point.
Vector2	Vertex (int) const
	Read only access to the i-th point.
QVector< Vector2 >	Vertices ()
	Get the array of vertices.
const QVector< Vector2 > &	Vertices () const
	Get the array of vertices.
Vector2	Edge (int) const
	Return the i-th edge, starting from the i-th vertex.
int	Size () const
	Return the number of vertices of the polygon.
bool	IsConvex () const
	Check whether the polygon is convex.
Vector2	PointAtLength (const double &) const
	Return the position of the point on the polygon at a given length from the starting point.
Vector2	NormalAtLength (const double &) const
	Return the normal at the position of the point on the polygon.
bool	Inside (const Vector2 &) const
	Check if a point is inside or outside of the polygon.
double	R (const Vector2 &) const
	Compute the squared distance between a point and a polygon.
double	R (const Line2 &) const
	Compute the distance from a polygon to a line.
double	Signed (const Vector2 &) const
	Compute the signed distance between a point and a polygon.
bool	Cut (const Line2 &line, const Vector2 &insidePoint)
	Cut the polygon by a line.
bool	Intersect (const Circle2 &) const
	Check the intersection between the boundaty of the polygon and a circle.
bool	Intersect (const Triangle2 &) const
	Test if a triangle intersects the polygon.
bool	Intersect (const Segment2 &) const
	Test if a segment intersects the polygon.
int	Where (const Circle2 &) const
	Check the position of a circle againts the polygon.
double	Area (bool=false) const
	Compute the (signed) area of the polygon.
double	Length () const
	Compute the perimeter of the polygon.
Vector2	Centroid () const
	Compute the centroid of the polygon.
Vector2	Center () const
	Compute the barycenter of the polygon.
void	Subdivide (int, QVector< Vector2 > &, QVector< int > &) const
	Create an n-adic subdivision of a polygon.
void	Expand (const double &)
	Expand the polygon by a given distance.
QPolygonF	GetQt () const
	Convert the rectangle into a Qt polygon.
void	Draw (QGraphicsScene &, const QPen &=QPen(), const QBrush &=QBrush()) const
	Draw a polygon.
Polygon2	Resampled (const double &) const
	Resample the edges of the polygon.
Polygon2	Collapsed (const double &) const
	Remove the edges of the polygon whose length is below a given distance threshold.
QVector< Vector2 >	Poisson (const double &, int, bool=false, Random &=Random::R239) const
	Compute a Poisson sphere distribution inside a polygon.
Vector2	RandomInside (Random &=Random::R239) const
	Generate a random vector inside the box.
Vector2	RandomOn (Random &=Random::R239) const
	Generate a random vector on the edge of the polygon.
QVector< int >	EarClip () const
	Compute a simple polygon triangulation using a ear clipping method.
void	RemoveColinear (const double &=1e-12)
	Remove colinear points from the polygon.

Static Public Member Functions
static bool	Inside (const QVector< Polygon2 > &, const Vector2 &)
	Test if a point is inside the union of a set of polygons.
static double	R (const QVector< Polygon2 > &, const Vector2 &)
	Compute the squared distance between a point and a set of polygons.

Protected Member Functions
double	RC (const Vector2 &) const
	Compute the squared distance between a point and the contour of the polygon.

Protected Attributes
QVector< Vector2 >	q
	Array of vertices.

Friends
std::ostream &	operator<< (std::ostream &s, const Polygon2 &p)
	Overloaded stream operator.

Detailed Description

Polygons in the plane.

The class provides range-based for loops.

Note that polygons can be non-convex or even self intersecting.

Constructor & Destructor Documentation

Polygon2() [1/15]

Polygon2::Polygon2 ( const Vector2 & a, const Vector2 & b, const Vector2 & c )

explicit

Create a triangle.

Parameters

a,b,c

Points.

Polygon2() [2/15]

Polygon2::Polygon2 ( const Vector2 & a, const Vector2 & b, const Vector2 & c, const Vector2 & d )

explicit

Create a quadrangle.

Parameters

a,b,c,d

Points.

Polygon2() [3/15]

Polygon2::Polygon2 ( const QVector< Vector > & p )

explicit

Create a polygon.

Parameters

p	Array of points.

Polygon2() [4/15]

Polygon2::Polygon2

(

const QVector< Vector2 > &

p

)

Create a polygon.

Parameters

p	Array of points.

Polygon2() [5/15]

Polygon2::Polygon2 ( const QVector< Vector2 > & p, const QVector< int > & indexes )

explicit

Create a polygon.

Parameters

p	Array of points.

Create a polygon from a set of vertexes and a subset of indexes.

Parameters

p	Array of points.
indexes	Set of indexes.

Polygon2() [6/15]

Polygon2::Polygon2 ( const Triangle2 & t )

explicit

Create a triangle.

Parameters

t

Triangle.

Polygon2() [7/15]

Polygon2::Polygon2 ( const Box2 & box )

explicit

Create a polygon from a box.

See also

Polygon2(const Hexagon2&)

Parameters

box

The box.

Polygon2() [8/15]

Polygon2::Polygon2 ( const Hexagon2 & hexagon )

explicit

Create a hexagon.

See also

Polygon2(const Box2&)

Parameters

hexagon

Hexagon.

Polygon2() [9/15]

Polygon2::Polygon2 ( const Pentagon2 & pentagon )

explicit

Create a pentagon.

See also

Polygon2(const Box2&)

Parameters

pentagon

Pentagon.

Polygon2() [10/15]

Polygon2::Polygon2 ( const Quadrangle2 & quadrangle )

explicit

Create a quadrangle.

See also

Polygon2(const Box2&)

Parameters

quadrangle

Quadrangle.

Polygon2() [11/15]

Polygon2::Polygon2 ( const Polygonal & p )

explicit

Create a planar polygon for a polygon.

Parameters

p	Array of points.

Polygon2() [12/15]

Polygon2::Polygon2 ( const Octogon2 & octogon )

explicit

Create an octogon.

See also

Polygon2(const Box2&)

Parameters

octogon

Octogon.

Polygon2() [13/15]

Polygon2::Polygon2 ( const IrregularOctogon2 & octogon )

explicit

Create an irregular octogon.

See also

Polygon2(const Box2&)

Parameters

octogon

Irregular octogon.

Polygon2() [14/15]

Polygon2::Polygon2 ( const Ellipse2 & e, int n = 72 )

explicit

Create a polygon approximation of an ellipse.

Parameters

e	Ellipse.
n	Discretization.

Polygon2() [15/15]

Polygon2::Polygon2 ( const Circle2 & c, int n = 72 )

explicit

Create a polygon approximation of an circle.

Parameters

c	Circle.
n	Discretization.

Member Function Documentation

Append() [1/2]

void Polygon2::Append ( const Vector2 & p )

inline

Add a vertex to the polygon.

Parameters

p

Point.

Append() [2/2]

void Polygon2::Append ( const Vector2 & p, int id )

inline

Add a vertex at the given id to the polygon.

Parameters

p	Point.
id	Id.

Area()

double Polygon2::Area

(

bool

s = false

)

const

Compute the (signed) area of the polygon.

The signed area can be computed by using:

Polygon2 p;
double a = p.Area(true); // Signed area

Parameters

s	Signed flag, set to false by default.

Center()

Vector2 Polygon2::Center

(

)

const

Compute the barycenter of the polygon.

Note that the barycenter is not the same as the centroid.

See also

Centroid

Centroid()

Vector2 Polygon2::Centroid

(

)

const

Compute the centroid of the polygon.

Note that the centroid is not the same as the barycenter.

See also

Barycenter

Collapsed()

Polygon2 Polygon2::Collapsed

(

const double &

e

)

const

Remove the edges of the polygon whose length is below a given distance threshold.

Parameters

e	Distance theshold.

Cut()

bool Polygon2::Cut	(	const Line2 &	line,
		const Vector2 &	insidePoint )

Cut the polygon by a line.

This function updates the polygon and returns true if intersection occured. Since the cutting can result in multiple polygons, the resulting polygon contains the point insidePoint.

Parameters

line	The line.
insidePoint	The point that is contained in the resulting polygon.

Draw()

void Polygon2::Draw	(	QGraphicsScene &	scene,
		const QPen &	pen = QPen(),
		const QBrush &	brush = QBrush() ) const

Draw a polygon.

Parameters

scene	Graphics scene.
pen	The pen.
brush	The brush.

EarClip()

QVector< int > Polygon2::EarClip

(

)

const

Compute a simple polygon triangulation using a ear clipping method.

The vertices of the polygon need to be given in trigonometric order. Moreover, this method doesn't work with auto-intersecting polygons (including polygons where one point lies on one other segment).

Returns

Indices triplet which define triangles.

Edge()

Vector2 Polygon2::Edge ( int i ) const

inline

Return the i-th edge, starting from the i-th vertex.

Parameters

i

Index.

Expand()

void Polygon2::Expand

(

const double &

e

)

Expand the polygon by a given distance.

Parameters

e	Expansion factor.

GetBox()

Box2 Polygon2::GetBox

(

)

const

Compute the bounding box of the polygon.

The polygon should have some vertices, otherwise the result is undefined.

GetOrientedBox()

OrientedBox2 Polygon2::GetOrientedBox

(

)

const

Compute the oriented bounding box of the polygon.

The best method is to rotating calipers algorithm that needs to compute the convex hull of the polygon.

Recall that the smallest-area enclosing rectangle of a polygon has a side collinear with one of the edges of its convex hull. To avoid the computation of the convex hull, we try the all the edges of the polygon, which is faster for medium sized polyons.

Hausdorff()

double Polygon2::Hausdorff	(	const Polygon2 &	polygon,
		bool	directed = false ) const

Compute the Hausdorff distance between two polygons.

Parameters

polygon	The second polygon.
directed	Directed distance flag, set to true to compute the directed Hausdorff distance, false to compute the (symmetrized) maximum of directed Hausdorff distances.

Note that the symmetrized Hausdorff distance is internally implemented as:

Polygon2 a,b;
double d=a.Hausdorff(b,true)+b.Hausdorff(a,true);

Inside() [1/2]

bool Polygon2::Inside ( const QVector< Polygon2 > & s, const Vector2 & p )

static

Test if a point is inside the union of a set of polygons.

Polygons should be non-intersecting. Polygons inside others will be considered as holes.

Parameters

s	Set of polygons.
p	Point.

Inside() [2/2]

bool Polygon2::Inside

(

const Vector2 &

p

)

const

Check if a point is inside or outside of the polygon.

Parameters

p

Point.

Intersect() [1/3]

bool Polygon2::Intersect

(

const Circle2 &

c

)

const

Check the intersection between the boundaty of the polygon and a circle.

Compute the signed distance between the center and the polygon.

See also

Polygon2::Signed(const Vector2&) const

Parameters

c	The circle.

Intersect() [2/3]

bool Polygon2::Intersect

(

const Segment2 &

s

)

const

Test if a segment intersects the polygon.

Parameters

s

Segment.

Intersect() [3/3]

bool Polygon2::Intersect

(

const Triangle2 &

t

)

const

Test if a triangle intersects the polygon.

Parameters

t	Triangle2.

NormalAtLength()

Vector2 Polygon2::NormalAtLength

(

const double &

length

)

const

Return the normal at the position of the point on the polygon.

Parameters

length

Perimeter length from the starting point.

PointAtLength()

Vector2 Polygon2::PointAtLength

(

const double &

length

)

const

Return the position of the point on the polygon at a given length from the starting point.

Parameters

length

Distance on the perimeter of the polygon. It should be less than the perimeter of the polygon, still a modulo operation is performed inside.

Poisson()

QVector< Vector2 > Polygon2::Poisson	(	const double &	ra,
		int	n,
		bool	border = false,
		Random &	random = Random::R239 ) const

Compute a Poisson sphere distribution inside a polygon.

This function uses a simple \(O(n^3)\) dart throwing algorithm.

See also

Box2::Poisson

Parameters

ra	Radius of the sphere.
n	Number of candidate points.
border	True to add vertexes of the polygon into the set (if possible).
random	Random number generator.

R() [1/3]

double Polygon2::R

(

const Line2 &

line

)

const

Compute the distance from a polygon to a line.

Parameters

line

Line.

R() [2/3]

double Polygon2::R ( const QVector< Polygon2 > & s, const Vector2 & p )

static

Compute the squared distance between a point and a set of polygons.

Parameters

p	Point.
s	Set of polygons.

R() [3/3]

double Polygon2::R

(

const Vector2 &

p

)

const

Compute the squared distance between a point and a polygon.

Parameters

p

Point.

RandomInside()

Vector2 Polygon2::RandomInside

(

Random &

random = Random::R239

)

const

Generate a random vector inside the box.

Parameters

random

Random number generator.

RandomOn()

Vector2 Polygon2::RandomOn

(

Random &

random = Random::R239

)

const

Generate a random vector on the edge of the polygon.

Parameters

random

Random number generator.

RC()

double Polygon2::RC ( const Vector2 & p ) const

protected

Compute the squared distance between a point and the contour of the polygon.

Parameters

p

Point.

RemoveColinear()

void Polygon2::RemoveColinear

(

const double &

epsilon = 1e-12

)

Remove colinear points from the polygon.

Parameters

epsilon

Colinearity threshold, set to 1e-12 by default.

Resampled()

Polygon2 Polygon2::Resampled

(

const double &

e

)

const

Resample the edges of the polygon.

Generate points separated by a maximal given input distance.

Parameters

e

Distance.

Rotate()

void Polygon2::Rotate

(

const Matrix2 &

r

)

Rotate the polygon.

Parameters

r	Rotation matrix.

Rotated() [1/2]

Polygon2 Polygon2::Rotated

(

const double &

a

)

const

Rotate the polygon.

Parameters

a

Angle.

Rotated() [2/2]

Polygon2 Polygon2::Rotated

(

const Matrix2 &

r

)

const

Rotate the polygon.

Parameters

r	Rotation matrix.

Scale()

void Polygon2::Scale

(

const double &

s

)

Scale the polygon by a given factor.

Parameters

s	Scaling factor.

Scaled() [1/2]

Polygon2 Polygon2::Scaled

(

const double &

s

)

const

Return the scaled polygon.

Parameters

s

Scale.

Scaled() [2/2]

Polygon2 Polygon2::Scaled

(

const Vector2 &

s

)

const

Return the scaled polygon.

Parameters

s	Scaling vector.

Signed()

double Polygon2::Signed

(

const Vector2 &

p

)

const

Compute the signed distance between a point and a polygon.

Parameters

p

Point.

Subdivide()

void Polygon2::Subdivide	(	int	n,
		QVector< Vector2 > &	vertex,
		QVector< int > &	index ) const

Create an n-adic subdivision of a polygon.

Note that the polygon should be star-shaped.

This function first computes the barycenter of the polygon and uses it to create triangles which are subdivided.

Parameters

n	Subdivision level.
vertex	Array of points.
index	Array of indexes defining the triangles.

Transformed() [1/2]

Polygon2 Polygon2::Transformed

(

const Frame2 &

f

)

const

Trasform the polygon.

Parameters

f

Frame.

Transformed() [2/2]

Polygon2 Polygon2::Transformed

(

const FrameScaled2 &

f

)

const

Trasform the polygon.

Parameters

f

Frame.

Translate()

void Polygon2::Translate

(

const Vector2 &

t

)

Translate the polygon by a given vector.

Parameters

t

Vector.

Translated()

Polygon2 Polygon2::Translated

(

const Vector2 &

t

)

const

Translate the polygon by a given vector.

Parameters

t

Vector.

Vertex() [1/2]

Vector2 & Polygon2::Vertex ( int i )

inline

Read write access to the i-th point.

Parameters

i

Index.

Vertex() [2/2]

Vector2 Polygon2::Vertex ( int i ) const

inline

Read only access to the i-th point.

Parameters

i

Index.

Where()

int Polygon2::Where

(

const Circle2 &

c

)

const

Check the position of a circle againts the polygon.

Returns

0 if the circle intersects the boundary of the polygon, -1 if strictly inside, +1 if strictly outside.

See also

Polygon2::Signed(const Vector2&) const

Parameters

c	The circle.

Friends And Related Symbol Documentation

operator<<

std::ostream & operator<< ( std::ostream & s, const Polygon2 & p )

friend

Overloaded stream operator.

Parameters

s	Stream.
p	Polygon.