RobWorkProject  24.5.15-
Classes | Namespaces
PolygonUtil.hpp File Reference

Utility functions for operations on polygons, such as convex partitioning. More...

#include <rw/geometry/Polygon.hpp>
#include <rw/math/Vector2D.hpp>

Classes

class  PolygonUtil
 Utility functions for operations on polygons, such as convex partitioning. More...
 

Namespaces

 rw
 Deprecated namespace since 16/4-2020 for this class.
 
 rw::geometry
 Loading and storing of CAD models.
 

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.