-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathREADME.Rmd
98 lines (75 loc) · 2.97 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
---
output:
md_document:
variant: gfm
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r setup, include=FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-"
)
```
## concaveman
<!-- badges: start -->
[](https://github.com/joelgombin/concaveman/actions)
<!-- badges: end -->
A very fast 2D concave hull algorithm [in JavaScript by Vladimir Agafonkin](https://github.com/mapbox/concaveman), wrapped in R (generates a general outline of a point set).
```{r example, warning=FALSE}
library(concaveman)
library(dplyr)
library(purrr)
library(sf)
library(tmap)
data(points)
polygons <- map(unique(points$k),
~ concaveman(points[points$k %in% .,])
) %>%
map2(unique(points$k), ~ mutate(.x, k = .y)) %>%
reduce(rbind)
tm_shape(points) +
tm_dots(col = "k", size = 0.1, legend.show = FALSE) +
tm_shape(polygons) +
tm_fill(col = "k", alpha = 0.5, legend.show = FALSE) +
tm_borders() +
tm_layout(frame = FALSE)
```
### Installation
`concaveman` can be installed from CRAN:
```{r cran, echo = TRUE, eval = FALSE}
install.packages("concaveman")
```
You can also install the dev version from github:
```{r install, echo = TRUE, eval = FALSE}
devtools::install_github("joelgombin/concaveman")
```
### Usage
```{r usage, echo=TRUE}
library(concaveman)
library(dplyr)
library(purrr)
library(sf)
library(tmap)
data(points)
polygons <- concaveman(points)
polygons
polygons2 <- map(unique(points$k),
~ concaveman(points[points$k %in% .,])
) %>%
map2(unique(points$k), ~ mutate(.x, k = .y)) %>%
reduce(rbind)
tm_shape(points) +
tm_dots(col = "k", size = 0.1, legend.show = FALSE) +
tm_shape(polygons2) +
tm_fill(col = "k", alpha = 0.5, legend.show = FALSE) +
tm_borders() +
tm_layout(frame = FALSE)
```
Signature: `concaveman(points, concavity = 2, lengthThreshold = 0)`
- `points` Can be represented as a matrix of coordinates or an `sf` object.
- `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.
- `length_threshold`: 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](http://www.iis.sinica.edu.tw/page/jise/2012/201205_10.pdf) by Jin-Seo Park and Se-Jong Oh.
This implementation by Vladimir Agafonkin 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.