mpadge / spatialcluster

spatially-constrained clustering in R
https://mpadge.github.io/spatialcluster/
30 stars 6 forks source link

Remove tripack dependency #25

Closed mpadge closed 3 years ago

mpadge commented 3 years ago

It's ACM-licensed, which among other restrictions prohibits commercial use. It's only used to generate lists of triangularion neighbours anyway, so can replace it with deldir which is GPL-3. This is independent of #5, which also still has to be addressed.

mdsumner commented 3 years ago

geometry is much faster than deldir, but you need to build the edges still - I haven't explored this thoroughly, and it uses more memory but worth a look ;0

d <- 
  data.frame(x = runif(1000), y = runif(1000))

## candidate replace function for edges from tripack neighbours
gm_edges <- function(x) {
 gm <- geometry::delaunayn(as.matrix(x))
 ## edges are pairs of triples
 dplyr::arrange(dplyr::distinct(tibble::as_tibble(matrix(t(rbind(gm[,1:2], gm[,2:3], gm[,c(3, 1)], 
                                                  gm[,2:1], gm[,3:2], gm[,c(1, 3)])), ncol = 2L, byrow = TRUE, dimnames = list(NULL, c("from", "to")))
                                   )), .data$from, .data$to)
}

## just the edge-creation from tripack neighbours as per scl_edges_tri 
tp_edges <- function(x) {
  x <- setNames(as.data.frame(x), c("x", "y"))
  tp <- tripack::tri.mesh(x)
  nbs <- tripack::neighbours(tp)
  n <- length (nbs)
  edges <- lapply (seq (n), function (i)
    cbind (i, nbs [[i]])) %>%
    do.call (rbind, .)
 tibble::tibble (from = edges [, 1],
                           to = edges [, 2])

}
library(magrittr)
bench::mark(gm_edges(d), tp_edges(d))
#> Warning: Some expressions had a GC in every iteration; so filtering is disabled.
#> # A tibble: 2 x 6
#>   expression       min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr>  <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 gm_edges(d)   16.6ms   18.3ms     47.4    23.28MB     1.97
#> 2 tp_edges(d)    125ms  133.1ms      6.95    1.02MB     6.95

Created on 2021-11-11 by the reprex package (v2.0.1)

mdsumner commented 3 years ago

this seems better

## candidate replace function for edges from tripack neighbours
gm_edges <- function(x) {
 gm <- geometry::delaunayn(as.matrix(x))
 ## edges are pairs of triples
 m0 <- rbind(gm[,1:2], gm[,2:3], gm[,c(3, 1)])
 m1 <- rbind(m0, m0[,2:1])
 m <- matrix(t(m1), ncol = 2L, byrow = TRUE, dimnames = list(NULL, c("from", "to")))
 dplyr::arrange(dplyr::distinct(tibble::as_tibble(m)), .data$from, .data$to)
}
mpadge commented 3 years ago

I've ditched all that for now anyway, in favour of sf::st_intersect bollocks, which is as close to unusable as possible while still maintaining marginal usability. It kinda works, but would be good to revert to a proper method down the line

mdsumner commented 3 years ago

ah right yeh