PolygonPartition Class Reference

Convex partition of polygons. More...

#include <easy3d/algo/polygon_partition.h>

Public Types
typedef std::vector< std::size_t >	Polygon
	An indexed polygon representation (defined by vertex indices).

Public Member Functions
	PolygonPartition ()=default
	Default constructor.

Static Public Member Functions
static bool	apply_OPT (const std::vector< vec2 > &poly, std::vector< Polygon > &parts)
	Optimal convex partition (in terms of number of resulting convex polygons) of a polygon into convex polygons by using the Keil-Snoeyink algorithm. More...
static bool	apply_HM (const std::vector< vec2 > &poly, std::vector< Polygon > &parts)
	Partition a polygon into convex polygons by using the Hertel-Mehlhorn algorithm. More...
static bool	apply (const std::vector< vec2 > &points, const std::vector< Polygon > &polys, const std::vector< Polygon > &holes, std::vector< Polygon > &parts)
	Convex partition of a general polygon with an arbitrary number of non-hole and hole contours. More...

Detailed Description

Convex partition of polygons.

The algorithm assumes simply polygons without self-intersections. For complex unknown structures, you may need to use the CSG operators provided in easy3d/algo/tessellator.h to obtain simply polygons first.

Member Function Documentation

apply()

bool apply ( const std::vector< vec2 > &  points, const std::vector< Polygon > &  polys, const std::vector< Polygon > &  holes, std::vector< Polygon > &  parts  )

static

Convex partition of a general polygon with an arbitrary number of non-hole and hole contours.

This function partitions a list of polygons into convex parts by using the Hertel-Mehlhorn algorithm. The algorithm gives at most four times the number of parts as the optimal algorithm. However, in practice it works much better than that and often gives optimal partition. Time complexity: O(n^2), where n is the number of vertices. Space complexity: O(n). See S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. 4th Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes Comput. Sci., pages 207–218. Springer-Verlag, 1983.

Parameters

points	A set of points.
polys	A set of non-hole polygons (each represented by the vertex indices). The vertices of all non-hole polygons have to be in counter-clockwise order.
holes	A set of holes (represented by the vertex indices). The vertices of all hole polygons have to be in clockwise order.
parts	Resulting list of convex polygons (represented by the vertex indices).

Returns

true on success, false on failure.

See also

apply_OPT, apply_HM.

apply_HM()

bool apply_HM ( const std::vector< vec2 > &  poly, std::vector< Polygon > &  parts  )

static

Partition a polygon into convex polygons by using the Hertel-Mehlhorn algorithm.

The algorithm gives at most four times the number of parts as the optimal algorithm. However, in practice it works much better than that and often gives optimal partition. Time complexity: O(n^2), where n is the number of vertices. Space complexity: O(n). See S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. 4th Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes Comput. Sci., pages 207–218. Springer-Verlag, 1983.

Parameters

poly	An input polygon (without holes). Vertices have to be in the counter-clockwise order.
parts	Resulting list of convex polygons, represented by the vertex indices.

Returns

true on success, false on failure.

See also

apply_OPT, apply.

apply_OPT()

bool apply_OPT ( const std::vector< vec2 > &  poly, std::vector< Polygon > &  parts  )

static

Optimal convex partition (in terms of number of resulting convex polygons) of a polygon into convex polygons by using the Keil-Snoeyink algorithm.

ToDo: use GenericPolygon<FT>::is_clockwise() to validate the input.

The optimal convex partition algorithm is described in M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998. Time complexity: O(n^3), where n is the number of vertices. Space complexity: O(n^3).

Parameters

poly	An input polygon (without holes). Vertices have to be in the counter-clockwise order.
parts	Resulting list of convex polygons, represented by the vertex indices.

Returns

true on success, false on failure.

See also

apply_HM, apply.

---

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

• /Users/lnan/Documents/Projects/Easy3D/easy3d/algo/polygon_partition.h
• /Users/lnan/Documents/Projects/Easy3D/easy3d/algo/polygon_partition.cpp