Aleph::CuttingEarsTriangulation Class Reference

Polygon triangulation using the ear-cutting algorithm. More...

#include <geom_algorithms.H>

Public Member Functions
DynList< Triangle >	operator() (const Polygon &poly) const
	Triangulate the polygon.

Static Public Member Functions
static bool	diagonalize (const Polygon &p, const Segment &s)
	Check if a segment is a valid diagonal of the polygon.
static bool	in_cone (const Polygon &p, const Vertex &a, const Vertex &b)
	Check if vertex b is inside the cone formed at vertex a.
static bool	diagonal (const Polygon &p, const Vertex &a, const Vertex &b)
	Check if segment (a, b) is a valid internal diagonal.
static EarsSet	init_ears (const Polygon &p)
	Initialize the set of ear vertices.

Private Types
using	EarsSet = DynSetTree< const Vertex *, Treap_Rk >

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

Detailed Description

Polygon triangulation using the ear-cutting algorithm.

Decomposes a simple polygon into a set of non-overlapping triangles. An "ear" is a triangle formed by three consecutive vertices where the diagonal between the first and third vertices lies entirely inside the polygon.

Algorithm

1. Find all ears (vertices whose diagonal is inside the polygon)
2. Remove an ear, creating a triangle
3. Update the ear status of adjacent vertices
4. Repeat until only a triangle remains

Complexity

• Time: O(n²) where n = number of vertices
• Space: O(n) for the ears set

Requirements

• Input must be a simple polygon (no self-intersections)
• Polygon must have at least 3 vertices
• Vertices can be clockwise or counter-clockwise (normalized internally)

Example

// Create a convex quadrilateral
Polygon quad;
quad.add_vertex(Point(0, 0));
quad.add_vertex(Point(4, 0));
quad.add_vertex(Point(4, 3));
quad.add_vertex(Point(0, 3));
quad.close();
 
CuttingEarsTriangulation triangulator;
DynList<Triangle> triangles = triangulator(quad);
// Result: 2 triangles

Warning

The input polygon is modified (vertices are removed). Pass a copy if you need to preserve the original.

See also

Triangle Output triangle type

Polygon Input polygon type

Author

Leandro Rabindranath León

Alejandro J. Mujica

Definition at line 639 of file geom_algorithms.H.

Member Typedef Documentation

EarsSet

using Aleph::CuttingEarsTriangulation::EarsSet = DynSetTree<const Vertex *, Treap_Rk>

private

Definition at line 641 of file geom_algorithms.H.

Member Function Documentation

diagonal()

static bool Aleph::CuttingEarsTriangulation::diagonal ( const Polygon &  p, const Vertex &  a, const Vertex &  b  )

inlinestatic

Check if segment (a, b) is a valid internal diagonal.

Parameters

p	The polygon.
a	First vertex of the diagonal.
b	Second vertex of the diagonal.

Returns

true if (a, b) is a valid diagonal.

Definition at line 723 of file geom_algorithms.H.

References Aleph::and, diagonalize(), in_cone(), and Aleph::Vertex::to_point().

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

diagonalize()

static bool Aleph::CuttingEarsTriangulation::diagonalize ( const Polygon &  p, const Segment &  s  )

inlinestatic

Check if a segment is a valid diagonal of the polygon.

A diagonal is valid if it doesn't intersect any edge of the polygon (except at endpoints).

Parameters

p	The polygon.
s	The candidate diagonal segment.

Returns

true if s is a valid diagonal.

Definition at line 679 of file geom_algorithms.H.

References Aleph::and, Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Polygon::Segment_Iterator::has_curr(), and Aleph::Segment::intersects_with().

Referenced by diagonal().

extract_vertices()

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

inlinestaticprivate

Definition at line 643 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by normalize_to_ccw().

in_cone()

static bool Aleph::CuttingEarsTriangulation::in_cone ( const Polygon &  p, const Vertex &  a, const Vertex &  b  )

inlinestatic

Check if vertex b is inside the cone formed at vertex a.

The cone is defined by the edges adjacent to a (from prev to next).

Parameters

p	The polygon.
a	The vertex forming the cone apex.
b	The vertex to test.

Returns

true if b is visible from a within the polygon.

Definition at line 702 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::get_next_vertex(), Aleph::Polygon::get_prev_vertex(), Aleph::Point::is_left_of(), and Aleph::Point::is_to_left_on_from().

Referenced by diagonal().

init_ears()

static EarsSet Aleph::CuttingEarsTriangulation::init_ears ( const Polygon &  p )

inlinestatic

Initialize the set of ear vertices.

Parameters

p	The polygon.

Returns

Set of pointers to ear vertices.

Definition at line 735 of file geom_algorithms.H.

References diagonal(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::get_next_vertex(), Aleph::Polygon::get_prev_vertex(), Aleph::Dlink::Iterator::has_curr(), Aleph::Dlink::insert(), and Aleph::next().

Referenced by operator()().

normalize_to_ccw()

static void Aleph::CuttingEarsTriangulation::normalize_to_ccw ( Polygon &  p )

inlinestaticprivate

Definition at line 653 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), extract_vertices(), and signed_double_area().

Referenced by operator()().

operator()()

DynList< Triangle > Aleph::CuttingEarsTriangulation::operator() ( const Polygon &  poly ) const

inline

Triangulate the polygon.

Parameters

poly	The polygon to triangulate.

Returns

List of triangles forming the triangulation.

Exceptions

domain_error	if polygon is not closed.
domain_error	if the polygon has fewer than 3 vertices.
domain_error	if polygon is degenerate (zero area).
domain_error	if no valid ear can be found.

Definition at line 762 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Dlink::append(), diagonal(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::get_first_vertex(), Aleph::Polygon::get_next_vertex(), Aleph::Polygon::get_prev_vertex(), init_ears(), Aleph::Dlink::insert(), Aleph::Polygon::is_closed(), Aleph::next(), Aleph::Vertex::next_vertex(), normalize_to_ccw(), Aleph::Polygon::remove_vertex(), Aleph::Polygon::size(), and Aleph::Vertex::to_point().

signed_double_area()

static Geom_Number Aleph::CuttingEarsTriangulation::signed_double_area ( const Polygon &  p )

inlinestaticprivate

Definition at line 648 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::signed_double_area().

Referenced by normalize_to_ccw().

---

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

• geom_algorithms.H