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:

• PolygonUtil.hpp