RobWorkProject
24.8.23-
|
Utility functions for operations on polygons, such as convex partitioning. More...
#include <PolygonUtil.hpp>
Static Public Member Functions | |
static std::vector< std::vector< std::size_t > > | convexDecompositionIndexed (const Polygon< rw::math::Vector2D<>> &polygon) |
Convex decomposition of a polygon. More... | |
static std::vector< Polygon< rw::math::Vector2D<> > > | convexDecomposition (const Polygon< rw::math::Vector2D<>> &polygon) |
Convex decomposition of a polygon. More... | |
static bool | isInsideConvex (const rw::math::Vector2D<> &point, const Polygon< rw::math::Vector2D<>> &polygon, double eps) |
Check if point lies inside convex polygon. More... | |
static double | area (const Polygon< rw::math::Vector2D<>> &polygon) |
Get the signed area of a 2D polygon. More... | |
Utility functions for operations on polygons, such as convex partitioning.
The algorithm for convex partitioning of polygons has time complexity \( O(n r^2 \log r) \) where n is the number of vertices and r is the number of reflex vertices (vertices that gives an inward notch). The algorithm is due to J. Mark Keil [1]. For more information, see also [2] and [3]. The polygons must not contain holes, and no new vertices are introduced (no Steiner points).
[1] Minimum Decompostions of Polygonal Objects. J. Mark Keil. 1985.
[2] http://cgm.cs.mcgill.ca/~athens/cs644/Projects/2004/LiliSang-YunjunLiu/project/MAIN3.htm
[3] On the time bound for convex decomposition of simple polygons. Mark Keil & Jack Snoeyink.
|
static |
Get the signed area of a 2D polygon.
polygon | [in] the polygon to find area of. |
|
static |
Convex decomposition of a polygon.
polygon | [in] the polygon to decompose into convex subpolygons. |
|
static |
Convex decomposition of a polygon.
polygon | [in] the polygon to decompose into convex subpolygons. |
|
static |
Check if point lies inside convex polygon.
point | [in] the point. |
polygon | [in] the polygon. |
eps | [in] distance threshold for when to consider a point inside the polygon. |