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.