Comprehensive example demonstrating Aleph-w's computational geometry. More...

#include <iostream>
#include <iomanip>
#include <cmath>
#include <chrono>
#include <cstring>
#include <geom_algorithms.H>
#include <tpl_dynArray.H>
#include <cstdlib>

Include dependency graph for geom_example.C:

Functions
void	print_header (const string &title)

void	print_subheader (const string &subtitle)

double	to_double (const Geom_Number &n)
	Convert Geom_Number to double.

void	print_point (const Point &p, const string &label="")
	Print a point with optional label.

void	print_polygon (const Polygon &poly, const string &name)
	Print a polygon's vertices.

void	print_triangle (const Triangle &t, int index)
	Print a triangle.

double	triangle_area (const Triangle &t)
	Calculate area of a triangle using cross product.

void	demo_triangulation_basic ()

void	demo_triangulation_complex ()

void	demo_convex_hull_cities ()

void	demo_convex_hull_performance ()

void	demo_geometric_primitives ()

void	demo_coverage_area ()

void	demo_advanced_algorithms ()

static void	usage (const char *prog)

int	main (int argc, char *argv[])

Detailed Description

Comprehensive example demonstrating Aleph-w's computational geometry.

This example showcases fundamental geometric algorithms from geom_algorithms.H, demonstrating how to solve common problems in computational geometry. The examples use Colombian geographical locations and landmarks for real-world context.

Computational Geometry Overview

Computational geometry deals with algorithms for solving geometric problems, such as finding convex hulls, triangulating polygons, and computing distances. These algorithms are essential in computer graphics, GIS, robotics, and more.

Algorithms Demonstrated

1. Polygon Triangulation

Problem: Decompose a simple polygon into triangles.

Algorithm: Ear-Cutting (CuttingEarsTriangulation)

An "ear" is a triangle formed by three consecutive vertices
Repeatedly "cut off" ears until polygon is fully triangulated
Time: O(n²) worst case, O(n) for convex polygons
Space: O(n)

Applications:

Computer graphics: Rendering polygons
Mesh generation: Finite element analysis
Game development: Collision detection
GIS: Polygon decomposition

2. Convex Hull Algorithms

Problem: Find the smallest convex polygon containing all points.

Three algorithms are demonstrated:

BruteForceConvexHull

Check all possible edges
Time: O(n³)
Use: Educational, small datasets

GiftWrappingConvexHull (Jarvis March)

Start with leftmost point, "wrap" around points
Time: O(nh) where h = number of hull points
Use: Output-sensitive, good when h is small

QuickHull

Divide and conquer approach
Time: O(n log n) average, O(n²) worst case
Use: General purpose, most practical

Applications:

Collision detection: Bounding shapes
Pattern recognition: Shape analysis
Computer vision: Object detection
Robotics: Path planning

Complexity Comparison

Algorithm	Time Complexity	Best For
Polygon Triangulation	O(n²)	Simple polygons
Brute Force Hull	O(n³)	Small datasets, education
Gift Wrapping	O(nh)	Few hull points
QuickHull	O(n log n) avg	General purpose

Colombian Geography Theme

Examples use real Colombian locations:

Cities: Bogotá, Medellín, Cali, Barranquilla
Landmarks: Mountains, rivers, regions
Makes examples more relatable and interesting

Geometric Data Structures

The example uses:

Point: 2D coordinates (x, y)
Polygon: Ordered list of points
PointSet: Collection of points for hull computation

Usage

# Run all geometric algorithm demos
./geom_example
 
# Run specific algorithm
./geom_example -s triangulation
./geom_example -s convexhull

See also: geom_algorithms.H Geometric algorithm implementations

Author: Leandro Rabindranath León

Definition in file geom_example.C.

Function Documentation

◆ demo_advanced_algorithms()

void demo_advanced_algorithms ( )

Definition at line 663 of file geom_example.C.

References Aleph::Polygon::add_vertex(), Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::VoronoiDiagramFromDelaunay::clipped_cells_indexed(), Aleph::PointInPolygonWinding::contains(), Aleph::divide_and_conquer_partition_dp(), print_header(), print_subheader(), and Aleph::Polygon::size().

Referenced by main().

◆ demo_convex_hull_cities()

void demo_convex_hull_cities ( )

Definition at line 346 of file geom_example.C.

References abs(), Aleph::DynArray< T >::append(), Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), print_header(), print_subheader(), to_double(), and y.

Referenced by main().

◆ demo_convex_hull_performance()

void demo_convex_hull_performance ( )

Definition at line 452 of file geom_example.C.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), print_header(), Aleph::DynArray< T >::size(), and y.

Referenced by main().

◆ demo_coverage_area()

void demo_coverage_area ( )

Definition at line 595 of file geom_example.C.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::Segment::length(), print_header(), Aleph::HTList::size(), to_double(), and triangle_area().

Referenced by main().

◆ demo_geometric_primitives()

void demo_geometric_primitives ( )

Definition at line 526 of file geom_example.C.

References Aleph::Triangle::contains(), Aleph::divide_and_conquer_partition_dp(), print_header(), print_point(), print_subheader(), to_double(), and triangle_area().

Referenced by main().

◆ demo_triangulation_basic()

void demo_triangulation_basic ( )

Definition at line 234 of file geom_example.C.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), cos(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), print_header(), print_polygon(), print_subheader(), print_triangle(), sin(), Aleph::HTList::size(), and triangle_area().

Referenced by main().

◆ demo_triangulation_complex()

void demo_triangulation_complex ( )

Definition at line 303 of file geom_example.C.

References Aleph::Polygon::add_vertex(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), print_header(), print_polygon(), print_subheader(), print_triangle(), Aleph::HTList::size(), and triangle_area().

Referenced by main().

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 742 of file geom_example.C.

References demo_advanced_algorithms(), demo_convex_hull_cities(), demo_convex_hull_performance(), demo_coverage_area(), demo_geometric_primitives(), demo_triangulation_basic(), demo_triangulation_complex(), Aleph::divide_and_conquer_partition_dp(), section(), and usage().

◆ print_header()

void print_header ( const string & title )

Definition at line 150 of file geom_example.C.

References Aleph::divide_and_conquer_partition_dp().

◆ print_point()

void print_point	(	const Point &	p,
		const string &	label = `""`
	)

Print a point with optional label.

Definition at line 175 of file geom_example.C.

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

Referenced by demo_geometric_primitives().

◆ print_polygon()

void print_polygon	(	const Polygon &	poly,
		const string &	name
	)

Print a polygon's vertices.

Definition at line 186 of file geom_example.C.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), Aleph::Polygon::size(), and to_double().

Referenced by demo_triangulation_basic(), and demo_triangulation_complex().

◆ print_subheader()

void print_subheader ( const string & subtitle )

Definition at line 158 of file geom_example.C.

References Aleph::divide_and_conquer_partition_dp().

Referenced by demo_advanced_algorithms(), demo_convex_hull_cities(), demo_geometric_primitives(), demo_triangulation_basic(), and demo_triangulation_complex().

◆ print_triangle()

void print_triangle	(	const Triangle &	t,
		int	index
	)

Print a triangle.

Definition at line 201 of file geom_example.C.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Triangle::get_p1(), Aleph::Triangle::get_p2(), Aleph::Triangle::get_p3(), Aleph::Point::get_x(), Aleph::Point::get_y(), and to_double().

Referenced by demo_triangulation_basic(), and demo_triangulation_complex().

◆ to_double()

double to_double ( const Geom_Number & n )

inline

Convert Geom_Number to double.

Definition at line 167 of file geom_example.C.

References __gmp_expr< mpq_t, mpq_t >::get_d().

Referenced by demo_convex_hull_cities(), demo_coverage_area(), demo_geometric_primitives(), print_point(), print_polygon(), print_triangle(), and triangle_area().

◆ triangle_area()

double triangle_area ( const Triangle & t )

Calculate area of a triangle using cross product.

Definition at line 216 of file geom_example.C.

References abs(), Aleph::divide_and_conquer_partition_dp(), Aleph::Triangle::get_p1(), Aleph::Triangle::get_p2(), Aleph::Triangle::get_p3(), Aleph::Point::get_x(), Aleph::Point::get_y(), and to_double().

Referenced by demo_coverage_area(), demo_geometric_primitives(), demo_triangulation_basic(), demo_triangulation_complex(), TEST_F(), TEST_F(), and TEST_F().

◆ usage()

static void usage ( const char * prog )

static

Definition at line 735 of file geom_example.C.

References Aleph::divide_and_conquer_partition_dp().