|
Core 1.0
|
Convex polygons in the plane. More...
#include <convex.h>
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. | |
Convex polygons in the plane.
Drawing member function is inherited from Polygon2::Draw() const.
|
explicit |
Create a convex polygon.
Note that convexity is not checked. See Convex2::Hull to compute the convex hull of a set of points.
| q | Array of points defining the polygon (should be convex). |
Create a convex polygon from three points.
| a,b,c | Points (should be in trigonometric ordrer). |
|
explicit |
Create a convex polygon from four points.
| a,b,c,d | Points (should be in trigonometric ordrer). |
|
explicit |
Create a convex polygon.
Note that convexity is not checked. See Convex2::Hull to compute the convex hull of a set of points.
| q | Array of points defining the polygon (should be convex). |
|
explicit |
Create a convex polygon.
| q | Array of points defining the polygon (should be convex). |
| Convex2::Convex2 | ( | const Box2 & | b | ) |
Create a convex from a box.
| b | The box. |
| Convex2::Convex2 | ( | const Hexagon2 & | h | ) |
Create a convex from a hexagon.
| h | The hexagon. |
| Convex2::Convex2 | ( | const Triangle2 & | t | ) |
Create a convex from a triangle.
| t | The triangle. |
| Convex2::Convex2 | ( | const Quadrangle2 & | q | ) |
Create a convex from a quadrangle.
| q | The quadrangle. |
| Convex2::Convex2 | ( | const Pentagon2 & | p | ) |
Create a convex from a hexagon.
| p | The pentagon. |
| Convex2::Convex2 | ( | const Ellipse2 & | e, |
| int | n ) |
Create a convex from an ellipse.
| e | The ellipse. |
| n | Number of vertices. |
| Convex2::Convex2 | ( | const Circle2 & | c, |
| int | n ) |
Create a convex from an ellipse.
| c | The circle. |
| n | Number of vertices. |
| 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.
| s | The segment. |
Project a the vertexes of the convex onto an axis.
| u | Axis. |
| 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.
| line | The line. |
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.
| p | Set of points. |
| bool Convex2::Inside | ( | const Convex2 & | convex | ) | const |
Test if a convex is inside another one.
| convex | The convex polygon. |
| bool Convex2::Inside | ( | const Vector2 & | p | ) | const |
Test if a point is inside the convex.
| p | The point. |
| bool Convex2::Intersect | ( | const Box2 & | b | ) | const |
Check the intersection between a convex and a box.
| b | The box. |
| 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.
| c | The circle. |
| bool Convex2::Intersect | ( | const Convex2 & | c | ) | const |
Test if two convex intersect.
| c | Convex. |
Check if two polygons intersect, return the convex intersection if they do.
| clip | Clipping convex. |
| cut | Returned convex intersection. |
Test if two convex intersect.
| c | Convex. |
| p | Return set of intersection points. |
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.
| c | Convex. |
Straightforward implementation of the Minkowski sum of two convex.
| c | Convex. |
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.
| p | Point. |
| bool Convex2::Overlap | ( | const Convex2 & | other | ) | const |
Test if two convex overlap.
| other | The second convex. |
| double Convex2::R | ( | const Vector2 & | p | ) | const |
Compute the squared distance between a point and a convex polygon.
| p | Point. |
| double Convex2::Radius | ( | ) | const |
Return the radius of the convex polygon.
It is defined as the half of the maximum distance between two vertices.
Rotate the polygon.
| r | Rotation matrix. |
| Convex2 Convex2::Scaled | ( | const double & | s | ) | const |
Return the scaled polygon.
| s | Scaling factor. |
Return the scaled polygon.
| s | Scaling vector. |
| 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.
| p | Point. |
|
protected |
Test if the axes of the first convex is a separating axis.
| other | The second convex. |
| Convex2 Convex2::Transformed | ( | const FrameScaled2 & | f | ) | const |
Trasform the convex.
| f | Frame. |
Translate the polygon by a given vector.
| t | Vector. |
|
static |
Create one Voronoi cell.
| q | Set of points. |
| p | Point. |
| box | Box embedding the set of points. |
Create the Voronoi cells from a given set of points.
| q | Set of points. |
| box | Box embedding the set of points. |
Test on which side lie the vertices of the convex polygon.
| d | Positive half space direction. |
| p | Point. |