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.
out
size_t size_t int32_t * out
Definition ca-c-api.h:120
Aleph::AlphaShape
Alpha shape of a point set.
Definition geom_algorithms.H:10713
Aleph::DynList
Doubly-linked list (defined in tpl_dynList.H).
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:221
Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466
Aleph::Geom_Number
mpq_class Geom_Number
Numeric type used by the geometry module.
Definition point.H:113

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

References Aleph::and, Aleph::area_of_parallelogram(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Point::distance_squared_to(), 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: