Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Member Functions | List of all members
Aleph::AlphaShape Class Reference

Alpha shape of a point set. More...

#include <geom_algorithms.H>

Classes

struct  Result
 Result of an alpha-shape computation. More...
 

Public Member Functions

Result operator() (const DynList< Point > &points, const Geom_Number &alpha_squared) const
 Compute the α-shape.
 

Detailed Description

Alpha shape of a point set.

The α-shape is a generalization of the convex hull. For α = ∞ it equals the convex hull; as α decreases, the shape "shrinks" around the points, revealing concavities.

Algorithm

  1. Compute the Delaunay triangulation.
  2. Filter: keep only triangles whose circumradius² ≤ α².
  3. Extract the boundary edges (edges belonging to exactly one kept triangle).

Complexity

O(n log n) for the Delaunay step + O(T) to filter, where T = number of Delaunay triangles.

Example
DynList<Point> pts;
pts.append(Point(0,0));
pts.append(Point(1,0));
pts.append(Point(0,1));
pts.append(Point(1,1));
AlphaShape as;
auto out = as(pts, Geom_Number(1));
// out.boundary_edges is the alpha-shape boundary as segments.
Aleph::AlphaShape
Alpha shape of a point set.
Definition geom_algorithms.H:10745
Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1155
Aleph::DynList::append
T & append(const T &item)
Definition htlist.H:1271
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133
Aleph::Geom_Number
mpq_class Geom_Number
Numeric type used by the geometry module.
Definition point.H:115

Definition at line 10744 of file geom_algorithms.H.

Member Function Documentation

◆ operator()()

Result Aleph::AlphaShape::operator() ( const DynList< Point > &  points,
const Geom_Number &  alpha_squared 
) const
inline

Compute the α-shape.

Parameters
pointsInput point set.
alpha_squaredThe α² threshold. A Delaunay triangle is kept iff its circumradius² ≤ alpha_squared.
Returns
The filtered triangulation and its boundary.
Exceptions
domain_errorif fewer than 3 points.

Key for identifying an undirected edge by its vertex indices.

< Vertex indices (sorted u < v).

Exact equality check.

Definition at line 10768 of file geom_algorithms.H.

References Aleph::and, Aleph::area_of_parallelogram(), Aleph::Point::distance_squared_to(), Aleph::divide_and_conquer_partition_dp(), k, operator<(), operator==(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), and Aleph::AlphaShape::Result::sites.

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