Overview

This page describes the various distance metrics implemented in the Correa shape comparison library. These metrics quantify the dissimilarity between two 2D polygonal shapes from different geometric and topological perspectives.

Available Distance Metrics

Fréchet Distance (Type 0)

The Fréchet distance measures the similarity between two curves by considering their trajectories. It can be intuitively understood as the minimum length of a leash required for a person walking along one curve and their dog walking along another curve, where both can control their speed but cannot go backwards.

Mathematical Definition: Given two curves P and Q, the Fréchet distance is:

$\delta_F(P, Q) = \inf_{\alpha, \beta} \max_{t \in [0,1]} d(P(\alpha(t)), Q(\beta(t)))$

where $\alpha$ and $\beta$ are continuous monotone reparameterizations.

Properties:

Captures both location and ordering of points along curves
Sensitive to the shape of the entire trajectory
Metric: satisfies triangle inequality, symmetry, and non-negativity

Use Cases:

Comparing shapes where the ordering of points matters
Path similarity analysis
Shape matching where global structure is important

Ellipse-Based Distances (Type 1)

These metrics compare shapes based on the properties of fitted ellipses. Three types of ellipse fits are computed for each polygon:

1. Maximum Volume Inscribed Ellipse:

The largest ellipse that fits completely inside the polygon
Provides a measure of the polygon's interior capacity

2. Minimum Volume Inscribing Ellipse:

The smallest ellipse that completely contains the polygon
Provides an outer bound on the shape

3. Least-Squares Ellipse:

Ellipse fitted by minimizing squared distances to polygon vertices
Balances interior and exterior fit

Distance Computation: For each ellipse type, we compute the aspect ratio r = a/b (where a and b are semi-major and semi-minor axes). The distance between two polygons is the absolute difference in their aspect ratios:

$d_E(P_1, P_2) = |r_1 - r_2|$

Properties:

Captures overall elongation and orientation
Robust to small perturbations in polygon vertices
Scale-invariant when comparing aspect ratios

Use Cases:

Comparing overall shape elongation
Orientation-independent shape classification
Quality control in manufacturing (elliptical objects)

Curvature-Based Distances (Type 2)

These metrics analyze shapes based on their curvature properties, capturing local geometric features and bending characteristics.

1. Willmore Energy: The Willmore energy measures the total squared curvature of a curve:

$W = \int \kappa^2 \, ds$

where $\kappa$ is the curvature and s is arc length.

The distance between two polygons is:

$d_W(P_1, P_2) = |W_1 - W_2|$

Properties:

Measures the "bending energy" of the curve
Minimized by circles (constant curvature)
Sensitive to sharp corners and irregularities

2. Wasserstein Distance on Curvature Distributions: Treats the curvature distribution along each polygon as a probability measure and computes the optimal transport distance between them.

$d_{OT}(\mu_1, \mu_2) = \inf_{\gamma \in \Gamma(\mu_1, \mu_2)} \int |x - y| \, d\gamma(x, y)$

Properties:

Captures differences in local curvature patterns
More informative than global curvature measures
Robust metric structure (satisfies triangle inequality)

Use Cases:

Detecting shape deformations and irregularities
Smoothness comparison
Medical imaging (comparing organ boundaries)

Persistence Diagram Distance (Type 3)

This metric uses topological data analysis to compare shapes based on their persistent homology features, specifically 0-dimensional persistence (connected components).

Persistence Diagrams: A persistence diagram is a multiset of points (b, d) in the plane, where:

b (birth): the scale at which a topological feature appears
d (death): the scale at which the feature disappears
Persistence = d - b measures feature significance

2-Wasserstein Distance: The distance between two persistence diagrams $D_1$ and $D_2$ is:

$W_2(D_1, D_2) = \left( \inf_{\gamma: D_1 \to D_2} \sum_{p \in D_1} \|p - \gamma(p)\|_2^2 \right)^{1/2}$

where the infimum is over all bijections $\gamma$ (including the diagonal).

Properties:

Topologically robust: insensitive to small perturbations
Captures multi-scale shape features
Mathematically well-founded metric
Stable under continuous deformations

Use Cases:

Shape classification with topological invariance
Robust feature detection in noisy data
Multi-scale shape analysis
Pattern recognition in scientific data

Sphericity Measure

All comparison programs also compute the sphericity difference:

$d_S(P_1, P_2) = 4\pi \left| \frac{A_1}{L_1^2} - \frac{A_2}{L_2^2} \right|$

where A is area and L is perimeter length.

Properties:

Measures how close a shape is to a circle (circle has sphericity = 1)
Scale-invariant (dimensionless quantity)
Simple and computationally efficient

Choosing a Distance Metric

Different metrics are appropriate for different applications:

Metric	Best For	Computational Cost
Fréchet	Path similarity, ordered matching	Medium
Ellipse-based	Overall shape, elongation	Low
Curvature-based	Local features, smoothness	Medium
Persistence	Topological features, noisy data	High
Sphericity	Quick comparison, roundness	Very Low

Recommendations:

Use Type 4 (All) for comprehensive analysis when computational cost is not a concern
Use Fréchet for ordered point sequences and path matching
Use Ellipse-based for fast, orientation-independent comparison
Use Curvature-based when local shape details matter
Use Persistence for robust topological comparison resistant to noise

Implementation Notes

All distance metrics are implemented in the following programs:

Comp2DShapesFocal: User-specified focal points for alignment
Comp2DShapes: Automatic centroid-based alignment

The distance type is selected via the -d command-line flag.

See also: Comp2DShapesFocal.cpp; Comp2DShapes.cpp; parse_args()