如何使用sf准确计算球形 Voronoi 图?

11
我希望用世界地图和 Voronoi 图案制作一个球形地图(不是它的投影),类似于 this using D3.js,但使用 R 语言。
据我所知(“Goodbye flat Earth, welcome S2 spherical geometry”),现在的 sf 包完全基于 s2 包,应该能够满足我的需求。但我认为我没有得到预期的结果。以下是一个可重复的示例:
library(tidyverse)
library(sf)
library(rnaturalearth)
library(tidygeocoder)

# just to be sure
sf::sf_use_s2(TRUE)

# download map 
world_map <- rnaturalearth::ne_countries(
                scale = 'small', 
                type = 'map_units',
                returnclass = 'sf')

# addresses that you want to find lat long and to become centroids of the voronoi tessellation 
addresses <- tribble(
~addr,
"Juneau, Alaska" ,
"Saint Petersburg, Russia" ,
"Melbourne, Australia" 
)

# retrive lat long using tidygeocoder
points <- addresses %>% 
          tidygeocoder::geocode(addr, method = 'osm')

# Transform lat long in a single geometry point and join with sf-base of the world
points <- points %>% 
          dplyr::rowwise() %>% 
          dplyr::mutate(point = list(sf::st_point(c(long, lat)))) %>% 
          sf::st_as_sf() %>% 
          sf::st_set_crs(4326)

# voronoi tessellation
voronoi <- sf::st_voronoi(sf::st_union( points ) ) %>% 
     sf::st_as_sf() %>% 
     sf::st_set_crs(4326)

# plot
ggplot2::ggplot() +
    geom_sf(data = world_map,
            mapping = aes(geometry = geometry), 
            fill = "gray95") +
    geom_sf(data = points,
            mapping = aes(geometry = point),
            colour = "red") +
    geom_sf(data = voronoi,
            mapping = aes(geometry = x),
            colour = "red",
            alpha = 0.5)  

enter image description here

整个南极洲应该比其他两点更靠近墨尔本。我错过了什么?如何使用sf在球面上计算 Voronoi?

1
我没有看到任何新的内容:文档上仍然有相同的警告:https://r-spatial.github.io/sf/articles/sf7.html。或许可以在[S2邮件列表](https://groups.google.com/g/s2geometry-io/search?q=voronoi)上询问? - Ben Bolker
嗨Ben,很高兴你回来了!也许我应该重新提出我的问题,改为“如何真正计算...使用R”(与“使用sf”不同),或者干脆开一个新的问题。 - Arthur Welle
从这里(https://dev59.com/m3RB5IYBdhLWcg3wtJGF)我尝试过,但没有成功(因为我的编码能力有限),调用Fortran子程序(https://people.sc.fsu.edu/~jburkardt/f_src/sphere_voronoi/sphere_voronoi.html),并简单尝试了使用RcppCGAL调用CDAL(https://doc.cgal.org/latest/Triangulation_3/index.html)。也许我应该再试一下使用reticulate + SciPy(https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.SphericalVoronoi.html)的方法。 - Arthur Welle
无论如何,我只能看到通过使用其他语言(Fortran、C、Python、JavaScript/D3)来前进的方式,而我对这些语言都不熟悉... - Arthur Welle
我不知道sf是什么,但你可以尝试使用 sphericalTessellation 包。 - Stéphane Laurent
3个回答

9

这是一种基于Stéphane Laurent方法的方法,但输出sf对象。

让我们获取所有世界首都的sf对象:

library(sf)
#> Linking to GEOS 3.9.3, GDAL 3.5.2, PROJ 8.2.1; sf_use_s2() is TRUE

capitals <- do.call(rbind,
  subset(maps::world.cities, capital == 1, select = c("long", "lat")) |>
  as.matrix() |>
  asplit(1) |>
  lapply(st_point) |>
  lapply(st_sfc) |>
  lapply(st_sf, crs = 'WGS84')) |>
  `st_geometry<-`('geometry') |>
  cbind(city = subset(maps::world.cities, capital == 1, select = c("name")))

capitals
#> Simple feature collection with 230 features and 1 field
#> Geometry type: POINT
#> Dimension:     XY
#> Bounding box:  xmin: -176.13 ymin: -51.7 xmax: 179.2 ymax: 78.21
#> Geodetic CRS:  WGS 84
#> First 10 features:
#>           name               geometry
#> 1       'Amman    POINT (35.93 31.95)
#> 2    Abu Dhabi    POINT (54.37 24.48)
#> 3        Abuja      POINT (7.17 9.18)
#> 4        Accra      POINT (-0.2 5.56)
#> 5    Adamstown  POINT (-130.1 -25.05)
#> 6  Addis Abeba     POINT (38.74 9.03)
#> 7        Agana   POINT (144.75 13.47)
#> 8      Algiers     POINT (3.04 36.77)
#> 9        Alofi POINT (-169.92 -19.05)
#> 10   Amsterdam     POINT (4.89 52.37)

我们的世界地图:

world_map <- rnaturalearth::ne_countries(
  scale = 'small', 
  type = 'map_units',
  returnclass = 'sf')

现在我们使用 Stéphane Laurent 的方法来将球体网格化,然后将投影反转回球面坐标。这允许回到 sf,但我们必须小心地拆分任何跨越 180/-180 经度线的对象。
voronoi <- capitals %>%
  st_coordinates() %>%
  `*`(pi/180) %>%
  cbind(1) %>%
  pracma::sph2cart() %>%
  sphereTessellation::VoronoiOnSphere() %>%
  lapply(\(x) rbind(t(x$cell), t(x$cell)[1,])) %>%
  lapply(\(x) {
    n <- nrow(x) - 1
    lapply(seq(n), function(i) {
      a <- approx(x[i + 0:1, 1], x[i + 0:1, 2], n = 1000)
      b <- approx(x[i + 0:1, 1], x[i + 0:1, 3], n = 1000)
      d <- cbind(a$x, a$y, b$y) |> pracma::cart2sph() 
      d <- d[,1:2] * 180/pi
      if(max(abs(diff(d[,1]))) > 180) {
        s <- which.max(abs(diff(d[,1])))
        d <- list(d[1:s, ], d[(s+1):nrow(d),])
      }
      d })}) |>
  lapply(\(x) {
    st_geometrycollection(lapply(x, \(y) {
    if(class(y)[1] == "list") {
      st_multilinestring(y)
      } else {
        st_linestring(y)
      }}))}) %>%
  lapply(st_sfc) %>%
  lapply(st_sf, crs = 'WGS84') %>%
  {do.call(rbind, .)} %>%
  `st_geometry<-`('geometry')

现在我们有了Voronoi网格作为一个sf对象,所以我们可以使用ggplot来绘制它。
library(ggplot2)

ggplot() +
  geom_sf(data = world_map, fill = "cornsilk", color = NA) +
  geom_sf(data = voronoi, color = "gray40") +
  geom_sf(data = capitals, color = "black", size = 0.2) + 
  coord_sf(crs = "ESRI:53011") +
  theme(panel.background = element_rect(fill = "lightblue"))

enter image description here


附录

虽然上述解决方案适用于在整个地球上绘制镶嵌图案,但如果我们只想得到陆地区域的多边形,可以按照以下步骤进行:

首先,我们从世界地图中合并所有陆地区域。

wm <- st_make_valid(world_map) |> st_union()

现在我们得到了Voronoi图块顶点的坐标:
pieces <- capitals %>%
  st_coordinates() %>%
  `*`(pi/180) %>%
  cbind(1) %>%
  pracma::sph2cart() %>%
  sphereTessellation::VoronoiOnSphere() %>%
  lapply(\(x) rbind(t(x$cell), t(x$cell)[1,])) %>%
  lapply(pracma::cart2sph) %>%
  lapply(\(x) x[,1:2] * 180/pi)

现在我们需要找到跨越-180 / 180线的瓦片。
complete <- pieces %>% sapply(\(x) abs(diff(c(min(x[,1]), max(x[,1])))) < 180)

现在我们将它们拆分并转换为多边形,找到它们与世界地图的交集:

orphans <- pieces[!complete] %>%
  lapply(\(x) {x[,1] + 180 -> x[,1]; x}) %>%
  lapply(\(x) st_polygon(list(x)) |> st_sfc(crs = "WGS84")) %>%
  lapply(\(x) {
    west <- st_intersection(x, matrix(c(-180, -0.001, -0.001, -180, -180, 
                                 -89, -89, 89, 89, -89), ncol = 2) |>
                                list() |> st_polygon() |> st_sfc(crs = "WGS84"))
    east <- st_intersection(x, matrix(c(0, 180, 180, 0, 0, 
                                        -89, -89, 89, 89, -89), ncol = 2) |>
                              list() |> st_polygon() |> st_sfc(crs = "WGS84"))
    west <- st_coordinates(west)[,1:2]
    east <- st_coordinates(east)[,1:2]
    west[,1] <- west[,1] + 180
    east[,1] <- east[,1] - 180
    w <- st_polygon(list(west)) |> st_sfc(crs = "WGS84") |> st_intersection(wm)
    e <- st_polygon(list(east)) |> st_sfc(crs = "WGS84") |> st_intersection(wm)
    st_combine(st_union(e, w))
  }) %>%
  lapply(st_sf) %>%
  lapply(\(x) { if(nrow(x) > 0) { st_segmentize(x, 100000) } else {
    st_point(matrix(c(0, 0), ncol = 2)) |> 
      st_sfc(crs = "WGS84") |> st_sf()
  }
  }) %>% 
  lapply(\(x) `st_geometry<-`(x, 'geometry')) %>%
  {do.call(rbind, .)} %>%
  cbind(city = capitals$name[!complete])

我们可以这样对非环绕瓦片进行交叉处理:
non_orphans <- pieces %>%
  subset(complete) %>%
  lapply(list) %>%
  lapply(st_polygon) %>%
  lapply(st_sfc, crs = "WGS84") %>%
  lapply(st_intersection, y = wm) %>%
  lapply(st_sf) %>%
  lapply(\(x) { if(nrow(x) > 0) { st_segmentize(x, 100000) } else {
    st_point(matrix(c(0, 0), ncol = 2)) |> 
      st_sfc(crs = "WGS84") |> st_sf()
  }
  }) %>%
  lapply(\(x) `st_geometry<-`(x, 'geometry')) %>%
  {do.call(rbind, .)} %>%
  cbind(city = capitals$name[complete])

最后,我们将所有这些绑定到一个单独的 sf 对象中:
voronoi <- rbind(orphans, non_orphans)
voronoi <- voronoi[!st_is_empty(voronoi),]
voronoi <- voronoi[sapply(voronoi$geometry, \(x) class(x)[2] != "POINT"),]

现在我们准备好绘图了。让我们定义一个调色板函数,其结果类似于你提供的示例链接:
f <- colorRampPalette(c("#dae7b4", "#c5b597", "#f3dca8", "#b4b6e7", "#d6a3a4"))

我们还将创建一个背景“地球仪”和一个平滑的网格,以在我们的地图上绘制,就像示例中一样。
grid <- lapply(seq(-170, 170, 10), \(x) rbind(c(x, -89), c(x, 0), c(x, 89))) |>
  lapply(st_linestring) |>
  lapply(\(x) st_sfc(x, crs = "WGS84")) |>
  lapply(\(x) st_segmentize(x, dfMaxLength = 100000)) |>
  c(
    lapply(seq(-80, 80, 10), \(x) rbind(c(-179, x), c(0, x), c(179, x))) |>
      lapply(st_linestring) |>
      lapply(\(x) st_sfc(x, crs = "WGS84"))
  ) |>
  lapply(st_sf) |>
  lapply(\(x) `st_geometry<-`(x, 'geometry')) %>%
  {do.call(rbind, .)}

globe <- st_polygon(list(cbind(c(-179, 179, 179, -179, -179), 
                               c(-89, -89, 89, 89, -89)))) |> 
  st_sfc(crs = "WGS84") |> 
  st_segmentize(100000)

最终结果是一个忠实的链接示例的sf版本。
ggplot() +
  geom_sf(data = globe, fill = "#4682b4", color = "black") +
  geom_sf(data = voronoi, color = "black", aes(fill = city)) +
  geom_sf(data = capitals, color = "black", size = 1) + 
  geom_sf(data = grid, color = "black", linewidth = 0.2) +
  coord_sf(crs = "ESRI:53011") +
  scale_fill_manual(values = f(nrow(voronoi))) +
  theme(panel.background = element_blank(),
        legend.position = "none",
        panel.grid = element_blank())

enter image description here

2023-06-24创建,使用reprex v2.0.2


3
太棒了!Stackoverflow的R英雄Stéphane Laurent和Allan Cameron一起贡献代码,真是令人惊叹!谢谢你们!我希望我能把奖励分给你们两个。 - Arthur Welle
多么有趣的附录啊!谢谢你,艾伦! - Arthur Welle

8
我不知道“sf”,但你可以使用“sphereTessellation”包代替。
library(pracma) # for the sph2cart function
library(maps)
data(world.cities)
data(worldMapEnv)

world <- map("world", plot = FALSE)
countries <- sph2cart(cbind(world$x*pi/180, world$y*pi/180, 1))

capitals_ll <- as.matrix(
    subset(world.cities, capital == 1, select = c("long", "lat"))
) * pi / 180
capitals <- sph2cart(cbind(capitals_ll, 1))


library(rgl)
open3d(windowRect = 50 + c(0, 0, 512, 512), zoom = 0.7)
sphereMesh <- Rvcg::vcgSphere()
shade3d(sphereMesh, color = "cyan", polygon_offset = 1)
lines3d(countries)
points3d(capitals, size = 4, color = "red")
snapshot3d("world.png", webshot = FALSE)

enter image description here

library(sphereTessellation)
vor <- VoronoiOnSphere(capitals)
open3d(windowRect = 50 + c(0, 0, 512, 512), zoom = 0.7)
plotVoronoiOnSphere(
    vor, colors = "white", edges = TRUE, ecolor = "green",
    sites = TRUE, scolor = "red", polygon_offset = 1
)
lines3d(countries)
snapshot3d("world_voronoi.png", webshot = FALSE)

enter image description here

但是我不知道我们如何将Voronoï单元剪裁到各个国家。

非常感谢你,Stéphane!你的包裹做得太棒了! - Arthur Welle
我成功地创建了一个借鉴了你的方法的sf解决方案,Stephane。我通过使用st_intersection解决了你遇到的问题。 - Allan Cameron
@StéphaneLaurent "tessellation"是从VoronoiOnSphere产生的输出,所以它与你产生的那个除了我所知道的最好方式之外,在sf具有周期性。尽管可以将网格映射到一个球体上,但在所使用的坐标系统边界处总会存在不连续性。在我回答中使用的投影中,不连续性出现在国际日期线(180度经度)处。在这种情况下,这并不太重要,因为很少有陆地跨越这条线(俄罗斯东部和南极洲的东端)。 - Allan Cameron
@StéphaneLaurent 实际上,这种不连续性有点麻烦,因为你需要确保跨越日期线的任何内容都被手动拆分成片段。这就是我的代码如此冗长的主要原因。 - Allan Cameron
@AllanCameron 啊,我没看到你用我的包裹。 - Stéphane Laurent
显示剩余4条评论

6

(这个答案并没有告诉你如何操作,但是告诉了你出了什么问题。)

当我运行这段代码时,我得到了以下警告:

警告信息:在 st_voronoi.sfc(sf::st_union(points)) 中: st_voronoi 无法正确地三角化经度/纬度数据。

从挖掘代码来看,这似乎是一个已知的限制。查看CPL_geos_voronoi的C++代码,它直接调用了一个用于构建Voronoi图的GEOS方法。如果没有人告诉开发者特定功能很有用,那么它们就不会被优先考虑... 值得注意的是,GEOS不会自动执行考虑球形几何的计算,这并不让我感到惊讶。尽管S2代码库在多个位置提到了Voronoi图,但看起来没有一个可以直接替换GEOS算法的解决方案... 在其他语言中有各种实现用于球形Voronoi图(例如Python),但可能需要将它们移植到R(或C++)...请考虑打开sf issue以表明您需要此功能。
如果我真的需要这样做,我可能会尝试找出如何从R中调用Python代码(将数据从“sf”格式导出到Python所需的任何格式,然后重新导入结果到适当的“sf”格式...)
打印“sf :: st_voronoi.sfc”的代码:
function (x, envelope = st_polygon(), dTolerance = 0, bOnlyEdges = FALSE) 
{
    if (compareVersion(CPL_geos_version(), "3.5.0") > -1) {
        if (isTRUE(st_is_longlat(x))) 
            warning("st_voronoi does not correctly triangulate longitude/latitude data")
        st_sfc(CPL_geos_voronoi(x, st_sfc(envelope), dTolerance = dTolerance, 
            bOnlyEdges = as.integer(bOnlyEdges)))
    }
    else stop("for voronoi, GEOS version 3.5.0 or higher is required")
}

换句话说,如果GEOS版本低于3.5.0,则操作将完全失败。如果它是>= 3.5.0( sf ::: CPL_geos_version()报告我有版本3.8.1),并且正在使用长纬度数据,则应该发出警告(但仍会进行计算)。
第一次运行时,我没有收到警告;我检查了 options(“warn”)设置为-1(抑制警告)。我不确定为什么 - 从干净的会话中运行确实给了我警告。也许管道中的某些内容(例如rnaturalearth告诉我需要安装rnaturalearthdata包)意外设置了选项?

感谢您对这个主题的研究。目前我同意您所强调的两种方法:a) 在Git上开一个问题;b) 使用reticulate + SciPy(尽管我还没有足够的知识来做到这一点)。谢谢! - Arthur Welle
如果这个“解决”(有点)了你的问题,我们鼓励你点击复选标记来接受它(尽管你可以一直保持开放状态,希望其他人会出现并提供完整的解决方案而不仅仅是诊断...) - Ben Bolker
1
是的,我不太清楚在这种情况下应该遵循什么样的stackoverflow礼仪(我是这个网站上的新手)。我想我会在git上发布一个问题,并附上这里的链接,然后再开放几天。 - Arthur Welle
未来参考:到目前为止,s2不提供Voronoi计算。 - Arthur Welle
你可以无限期地保持它开放。如果您愿意,您也可以(1)取消该勾选标记(如果问题没有被接受的答案可能更容易引起关注),(2)如果有人提供了更好的答案(包括您自己),则将勾选标记移到其他答案上。 - Ben Bolker

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接