Aleph::ConvexPolygonDecomposition Class Reference

Decompose a simple polygon into convex parts using Hertel-Mehlhorn. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::ConvexPolygonDecomposition:

Public Member Functions
Array< Polygon >	operator() (const Polygon &poly) const
	Decompose polygon poly into convex parts.

Static Private Member Functions
static size_t	find_pos (const Array< size_t > &face, size_t v)
static bool	is_polygon_edge (size_t u, size_t v, size_t n)
static bool	can_merge (const Array< Point > &pts, const Array< size_t > &f1, const Array< size_t > &f2, size_t u, size_t v)
	Check whether merging faces f1 and f2 across diagonal (u,v) is convex.
static Array< size_t >	merge_faces (const Array< size_t > &f1, const Array< size_t > &f2, size_t u, size_t v)
	Merge f1 and f2 by removing their shared edge (u,v).
static Array< Point >	extract_vertices (const Polygon &p)

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

Decompose a simple polygon into convex parts using Hertel-Mehlhorn.

The algorithm triangulates the polygon, then greedily removes internal diagonals whose removal keeps the merged region convex.

Algorithm

1. Triangulate the polygon (via MonotonePolygonTriangulation).
2. For each internal diagonal shared by two convex faces, check whether removing it (merging the two faces) preserves convexity.
3. Remove all such diagonals greedily.

Complexity

• Time: O(n log n) for triangulation + O(n²) for merging = O(n²)
• Space: O(n)
• The output has at most 4× the optimal number of convex parts.

Example

Polygon poly;
poly.add_vertex(Point(0,0)); poly.add_vertex(Point(4,0));
poly.add_vertex(Point(4,1)); poly.add_vertex(Point(1,1));
poly.add_vertex(Point(1,4)); poly.add_vertex(Point(0,4));
poly.close();
ConvexPolygonDecomposition dec;
auto parts = dec(poly);

Definition at line 8311 of file geom_algorithms.H.

Member Function Documentation

can_merge()

static bool Aleph::ConvexPolygonDecomposition::can_merge ( const Array< Point > &  pts, const Array< size_t > &  f1, const Array< size_t > &  f2, size_t  u, size_t  v  )

inlinestaticprivate

Check whether merging faces f1 and f2 across diagonal (u,v) is convex.

Definition at line 8335 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CW, find_pos(), Aleph::orientation(), and Aleph::Array< T >::size().

Referenced by operator()().

extract_vertices()

static Array< Point > Aleph::ConvexPolygonDecomposition::extract_vertices ( const Polygon &  p )

inlinestaticprivate

Definition at line 8410 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by operator()().

find_pos()

static size_t Aleph::ConvexPolygonDecomposition::find_pos ( const Array< size_t > &  face, size_t  v  )

inlinestaticprivate

Definition at line 8315 of file geom_algorithms.H.

References NONE, and Aleph::Array< T >::size().

Referenced by can_merge(), merge_faces(), and operator()().

is_polygon_edge()

static bool Aleph::ConvexPolygonDecomposition::is_polygon_edge ( size_t  u, size_t  v, size_t  n  )

inlinestaticprivate

Definition at line 8323 of file geom_algorithms.H.

References Aleph::and, and Aleph::blossom_maximum_cardinality_matching().

Referenced by operator()().

merge_faces()

static Array< size_t > Aleph::ConvexPolygonDecomposition::merge_faces ( const Array< size_t > &  f1, const Array< size_t > &  f2, size_t  u, size_t  v  )

inlinestaticprivate

Merge f1 and f2 by removing their shared edge (u,v).

Definition at line 8375 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), find_pos(), k, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by operator()().

operator()()

Array< Polygon > Aleph::ConvexPolygonDecomposition::operator() ( const Polygon &  poly ) const

inline

Decompose polygon poly into convex parts.

Parameters

poly	A closed simple polygon with ≥ 3 vertices.

Returns

Array of closed convex polygons partitioning the input.

Definition at line 8422 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), can_merge(), Aleph::Polygon::close(), Aleph::CW, extract_vertices(), find_pos(), Aleph::Triangle::get_p1(), Aleph::Triangle::get_p2(), Aleph::Triangle::get_p3(), Aleph::HTList::Iterator::has_curr(), Aleph::Polygon::is_closed(), is_polygon_edge(), k, merge_faces(), NONE, Aleph::orientation(), Aleph::Array< T >::reserve(), Aleph::Polygon::size(), and Aleph::Array< T >::size().

Member Data Documentation

NONE

constexpr size_t Aleph::ConvexPolygonDecomposition::NONE = ~static_cast<size_t>(0)

staticconstexprprivate

Definition at line 8313 of file geom_algorithms.H.

Referenced by find_pos(), and operator()().

---

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

• geom_algorithms.H