RobWorkProject
24.5.15

Utility functions for operations on polygons, such as convex partitioning. More...
Classes  
class  PolygonUtil 
Utility functions for operations on polygons, such as convex partitioning. More...  
Namespaces  
rw  
Deprecated namespace since 16/42020 for this class.  
rw::geometry  
Loading and storing of CAD models.  
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/LiliSangYunjunLiu/project/MAIN3.htm
[3] On the time bound for convex decomposition of simple polygons. Mark Keil & Jack Snoeyink.