Convex polygons in the plane. More...

#include <convex.h>

Inheritance diagram for Convex2:

Public Member Functions
	Convex2 ()
	Empty.
	Convex2 (const Polygon2 &)
	Create a convex polygon.
	Convex2 (const Vector2 &, const Vector2 &, const Vector2 &)
	Create a convex polygon from three points.
	Convex2 (const QVector< Vector > &)
	Create a convex polygon.
	Convex2 (const QVector< Vector2 > &)
	Create a convex polygon.
	Convex2 (const Box2 &)
	Create a convex from a box.
	Convex2 (const Hexagon2 &)
	Create a convex from a hexagon.
	Convex2 (const Triangle2 &)
	Create a convex from a triangle.
	Convex2 (const Quadrangle2 &)
	Create a convex from a quadrangle.
	Convex2 (const Pentagon2 &)
	Create a convex from a hexagon.
	Convex2 (const Ellipse2 &, int)
	Create a convex from an ellipse.
	Convex2 (const Circle2 &, int)
	Create a convex from an ellipse.
	~Convex2 ()
	Empty.
double	Radius () const
	Return the radius of the convex polygon.
bool	Cut (const Line2 &)
	Cut the convex polygon by a line.
bool	AddIntersection (const Segment2 &)
	Check the intersection between the convex and a segment, if intersection occurs, add the points to the convex.
double	R (const Vector2 &) const
	Compute the squared distance between a point and a convex polygon.
double	Signed (const Vector2 &) const
	Compute the signed Euclidean distance between a point and a convex polygon.
Vector2	Normal (const Vector2 &) const
	Compute the normal vector between a point and a convex polygon.
bool	Inside (const Convex2 &) const
	Test if a convex is inside another one.
bool	Inside (const Vector2 &) const
	Test if a point is inside the convex.
Convex2	Scaled (const double &) const
	Return the scaled polygon.
Convex2	Scaled (const Vector2 &) const
	Return the scaled polygon.
Convex2	Translated (const Vector2 &) const
	Translate the polygon by a given vector.
Convex2	Rotated (const Matrix2 &) const
	Rotate the polygon.
Convex2	Transformed (const FrameScaled2 &) const
	Trasform the convex.
Convex2	Transformed (const Frame2 &) const
	Trasform the convex.
bool	Intersect (const Convex2 &) const
	Test if two convex intersect.
bool	Intersect (const Box2 &) const
	Check the intersection between a convex and a box.
bool	Intersect (const Circle2 &) const
	Check the intersection between a convex and a circle.
bool	Intersection (const Convex2 &, QVector< Vector2 > &) const
	Test if two convex intersect.
bool	Intersection (const Convex2 &, Convex2 &) const
	Check if two polygons intersect, return the convex intersection if they do.
Ia	AxisInterval (const Vector2 &) const
	Project a the vertexes of the convex onto an axis.
Convex2	Minkowski (const Convex2 &) const
	Straightforward implementation of the Minkowski sum of two convex.
bool	Overlap (const Convex2 &) const
	Test if two convex overlap.
void	Reorder ()
	Changer the order of the vertexes: the first vertex is the one with the lowest y value, and in case of tie, the one with the lowest x value.
Public Member Functions inherited from Polygon2
	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 Convex2	Hull (QVector< Vector2 >)
	Create the convex hull of a set of points.
static QVector< Convex2 >	VoronoiCells (const QVector< Vector2 > &, const Box2 &)
	Create the Voronoi cells from a given set of points.
static Convex2	VoronoiCell (const QVector< Vector2 > &, const Box2 &, const Vector2 &)
	Create one Voronoi cell.
Static Public Member Functions inherited from Polygon2
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
int	WhichSide (const Vector2 &, const Vector2 &) const
	Test on which side lie the vertices of the convex polygon.
bool	TestAxes (const Convex2 &) const
	Test the axes of the first convex is a separating axis.
Protected Member Functions inherited from Polygon2
double	RC (const Vector2 &) const
	Compute the squared distance between a point and the contour of the polygon.

Additional Inherited Members
Protected Attributes inherited from Polygon2
QVector< Vector2 >	q
	Array of vertices.

Detailed Description

Convex polygons in the plane.

Drawing member function is inherited from Polygon2::Draw() const.

Constructor & Destructor Documentation

◆ Convex2() [1/11]

Convex2::Convex2 ( const Polygon2 & q )

explicit

Create a convex polygon.

Note that convexity is not checked. See Convex2::Hull to compute the convex hull of a set of points.

Parameters

q	Array of points defining the polygon (should be convex).

◆ Convex2() [2/11]

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

explicit

Create a convex polygon from three points.

Parameters

a,b,c Points (should be in trigonometric ordrer).

◆ Convex2() [3/11]

Convex2::Convex2 ( const QVector< Vector > & q )

explicit

Create a convex polygon.

Note that convexity is not checked. See Convex2::Hull to compute the convex hull of a set of points.

Parameters

q	Array of points defining the polygon (should be convex).

◆ Convex2() [4/11]

Convex2::Convex2 ( const QVector< Vector2 > & q )

explicit

Create a convex polygon.

Parameters

q	Array of points defining the polygon (should be convex).

◆ Convex2() [5/11]

Convex2::Convex2 ( const Box2 & b )

Create a convex from a box.

Parameters

b The box.

◆ Convex2() [6/11]

Convex2::Convex2 ( const Hexagon2 & h )

Create a convex from a hexagon.

Parameters

h	The hexagon.

◆ Convex2() [7/11]

Convex2::Convex2 ( const Triangle2 & t )

Create a convex from a triangle.

Parameters

t	The triangle.

◆ Convex2() [8/11]

Convex2::Convex2 ( const Quadrangle2 & q )

Create a convex from a quadrangle.

Parameters

q	The quadrangle.

◆ Convex2() [9/11]

Convex2::Convex2 ( const Pentagon2 & p )

Create a convex from a hexagon.

Parameters

p	The pentagon.

◆ Convex2() [10/11]

Convex2::Convex2	(	const Ellipse2 &	e,
		int	n )

Create a convex from an ellipse.

Parameters

e	The ellipse.
n	Number of vertices.

◆ Convex2() [11/11]

Convex2::Convex2	(	const Circle2 &	c,
		int	n )

Create a convex from an ellipse.

Parameters

c	The circle.
n	Number of vertices.

Member Function Documentation

◆ AddIntersection()

bool Convex2::AddIntersection ( const Segment2 & s )

Check the intersection between the convex and a segment, if intersection occurs, add the points to the convex.

This function adds the points to the list of vertices of the convex polygon.

Parameters

s	The segment.

◆ AxisInterval()

Ia Convex2::AxisInterval ( const Vector2 & u ) const

Project a the vertexes of the convex onto an axis.

Parameters

u Axis.

◆ Cut()

bool Convex2::Cut ( const Line2 & line )

Cut the convex polygon by a line.

This function updates the convex polygon and returns true if intersection occured.

Parameters

line The line.

◆ Hull()

Convex2 Convex2::Hull ( QVector< Vector2 > p )

static

Create the convex hull of a set of points.

Parameters

p	Set of points.

◆ Inside() [1/2]

bool Convex2::Inside ( const Convex2 & convex ) const

Test if a convex is inside another one.

Parameters

convex The convex polygon.

◆ Inside() [2/2]

bool Convex2::Inside ( const Vector2 & p ) const

Test if a point is inside the convex.

Parameters

p	The point.

◆ Intersect() [1/3]

bool Convex2::Intersect ( const Box2 & b ) const

Check the intersection between a convex and a box.

Parameters

b The box.

◆ Intersect() [2/3]

bool Convex2::Intersect ( const Circle2 & c ) const

Check the intersection between a convex and a circle.

Compute the distance to the center of the circle: if it is greater than the radius, then there is no intersection.

Parameters

c	The circle.

◆ Intersect() [3/3]

bool Convex2::Intersect ( const Convex2 & c ) const

Test if two convex intersect.

Parameters

c Convex.

◆ Intersection() [1/2]

bool Convex2::Intersection	(	const Convex2 &	clip,
		Convex2 &	cut ) const

Check if two polygons intersect, return the convex intersection if they do.

Parameters

clip	Clipping convex.
cut	Returned convex intersection.

◆ Intersection() [2/2]

bool Convex2::Intersection	(	const Convex2 &	c,
		QVector< Vector2 > &	p ) const

Test if two convex intersect.

Parameters

c	Convex.
p	Return set of intersection points.

See also: bool Convex2::Intersection(const Convex2&, Convex2&) const

◆ Minkowski()

Convex2 Convex2::Minkowski ( const Convex2 & c ) const

Straightforward implementation of the Minkowski sum of two convex.

Parameters

c Convex.

◆ Normal()

Vector2 Convex2::Normal ( const Vector2 & p ) const

Compute the normal vector between a point and a convex polygon.

Returns null vector if the point is inside the polygon.

Parameters

p Point.

◆ Overlap()

bool Convex2::Overlap ( const Convex2 & other ) const

Test if two convex overlap.

Parameters

other The second convex.

◆ R()

double Convex2::R ( const Vector2 & p ) const

Compute the squared distance between a point and a convex polygon.

Parameters

p Point.

◆ Radius()

double Convex2::Radius ( ) const

Return the radius of the convex polygon.

It is defined as the half of the maximum distance between two vertices.

◆ Rotated()

Convex2 Convex2::Rotated ( const Matrix2 & r ) const

Rotate the polygon.

Parameters

r	Rotation matrix.

◆ Scaled() [1/2]

Convex2 Convex2::Scaled ( const double & s ) const

Return the scaled polygon.

Parameters

s	Scaling factor.

◆ Scaled() [2/2]

Convex2 Convex2::Scaled ( const Vector2 & s ) const

Return the scaled polygon.

Parameters

s	Scaling vector.

◆ Signed()

double Convex2::Signed ( const Vector2 & p ) const

Compute the signed Euclidean distance between a point and a convex polygon.

Parameters

p Point.

◆ TestAxes()

bool Convex2::TestAxes ( const Convex2 & other ) const

protected

Test the axes of the first convex is a separating axis.

Parameters

other The second convex.

◆ Transformed() [1/2]

Convex2 Convex2::Transformed ( const Frame2 & f ) const

Trasform the convex.

Parameters

f Frame.

◆ Transformed() [2/2]

Convex2 Convex2::Transformed ( const FrameScaled2 & f ) const

Trasform the convex.

Parameters

f Frame.

◆ Translated()

Convex2 Convex2::Translated ( const Vector2 & t ) const

Translate the polygon by a given vector.

Parameters

t Vector.

◆ VoronoiCell()

Convex2 Convex2::VoronoiCell	(	const QVector< Vector2 > &	q,
		const Box2 &	box,
		const Vector2 &	p )

static

Create one Voronoi cell.

Parameters

q	Set of points.
p	Point.
box	Box embedding the set of points.

◆ VoronoiCells()

QVector< Convex2 > Convex2::VoronoiCells	(	const QVector< Vector2 > &	q,
		const Box2 &	box )

static

Create the Voronoi cells from a given set of points.

Parameters

q	Set of points.
box	Box embedding the set of points.

◆ WhichSide()

int Convex2::WhichSide	(	const Vector2 &	d,
		const Vector2 &	p ) const

protected

Test on which side lie the vertices of the convex polygon.

Parameters

d	Positive half space direction.
p	Point.

Returns: A value +1 if all vertexes lie on the positive half-space side, -1 on the negative half space, and 0 otherwise, in which case the line splits the convex.

Public Member Functions

Static Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Convex2() [1/11]

◆ Convex2() [2/11]

◆ Convex2() [3/11]

◆ Convex2() [4/11]

◆ Convex2() [5/11]

◆ Convex2() [6/11]

◆ Convex2() [7/11]

◆ Convex2() [8/11]

◆ Convex2() [9/11]

◆ Convex2() [10/11]

◆ Convex2() [11/11]

Member Function Documentation

◆ AddIntersection()

◆ AxisInterval()

◆ Cut()

◆ Hull()

◆ Inside() [1/2]

◆ Inside() [2/2]

◆ Intersect() [1/3]

◆ Intersect() [2/3]

◆ Intersect() [3/3]

◆ Intersection() [1/2]

◆ Intersection() [2/2]

◆ Minkowski()

◆ Normal()

◆ Overlap()

◆ R()

◆ Radius()

◆ Rotated()

◆ Scaled() [1/2]

◆ Scaled() [2/2]

◆ Signed()

◆ TestAxes()

◆ Transformed() [1/2]

◆ Transformed() [2/2]

◆ Translated()

◆ VoronoiCell()

◆ VoronoiCells()

◆ WhichSide()