RobWorkProject  22.2.21-
Static Public Member Functions | List of all members
PolygonUtil Class Reference

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...
 

Detailed Description

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.

  1. 10th Canadian Conference on Computational Geometry, Aug 1998. See http://www.cs.ubc.ca/~snoeyink/convdecomp for full version paper.

Member Function Documentation

◆ area()

static double area ( const Polygon< rw::math::Vector2D<> > &  polygon)
static

Get the signed area of a 2D polygon.

Parameters
polygon[in] the polygon to find area of.
Returns
area of the polygon, with negative sign if vertices are given clockwise, or positive sign if given counter-clockwise.

◆ convexDecomposition()

static std::vector< Polygon< rw::math::Vector2D<> > > convexDecomposition ( const Polygon< rw::math::Vector2D<> > &  polygon)
static

Convex decomposition of a polygon.

Parameters
polygon[in] the polygon to decompose into convex subpolygons.
Returns
a vector of convex polygons.

◆ convexDecompositionIndexed()

static std::vector< std::vector< std::size_t > > convexDecompositionIndexed ( const Polygon< rw::math::Vector2D<> > &  polygon)
static

Convex decomposition of a polygon.

Parameters
polygon[in] the polygon to decompose into convex subpolygons.
Returns
a vector of indexed polygons. Each indexed polygon is returned as an ordered vector of indices.

◆ isInsideConvex()

static bool isInsideConvex ( const rw::math::Vector2D<> &  point,
const Polygon< rw::math::Vector2D<> > &  polygon,
double  eps 
)
static

Check if point lies inside convex polygon.

Parameters
point[in] the point.
polygon[in] the polygon.
eps[in] distance threshold for when to consider a point inside the polygon.
Returns
true if point is strictly inside the polygon, or false if on the border or outside.

The documentation for this class was generated from the following file: