O(n log n) triangulation of simple polygons via y-monotone partition + linear-time monotone triangulation. More...

#include <geom_algorithms.H>

Classes
class	EdgeStatusTree

Public Member Functions
DynList< Triangle >	operator() (Polygon p) const
	Triangulate a simple polygon.

Private Types
enum class	VertexType { START , END , SPLIT , MERGE , REGULAR }
	Classification of vertices for y-monotone decomposition. More...

Static Private Member Functions
static Array< Point >	extract_vertices (const Polygon &p)

static Geom_Number	signed_double_area (const Array< Point > &v)

static void	ensure_ccw (Array< Point > &v)

static bool	is_above (const Point &a, const Point &b)
	Lexicographical "above" comparison (y primary, x secondary).

static bool	is_below (const Point &a, const Point &b)
	Lexicographical "below" comparison.

static bool	edge_goes_down (const Array< Point > &verts, const size_t edge)
	Check if the edge starting at `edge` points downwards.

static Geom_Number	edge_x_at_y (const Array< Point > &verts, const size_t edge, const Geom_Number &y)

static bool	edge_status_less (const size_t lhs, const size_t rhs, const Geom_Number &sweep_y, const Array< Point > &verts)

static DynList< Triangle >	triangulate_monotone (const Array< Point > &verts)
	Triangulate a y-monotone polygon given as a vertex array.

static VertexType	classify_vertex (const Array< Point > &v, const size_t i)

static bool	regular_interior_right (const Array< Point > &v, const size_t i)

static Array< Array< size_t > >	build_faces_from_diagonals (const Array< Point > &verts, const DynSetTree< std::pair< size_t, size_t > > &diagonals)

static Array< Array< size_t > >	decompose_to_monotone_faces (const Array< Point > &verts)

static bool	is_y_monotone (const Array< Point > &v)
	Check if a CCW polygon vertex array is y-monotone.

Detailed Description

O(n log n) triangulation of simple polygons via y-monotone partition + linear-time monotone triangulation.

Algorithm

Decompose the simple polygon into y-monotone sub-polygons by adding diagonals at split and merge vertices (sweep-line, O(n log n)).
Triangulate each y-monotone polygon in O(n) with a stack-based scan.

Requirements

Input must be a closed simple polygon with ≥ 3 vertices.
Vertices may be CW or CCW (normalized internally).

Complexity

Time: O(n log n) for general simple polygons.
Time: O(n) when the input polygon is already y-monotone.
Space: O(n)

Definition at line 6522 of file geom_algorithms.H.

Member Enumeration Documentation

◆ VertexType

enum class Aleph::MonotonePolygonTriangulation::VertexType

strongprivate

Classification of vertices for y-monotone decomposition.

Enumerator
START
END
SPLIT
MERGE
REGULAR

Definition at line 6543 of file geom_algorithms.H.

Member Function Documentation

◆ build_faces_from_diagonals()

static Array< Array< size_t > > Aleph::MonotonePolygonTriangulation::build_faces_from_diagonals	(	const Array< Point > &	verts,
		const DynSetTree< std::pair< size_t, size_t > > &	diagonals
	)

inlinestaticprivate

Definition at line 6949 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::empty(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::in_place_sort(), Aleph::in_place_unique(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::Array< T >::is_empty(), k, pred, Aleph::Array< T >::reserve(), Aleph::DynSetTree< Key, Tree, Compare >::search(), and Aleph::Array< T >::size().

Referenced by decompose_to_monotone_faces().

◆ classify_vertex()

static VertexType Aleph::MonotonePolygonTriangulation::classify_vertex	(	const Array< Point > &	v,
		const size_t	i
	)

inlinestaticprivate

Definition at line 6921 of file geom_algorithms.H.

References Aleph::and, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), END, is_above(), is_below(), MERGE, Aleph::next(), Aleph::orientation(), REGULAR, Aleph::Array< T >::size(), SPLIT, and START.

Referenced by decompose_to_monotone_faces().

◆ decompose_to_monotone_faces()

static Array< Array< size_t > > Aleph::MonotonePolygonTriangulation::decompose_to_monotone_faces ( const Array< Point > & verts )

inlinestaticprivate

◆ edge_goes_down()

static bool Aleph::MonotonePolygonTriangulation::edge_goes_down	(	const Array< Point > &	verts,
		const size_t	edge
	)

inlinestaticprivate

Check if the edge starting at edge points downwards.

Definition at line 6565 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and is_below().

Referenced by decompose_to_monotone_faces().

◆ edge_status_less()

static bool Aleph::MonotonePolygonTriangulation::edge_status_less	(	const size_t	lhs,
		const size_t	rhs,
		const Geom_Number &	sweep_y,
		const Array< Point > &	verts
	)

inlinestaticprivate

Definition at line 6584 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and edge_x_at_y().

Referenced by Aleph::MonotonePolygonTriangulation::EdgeStatusTree::predecessor_for_insert(), and Aleph::MonotonePolygonTriangulation::EdgeStatusTree::successor_for_insert().

◆ edge_x_at_y()

static Geom_Number Aleph::MonotonePolygonTriangulation::edge_x_at_y	(	const Array< Point > &	verts,
		const size_t	edge,
		const Geom_Number &	y
	)

inlinestaticprivate

Definition at line 6571 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), and y.

Referenced by edge_status_less(), and Aleph::MonotonePolygonTriangulation::EdgeStatusTree::left_edge_of_point().

◆ ensure_ccw()

static void Aleph::MonotonePolygonTriangulation::ensure_ccw ( Array< Point > & v )

inlinestaticprivate

Definition at line 6535 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::ensure_ccw().

Referenced by operator()().

◆ extract_vertices()

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

inlinestaticprivate

Definition at line 6525 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by operator()().

◆ is_above()

static bool Aleph::MonotonePolygonTriangulation::is_above	(	const Point &	a,
		const Point &	b
	)

inlinestaticprivate

Lexicographical "above" comparison (y primary, x secondary).

Definition at line 6548 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by classify_vertex(), and is_below().

◆ is_below()

static bool Aleph::MonotonePolygonTriangulation::is_below	(	const Point &	a,
		const Point &	b
	)

inlinestaticprivate

Lexicographical "below" comparison.

Definition at line 6557 of file geom_algorithms.H.

References is_above().

Referenced by classify_vertex(), edge_goes_down(), and regular_interior_right().

◆ is_y_monotone()

static bool Aleph::MonotonePolygonTriangulation::is_y_monotone ( const Array< Point > & v )

inlinestaticprivate

Check if a CCW polygon vertex array is y-monotone.

Definition at line 7305 of file geom_algorithms.H.

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

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

◆ operator()()

DynList< Triangle > Aleph::MonotonePolygonTriangulation::operator() ( Polygon p ) const

inline

Triangulate a simple polygon.

For convex and y-monotone polygons, the result is computed directly in O(n). For general simple polygons, the polygon is partitioned into y-monotone sub-polygons in O(n log n), then each sub-polygon is triangulated in linear time.

Parameters

p	The polygon (will not be modified; a copy is used).

Returns: List of triangles forming the triangulation.

Exceptions

domain_error	if polygon is not closed or has < 3 vertices.
domain_error	if polygon is degenerate (zero area).

Note: The algorithm follows the standard sweep-line monotone partition pipeline and runs in O(n log n) for simple polygons.

Definition at line 7239 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::DynList< T >::append(), decompose_to_monotone_faces(), Aleph::divide_and_conquer_partition_dp(), ensure_ccw(), extract_vertices(), Aleph::HTList::Iterator::has_curr(), Aleph::Polygon::is_closed(), is_y_monotone(), Aleph::Array< T >::reserve(), signed_double_area(), Aleph::Polygon::size(), Aleph::Array< T >::size(), Aleph::size(), and triangulate_monotone().

◆ regular_interior_right()

static bool Aleph::MonotonePolygonTriangulation::regular_interior_right	(	const Array< Point > &	v,
		const size_t	i
	)

inlinestaticprivate

Definition at line 6942 of file geom_algorithms.H.

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

Referenced by decompose_to_monotone_faces().

◆ signed_double_area()

static Geom_Number Aleph::MonotonePolygonTriangulation::signed_double_area ( const Array< Point > & v )

inlinestaticprivate

Definition at line 6530 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::signed_double_area().

Referenced by operator()().

◆ triangulate_monotone()

static DynList< Triangle > Aleph::MonotonePolygonTriangulation::triangulate_monotone ( const Array< Point > & verts )

inlinestaticprivate

Triangulate a y-monotone polygon given as a vertex array.

Definition at line 6815 of file geom_algorithms.H.

References Aleph::and, Aleph::DynList< T >::append(), Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::HTList::size(), Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by operator()().

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

geom_algorithms.H

Classes

Public Member Functions

Private Types

Static Private Member Functions

Detailed Description

Algorithm

Requirements

Complexity

Member Enumeration Documentation

◆ VertexType

Member Function Documentation

◆ build_faces_from_diagonals()

◆ classify_vertex()

◆ decompose_to_monotone_faces()

◆ edge_goes_down()

◆ edge_status_less()

◆ edge_x_at_y()

◆ ensure_ccw()

◆ extract_vertices()

◆ is_above()

◆ is_below()

◆ is_y_monotone()

◆ operator()()

◆ regular_interior_right()

◆ signed_double_area()

◆ triangulate_monotone()