Convex-hull shape metrics and alpha shapes

ConvexHull: Andrew's monotone chain, counter-clockwise from the lexicographically smallest point, collinear points dropped. HullMetrics: solidity (polygon area over hull area), elongation \(1 - w/l\) of the minimum-area enclosing rectangle (rotating calipers), its orientation, the FRAGSTATS fractal dimension \(2 \ln(P/4) / \ln A\) and the isoperimetric roundness \(4 \pi A / P^2\) of hull and polygon. Delaunay: Bowyer-Watson triangulation (general position assumed). TriangleQuality: \(4\sqrt{3} A / (a^2 + b^2 + c^2)\) per triangle (1 equilateral), areas and longest-to-shortest edge ratios (Field 2000). AlphaShape: Delaunay triangles with circumradius at most radius, their area, boundary edges and perimeter (Edelsbrunner, Kirkpatrick and Seidel 1983). Identical to the Python arm morie.fn.hullgeo; indices are 1-based here.

Usage

ConvexHull(points)

HullMetrics(polygon)

Delaunay(points)

TriangleQuality(points, triangles = NULL)

AlphaShape(points, radius)

Arguments

points, polygon: Two-column coordinates (polygon vertices in order).
triangles: Triangle index matrix (default the Delaunay triangulation).
radius: Alpha radius.

Value

Matrix (ConvexHull, Delaunay) or list.

References

Andrew, A. M. (1979). Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9, 216-219.

Freeman, H. and Shapira, R. (1975). Determining the minimum-area encasing rectangle for an arbitrary closed curve. Communications of the ACM 18, 409-413.

Edelsbrunner, H., Kirkpatrick, D. G. and Seidel, R. (1983). On the shape of a set of points in the plane. IEEE Transactions on Information Theory 29, 551-559.

Field, D. A. (2000). Qualitative measures for initial meshes. International Journal for Numerical Methods in Engineering 47, 887-906.

Examples

HullMetrics(rbind(c(0, 0), c(4, 0), c(4, 1), c(0, 1)))$elongation
#> [1] 0.75
Delaunay(rbind(c(0, 0), c(2, 0), c(0, 2), c(2.2, 2.1)))
#>      [,1] [,2] [,3]
#> [1,]    1    2    3
#> [2,]    2    3    4
AlphaShape(rbind(c(0, 0), c(2, 0), c(0, 2), c(2.2, 2.1)), 10)$area
#> [1] 4.3