hypertidy/silicate

support alphahull

Opened this issue · 15 comments

mdsumner commented

Start with

#' @param xa a single row of ahull()$arcs
rc_data <- function (xa) {
  # c, r, v, theta, ...
  c <- xa[1, 1:2]
  r <- xa[1, 3]
  v <- xa[1, 4:5]
  theta <- xa[1, 6]
  angles <- alphahull:::anglesArc(v, theta)
  seqang <- seq(angles[1], angles[2], length = 100)
  x <- c[1] + r * cos(seqang)
  y <- c[2] + r * sin(seqang)
  cbind(x, y)
}
mpadge commented

I'm less sure about this. I've got alphahull code integrated with both spatialcluster and gtfs-router, so you may feel free to pilfer from there. But redoing the code of that routine is definitely on my todo list, especially as in the latter context, it really is too inefficient. The arbitrary parameter dependence (on alpha) also makes me uneasy ...

mdsumner commented

Interesting! Yes the abitrary-ness is awful - I feel like if we had more accessibility it would be easier to tweak and hone (same old story!).

mpadge commented

Note also that there are cases in which results will be very dependent on alpha, and others in which there is no sensitivity whatsoever, and results will remain identical regardless of the value. Sensitivity seems to me (entirely subjectively at the moment) to scale with numbers of points, and that further reduces general functionality of current implementation. I think there is a definite need for a general hypertidy::hyperhull (or whatever) package with efficient and reliable implementations.

mdsumner commented

Oh but https://twitter.com/mourner/status/1035092508701847552

if that exists I can't find it

mpadge commented

Cool, thanks heaps, I hadn't seen concaveman at all, so will definitely incorporate that in my stuff. Also great to see that tweet, because I've also been thinking some kind of "Delaunator" approach is likely to be the only ultimately satisfactory way.

mpadge commented

Hey, the paper behind "concaveman" is really cool, and very trivial to implement. Shall we just implement our own C++/C version for general hypertidy usage? It'd be pretty trivial and avoid referencing the stupid and sexist "concaveman" name, which is something I'd be very loathe to do

  • 👍1
mdsumner commented

It is bad

mpadge commented

Oh, really?

mdsumner commented

I mean that sexist name

  • 😄1
mpadge commented

Okay, so I had a read through the alphahull code, and it seems actually perfectly satisfactory. The main triangulation is done in (copied) fortran, so re-writing from scratch is not likely to gain that much. I think that alpha hulls are mathematically more robust - a lot more! - than the concaveman algorithm, and that's worth retaining even if it's not the fastest game in town. For me at least, that means I'll just keep on using alphahull as a standard dependency. But I'd suggest for silicate that convex hulls are a bespoke thing anyway that ought not be incorporated in any direct way. That said, I've got no idea where you're going with the above code? It's a cool interpolation of the hull arcs, but surely for general usage you just want ashape anyway? All very interesting ...

mdsumner commented

For me it's about turning bespoke types into general form, so methods on the sc_ verbs that make PATH, SC, etc work on this format

  • 👍1
mpadge commented

Other approaches to concave hulls here and here. Lots of approaches. One idea would be to implement at least one, ideally (effectively) parameter-free concave hull generator as part of decido - what do you think?

mdsumner commented

here's a re-spatializer example

f <- "https://raw.githubusercontent.com/gdsbook/book/master/data/tokyo/tokyo_clean.csv"
library(dplyr)
tokyo <- readr::read_csv(f) |> dplyr::filter(user_id == "95795770@N00") 
##|> mutate(unique_vert = as.integer(factor(paste(longitude, latitude, sep = "-"))))

## or
utokyo <- dplyr::distinct(tokyo, longitude, latitude)
a <- alphahull::ahull(utokyo$longitude, utokyo$latitude, .1)

#' @param xa a single row of ahull()$arcs
rc_data <- function (xa) {
  
  # c, r, v, theta, ...
  c <- xa[1, 1:2]
  r <- xa[1, 3]
  v <- xa[1, 4:5]
  theta <- xa[1, 6]
  angles <- alphahull:::anglesArc(v, theta)
  seqang <- seq(angles[1], angles[2], length = 100)
  x <- c[1] + r * cos(seqang)
  y <- c[2] + r * sin(seqang)
  cbind(x, y)
}

coords <- purrr::map_dfr(seq_len(nrow(a$arcs)), function(.x) tibble::as_tibble(rc_data(a$arcs[.x, , drop = FALSE])), .id = "arc")
plot(sfheaders::sfc_linestring(coords, x = "x", y = "y", linestring_id = "arc"))

image