Core 1.0
Convex2 Class Reference

Convex polygons in the plane. More...

#include <convex.h>

Inheritance diagram for Convex2:
Polygon2

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 Vector2 &, const Vector2 &, const Vector2 &, const Vector2 &)
 Create a convex polygon from four 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 distance vector between a convex polygon and a point.
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 MinkowskiSlow (const Convex2 &) const
 Straightforward implementation of the Minkowski sum of two convex.
Convex2 Minkowski (const Convex2 &) const
 Minkowski sum of two convex polygons, computed in linear time.
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 from a set of vertexes and a subset of indexes.
 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.
Vector2 & operator[] (int)
 Access to the i-th vertex.
Vector2 operator[] (int) const
 Read only access to the i-th vertex.
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 Empty () const
 Check if the polygon has no vertex.
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 squared distance between the polygon and a line (0 if the line crosses the polygon).
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 Perimeter () 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 if 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/12]

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
qArray of points defining the polygon (should be convex).

◆ Convex2() [2/12]

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

Create a convex polygon from three points.

Parameters
a,b,cPoints (should be in trigonometric ordrer).

◆ Convex2() [3/12]

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

Create a convex polygon from four points.

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

◆ Convex2() [4/12]

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
qArray of points defining the polygon (should be convex).

◆ Convex2() [5/12]

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

Create a convex polygon.

Parameters
qArray of points defining the polygon (should be convex).

◆ Convex2() [6/12]

Convex2::Convex2 ( const Box2 & b)

Create a convex from a box.

Parameters
bThe box.

◆ Convex2() [7/12]

Convex2::Convex2 ( const Hexagon2 & h)

Create a convex from a hexagon.

Parameters
hThe hexagon.

◆ Convex2() [8/12]

Convex2::Convex2 ( const Triangle2 & t)

Create a convex from a triangle.

Parameters
tThe triangle.

◆ Convex2() [9/12]

Convex2::Convex2 ( const Quadrangle2 & q)

Create a convex from a quadrangle.

Parameters
qThe quadrangle.

◆ Convex2() [10/12]

Convex2::Convex2 ( const Pentagon2 & p)

Create a convex from a hexagon.

Parameters
pThe pentagon.

◆ Convex2() [11/12]

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

Create a convex from an ellipse.

Parameters
eThe ellipse.
nNumber of vertices.

◆ Convex2() [12/12]

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

Create a convex from an ellipse.

Parameters
cThe circle.
nNumber 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
sThe segment.

◆ AxisInterval()

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

Project a the vertexes of the convex onto an axis.

Parameters
uAxis.

◆ 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
lineThe line.

◆ Hull()

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

Create the convex hull of a set of points.

The hull is computed with Andrew's monotone chain algorithm. Its vertices are in trigonometric order, the points which are in the interior of an edge of the hull, and the duplicate points, are not vertices. The hull of one point, or of two distinct points, is the polygon made of these points.

Parameters
pSet of points.

◆ Inside() [1/2]

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

Test if a convex is inside another one.

Parameters
convexThe convex polygon.

◆ Inside() [2/2]

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

Test if a point is inside the convex.

Parameters
pThe point.

◆ Intersect() [1/3]

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

Check the intersection between a convex and a box.

Parameters
bThe box.

◆ Intersect() [2/3]

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

Check the intersection between a convex and a circle.

The circle is the disc, so that a circle contained in the convex intersects it. We compute the distance between the center of the circle and the convex, which is null if the center is inside the convex: if it is greater than the radius, then there is no intersection.

Parameters
cThe circle.

◆ Intersect() [3/3]

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

Test if two convex intersect.

Parameters
cConvex.

◆ 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
clipClipping convex.
cutReturned convex intersection.

◆ Intersection() [2/2]

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

Test if two convex intersect.

Parameters
cConvex.
pReturn set of intersection points.
See also
bool Convex2::Intersection(const Convex2&, Convex2&) const

◆ Minkowski()

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

Minkowski sum of two convex polygons, computed in linear time.

The edges of the two polygons, sorted by polar angle, are merged: the vertexes of the sum are obtained by following these edges, starting from the sum of the lowest vertexes of the polygons, that is, the vertexes with the smallest y coordinate, and with the smallest x coordinate in case of equality. The complexity is \( O(n+m) \) for polygons with n and m vertexes, instead of \( O(nm\log(nm)) \) for MinkowskiSlow().

The polygons may be oriented clockwise or counterclockwise. Parallel edges are merged, and the vertexes in the interior of an edge are not kept. The sum is counterclockwise, and starts with the lowest vertex. If one of the polygons has less than three vertexes (a point or a segment), MinkowskiSlow() is used. If one of the polygons is empty, the sum is empty.

The sum is strictly convex if the polygons are strictly convex at the working precision. The function does not filter the vertexes: if the polygons have turning angles smaller than the rounding errors on their coordinates, for example if their size is much smaller than the distance to the origin (by a factor of about 1e8), the sum may keep nearly aligned vertexes.

See also
MinkowskiSlow(const Convex2&) const
Parameters
cConvex.

◆ MinkowskiSlow()

Convex2 Convex2::MinkowskiSlow ( const Convex2 & c) const

Straightforward implementation of the Minkowski sum of two convex.

Parameters
cConvex.

◆ Normal()

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

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

The vector goes from the closest point of the polygon to the point, so that the projection of the point on the polygon is p-Normal(p). It is null if the point is inside the polygon.

The function is computed in a single pass over the edges. A point is outside the polygon if, and only if, it lies on the outer side of at least one edge, and the closest point of the polygon is then on one of these edges. The projection on the edge, clamped to the end points of the edge, is therefore only computed for these edges, and no projection is computed when the point is inside. The cost of the function is linear in the number of vertices.

A polygon with less than three vertices (a point or a segment) has no interior: the distance vector to the point or to the segment is returned.

Parameters
pPoint.

◆ Overlap()

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

Test if two convex overlap.

Parameters
otherThe second convex.

◆ R()

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

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

Parameters
pPoint.

◆ 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
rRotation matrix.

◆ Scaled() [1/2]

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

Return the scaled polygon.

Parameters
sScaling factor.

◆ Scaled() [2/2]

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

Return the scaled polygon.

Parameters
sScaling vector.

◆ Signed()

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

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

The distance is negative inside the polygon, which should be counterclockwise.

Parameters
pPoint.

◆ TestAxes()

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

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

Parameters
otherThe second convex.

◆ Transformed() [1/2]

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

Trasform the convex.

Parameters
fFrame.

◆ Transformed() [2/2]

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

Trasform the convex.

Parameters
fFrame.

◆ Translated()

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

Translate the polygon by a given vector.

Parameters
tVector.

◆ VoronoiCell()

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

Create one Voronoi cell.

Parameters
qSet of points.
pPoint.
boxBox 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
qSet of points.
boxBox 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
dPositive half space direction.
pPoint.
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.