mapbox/concaveman

A very fast 2D concave hull algorithm in JavaScript

concaveman

A very fast 2D concave hull algorithm in JavaScript (generates a general outline of a point set).

Usage

var points = [[10, 20], [30, 12.5], ...];
var polygon = concaveman(points);

Signature: concaveman(points[, concavity = 2, lengthThreshold = 0])

• points is an array of [x, y] points.
• concavity is 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.
• lengthThreshold: when a segment length is under this threshold, it stops being considered for further detalization. Higher values result in simpler shapes.

Algorithm

The algorithm is based on ideas from the paper A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets, 2012 by Jin-Seo Park and Se-Jong Oh.

This implementation dramatically improves performance over the one stated in the paper (O(rn), where r is a number of output points, to O(n log n)) by introducing a fast k nearest points to a segment algorithm, a modification of a depth-first kNN R-tree search using a priority queue.

TypeScript

TypeScript type definitions are available through npm install --save @types/concaveman.

Dependencies

• monotone-convex-hull-2d for the convex hull algorithm
• rbush for point indexing
• tinyqueue as a priority queue
• point-in-polygon for point in polygon queries
• robust-orientation for 3-point orientation tests

C++ Port

In 2019, a C++ port has been created, allowing for efficient usage from C/C++, Python (via cffi) and other languages featuring an FFI and/or plug-in mechanism for C (e.g. a MATLAB MEX file should be easy to prepare).

concaveman's Issues

Support esm

Any chance to support esm?

function doesn't return original coordinates

First, thank you for the awesome function! As the title already indicates, the function does not return the original coordinates. It seems that this is a rounding issue. Please see my example code (in R) which should illustrate the problem.

# create dummy data.frame with X/Y coordinates and ID column
cur_df = sample(x = 1:2, size = 500, replace = T)
cur_df = as.data.frame(cbind(cur_df, matrix(rexp(1000, rate=.1), ncol=2)))
colnames(cur_df)<- c("id", "X", "Y")

# compute concave hull
coords <- as.matrix(cbind(cur_df$X, cur_df$Y))
hull = as.data.table(concaveman(coords, concavity = 1))  
colnames(hull) <- c("X", "Y")

# how many data points make up the hull?
nrow(hull)
[1] 212

# return common rows between input and the hull
common <- inner_join(cur_df, hull)  
> Joining, by = c("X", "Y")

# number of common rows
nrow(common)
[1] 0

My input consists of coordinates that have 8 digits but the output coordinates from the concave function have only 4 digits. Therefore, it is not possible to find the common rows (by the inner_join function) between input and output.

I don't know if this behavior is intended but I think it should not be the default.

Thank you!

> sessionInfo()
R version 4.0.0 (2020-04-24)
Platform: x86_64-apple-darwin17.0 (64-bit)
Running under: macOS High Sierra 10.13.6

Matrix products: default
BLAS:   /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/4.0/Resources/lib/libRlapack.dylib

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] dplyr_0.8.5       data.table_1.12.8 sf_0.9-3          concaveman_1.1.0 

loaded via a namespace (and not attached):
 [1] Rcpp_1.0.4.6       rstudioapi_0.11    magrittr_1.5       units_0.6-6        tidyselect_1.1.0   R6_2.4.1          
 [7] rlang_0.4.6        tools_4.0.0        grid_4.0.0         KernSmooth_2.23-17 e1071_1.7-3        DBI_1.1.0         
[13] ellipsis_0.3.1     class_7.3-17       assertthat_0.2.1   tibble_3.0.1       lifecycle_0.2.0    crayon_1.3.4      
[19] purrr_0.3.4        vctrs_0.3.0        curl_4.3           glue_1.4.1         V8_3.0.2           compiler_4.0.0    
[25] pillar_1.4.4       classInt_0.4-3     jsonlite_1.6.1     pkgconfig_2.0.3   

Look at replacing robust-orientation with robust-predicates

We've had a few issues upstream in Turf because of robust-predicates causing an issue.

Uncaught EvalError: Refused to evaluate a string as JavaScript because 'unsafe-eval' is not an allowed source of script in the following Content Security Policy directive: "script-src 'self' 'unsafe-inline'

See related issue in robust-orientation

Potentially robust-predicates could be used to replace it, however in swapping one for the other there were changes

So It's not quite a drop in replacement yet but I thought I'd flag it here and I'll also open an issue in robust-predicates

FeatureRequest: Segments as input

Would it be possible to extend concaveman to support segments as input in addition to points?

The use case would be to fix slightly broken complex vector data, where say the boundary lines of a lake don't quite make up a closed polygon.

I was initially thinking converting the lines to points, but I realized that this will cause artifacts in cases where the original segments made a nice crisp edge (say at a jetty), the inner corners will end up mitered by the tolerance amount, which would in my case be significant.

TypeError: Queue is not a constructor

Hello!

When running version v1.2.0 of concaveman with Webpack (in a vue-cli environment), the following error occurs:

TypeError: Queue is not a constructor
    at findCandidate (index.js:95)
    at concaveman (index.js:65)

In Chrome Debugger, Queue is an object which holds a transpiled ES6 module, and has __esModule and default properties.

Is this a bug in concaveman or my Webpack configuration?

Thanks!

Interactive demo

Something like https://www.mapbox.com/bites/00222/, maybe with clustered random points like in RBush demo http://mourner.github.io/rbush/viz/viz-cluster.html

concave hull with break lines

I am trying to perform a concave hull with break lines on the edges. Any Ideas?

feature request: 3D

I'd like to generate a 3D concave hull of 3D points. I'm on a quest to make it happen. The Wikipedia article on Alpha Shapes links to a 3D version of Alpha Shapes written in R.

Ordering?

What's the order of the points returned? They appear to be somewhat random.

extend to 3d cluster of points

The actual use of this would come if it can handle large 3-d clusters of points and return the concave hull in fast computation

Prevent the algorithm from generating self-intersecting polygons

In some cases, the algorithm generates self-intersections. We should fix this and guarantee that the resulting concave hull is a simple polygon.

guidelines for getting consistent results

I'm looking for guidelines for getting consistent results.

I started off with a data set of around 250k GPS points. I got great results, but as I add more points I am seeing inconsistency. For instance, initially it took around 20 seconds to run, but after adding points, suddenly it dropped to around 2 seconds despite there being more points! It also seems to sometimes improperly gap across points on the map instead of following the concave shape, even in areas nowhere near where new points were added.

I thought to fix this problem by taking the resulting set of points from a good run with concaveman and then adding the new points and rerunning the algorithm. This worked fine the first time, but the second time it seems to have become intractible, running over 20 minutes before I interrupted the process, with only 26.3k points in the input, of which 21.6k were from the previously found results.

I'm mostly using the default concavity of 2, except occasionally I have pushed it as low as 1.3 when I find the output has weird jumps where it shouldn't. There seems to be some kind of threshold where as I lower the number it takes about the same amount of time and then suddenly it becomes intractible again. In the latest case, I found that if concavity was 2.4491023 or above, it would consistently take between 2.0 and 2.2s to complete, but at 2.4491022 and below it would never seem to finish. Upping the length threshold has no effect. However, the results in this case are unacceptable as there are several cases where I see what appear to be lines drawn between distance points on the perimeter, as well as spots where the results aren't concave enough.

Are there any guidelines as to how I can get better results? Should I sort the points by some criteria? Am I expected to sort the output (could this be why I sometimes see lines between distance points when I plot the coordinates on a map)? Is there a limit on how many points I should try to pass? Should I format the numbers differently, e.g. could GPS coordinates with 8 or nine digits after the decimal place run into precision issues or something?

Standalone bundled script

Hi, I'm using D3.js for years and now Leaflet more often and need to display the concave regions from points in the same area.

Now, I know how to script Electron (Node.js) applications yet am not versed to bundle (node) modules to standalone files e.g. bundled with all dependent libraries into one file.

Is there concaveman.js available with this requirement - or is there an easy way to pack it into one file (to be used in a web browser with either D3.js or Leaflet or other script/code)?

It's funny that concaveman(points) function works in the web browser console yet doesn't on a page.

Does the library guarantee that the coords will be picked from the input points and not cloned?

Hi,
From knowing the theoretical algorithm, I guess that the returned values are "picked" from the original array of points (each is a "Javascript Object" - an array of two floats). I don't see why a future implementation would want to clone these arrays.
Is this guaranteed to be the same way in the future? If so, please mention this in the README.
If not, will it be guaranteed that the floating-point values will be copied and not "calculated"? i.e. that the convex result will not have points that are "very close" to some of the original points, but not equal (due to floating-point errors).

Thanks

Is there a way to add a buffer to the concave?

Hello Lovely People,

As seen in my amazing drawing below, does anyone have an idea of how I can achieve something like it?