Aleph::CuttingEarsTriangulation Class Reference

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

#include <geom_algorithms.H>

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

Static Public Member Functions
static bool	diagonalie (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 >

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 should be in counter-clockwise order

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

Alejandro J. Mujica

Definition at line 168 of file geom_algorithms.H.

Member Typedef Documentation

EarsSet

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

private

Definition at line 170 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 230 of file geom_algorithms.H.

References diagonalie(), in_cone(), and Aleph::maps().

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

diagonalie()

static bool Aleph::CuttingEarsTriangulation::diagonalie ( 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 184 of file geom_algorithms.H.

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

Referenced by diagonal().

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 209 of file geom_algorithms.H.

References Polygon::get_next_vertex(), Polygon::get_prev_vertex(), and Aleph::maps().

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 242 of file geom_algorithms.H.

References diagonal(), Polygon::get_next_vertex(), Polygon::get_prev_vertex(), Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::next().

Referenced by operator()().

operator()()

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

inline

Triangulate the polygon.

Parameters

p	The polygon to triangulate (will be modified).

Returns

List of triangles forming the triangulation.

Exceptions

domain_error

if the polygon has fewer than 3 vertices.

Note

The input polygon is consumed (vertices removed).

Definition at line 270 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), diagonal(), Polygon::get_first_vertex(), Polygon::get_next_vertex(), Polygon::get_prev_vertex(), init_ears(), Aleph::DynList< T >::insert(), Aleph::maps(), Aleph::next(), Vertex::next_vertex(), Aleph::DynList< T >::remove(), Polygon::remove_vertex(), and Polygon::size().

---

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

• geom_algorithms.H