Convex hull of lattice points by Andrew's monotone chain

Orientation tests are exact integer cross products, so no hull vertex is ever mis-classified by rounding – the failure mode of floating hulls on nearly-collinear input. Collinear boundary points are dropped; the hull is the minimal vertex set, counter-clockwise from the lexicographic minimum.

Usage

morie_lattice_convex_hull(points)

Arguments

points

Two-column matrix of integer (x, y).

Value

A list with hull (matrix), n_vertices, twice_area (exact integer), area.

Examples

D <- data.frame(x = c(1, 2, 3, 4), y = c(2, 4, 5, 9))
morie_lattice_convex_hull(D)
#> $hull
#>      x y
#> [1,] 1 2
#> [2,] 3 5
#> [3,] 4 9
#> 
#> $n_vertices
#> [1] 3
#> 
#> $twice_area
#> [1] 5
#> 
#> $area
#> [1] 2.5
#> 
#> $estimate
#> [1] 2.5
#> 
#> $n
#> [1] 4
#> 
#> $method
#> [1] "Andrew's monotone chain, exact integer orientation"
#>