lidR (version 3.2.3)

concaveman: A very fast 2D concave hull algorithm

Description

A very fast 2D concave hull algorithm for a set of points

Usage

concaveman(x, y = NULL, concavity = 2, length_threshold = 0)

Arguments

x, y

coordinate vectors of points. This can be specified as two vectors x and y, a 2-column matrix x, a list with two components, etc.

concavity

numeric a relative measure of concavity. 1 results in a relatively detailed shape, Infinity results in a convex hull. You can use values lower than 1, but they can produce pretty crazy shapes.

length_threshold

numeric. When a segment length is under this threshold, it stops being considered for further detailed processing. Higher values result in simpler shapes.

Details

The algorithm is based on ideas from Park and Oh (2012). A first implementation in JavaScript was proposed by Vladimir Agafonkin in mapbox. This implementation dramatically improved performance over the one stated in the paper using a spatial index. The algorithm was then ported to R by Jo<U+00EB>l Gombin in the R package concaveman that runs the JavaScript implementation proposed by Vladimir Agafonkin. Later a C++ version of Vladimir Agafonkin's JavaScript implementation was proposed by Stanislaw Adaszewski in concaveman-cpp. This concaveman function uses Stanislaw Adaszewski's C++ code making the concaveman algorithm an order of magnitude (up to 50 times) faster than the Javascript version.

References

Park, J.-S & Oh, S.-J. (2013). A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets. Journal of Information Science and Engineering. 29. 379-392.

Examples

# NOT RUN {
x = runif(35)
y = runif(35)
hull <- concaveman(x,y)
plot(x,y, asp = 1)
lines(hull, lwd = 3, col = "red")
# }