Generarea unei rețele de navigație triunghiulare din hexagoane H3 în R

Introducere

O plasă de navigare este o structură de date folosită pentru a ajuta la identificarea traseului în jurul obstacolelor. Folosit inițial pentru jocuri video și robotică, putem aplica și conceptul acestei rețele de navigație la mișcarea animalelor prin peisaj, folosind metode precum FEEMS.

Luați în considerare următorul peisaj:

Găsirea unei căi de la punctul de plecare s la punctul de gol t este o provocare din punct de vedere computațional, deoarece există multe rute posibile pe care le-ar putea lua între aceste două puncte finale, iar spațiul posibil este atât de mare încât poate fi dificil să se calculeze eficient o cale rapidă. În schimb, putem simplifica spațiul prin micșorarea posibilelor locații din peisaj la o serie de noduriiar nodurile învecinate la care vă puteți muta sunt conectate prin marginile. Rezultatul plasă de obicei arată ca o grămadă de triunghiuri care se suprapun peisajului:

În această postare pe blog, voi discuta cum să construiți o astfel de plasă folosind fișiere de formă din lumea reală și h3 bibliotecă în R, care teselează hexagoane de pe tot globul la mai multe rezoluții. Am căutat și alternative, cum ar fi dggridR, dar am găsit că alte pachete nu sunt satisfăcătoare din mai multe motive (în special viteza).

Pentru început, de ce h3 și de ce hexagoane? Răspunsul la aceasta este că este foarte convenabil să existe un sistem de grilă care să poată fi utilizat pentru orice loc de pe planetă, iar având o varietate de rezoluții diferite, este convenabil să analizezi datele spațiale la scări variind de la nivel de continent până la oraș. nivel. În special, hexagoanele au o proprietate frumoasă în care distanța de la centrul unui hexagon până la hexagonul său vecin este aproximativ egală.

Exemplu lucrat

Mai întâi, încărcați câteva pachete necesare, inclusiv h3jsrdespre care am găsit o interfață mai frumoasă decât alte biblioteci h3 pentru R.

library(tidyverse)
library(h3jsr)
library(sf)
requireNamespace("maps")

Pentru exemplul de astăzi, vom folosi o hartă simplă care arată unele județe din zona golfului San Francisco (SFBA). Trebuie să dezactivăm geometria sferică sf deoarece la această scară, totul este oricum aproximativ plan și există unele probleme cu geometriile furnizate în
maps pachet.

sf::sf_use_s2(FALSE)
bay_counties <- c(“alameda”, “contra costa”, “marin”, “napa”, “san mateo”, “santa clara”, “solano”, “sonoma”, “san francisco”)
sfba <- maps::map(‘county’, paste0(“california,”, bay_counties), fill = TRUE, plot = FALSE) %>%
st_as_sf() %>%
st_transform(4326) %>%
st_make_valid()
ggplot(sfba, aes(fill = ID)) +
geom_sf() +
theme_minimal()

În continuare, trebuie să găsim hexagoanele h3 care intersectează acest fișier de formă al SFBA. Aș dori ca hexagoanele mele să acopere câțiva kilometri pătrați, iar aceasta corespunde aproximativ cu rezoluția 7 în h3. Mai întâi trebuie să dizolvăm caracteristicile individuale (adică să eliminăm frontierele interne), apoi să folosim polygon_to_cells funcția de a identifica celulele h3 corecte care se intersectează cu granițele noastre SFBA.

dissolved_sfba <- summarise(sfba, geom = st_union(geom))
ids <- polygon_to_cells(dissolved_sfba, res = 7)((1))
head(ids)

## (1) "872830311ffffff" "872830925ffffff" "87283154dffffff" "872836a62ffffff"
## (5) "872830314ffffff" "872830928ffffff"

Trasează aceste hexagonale h3 pentru a-ți face o idee despre cu ce lucrăm.

ggplot(cell_to_polygon(ids)) +
  geom_sf() +
  theme_minimal()

Pentru fiecare ID de celulă, trebuie să îi identificăm vecinii folosind get_disk
functioneaza cu distance = 1. Documentația acestei funcții spune:

Prima adresă returnată este adresa de intrare, restul urmează în spirală în sens invers acelor de ceasornic.

Acesta este perfect pentru cazul nostru de utilizare. Luăm hexagonul de origine și îi găsim centrul. Apoi faceți același lucru pentru doi dintre vecinii săi și construiți un triunghi între centrele acestor trei hexuri.

id <- ids(1)
disk <- get_disk(id, ring_size = 1)((1))
first_three <- disk(1:3)
first_triangle <- cell_to_point(first_three, simple = TRUE) %>%
st_combine() %>%
st_cast(“POLYGON”) %>%
st_as_sf()
ggplot(first_triangle) +
geom_sf() +
theme_minimal()

Putem repeta această procedură pentru a construi triunghiuri între centrele tuturor hexurilor din jurul hexului nostru de origine. Excludem punctul de origine din buclă și adăugăm, de asemenea, primul hex vecin din inel, altfel vom avea doar cinci triunghiuri, nu șase, în jurul hexului de origine.

wrapped_vec <- c(disk(-1), disk(2))
results <- list()
for (ii in 1:(length(wrapped_vec) - 1)) {
results((ii)) <- cell_to_point(c(id, wrapped_vec(ii), wrapped_vec(ii+1)), simple = TRUE) %>%
st_combine() %>%
st_cast(“POLYGON”) %>%
st_as_sf()
}
tris <- bind_rows(results) %>%
mutate(idx = 1:6)
ggplot(tris, aes(fill = factor(idx))) +
geom_sf() +
theme_minimal()

Putem construi din această muncă inițială pentru a scrie o funcție care va lua un h3 id ca intrare și returnează o plasă triunghiulară.

to_triangles <- function(id) {
  disk <- get_disk(id, ring_size = 1)((1))
  wrapped_vec <- c(disk(-1), disk(2))
  lapply(1:(length(wrapped_vec) - 1), function(ii) {
    tri <- c(id, wrapped_vec(ii), wrapped_vec(ii + 1))
    cell_to_point(tri, simple = TRUE) %>%
      st_combine() %>%
      st_cast("POLYGON") %>%
      st_as_sf()
  }) %>% bind_rows()
}

Utilizare lapply şi bind_rows a construi un întreg sf cadru de date care conține întreaga rețea triunghiulară. Există o mulțime de duplicate, dar le putem folosi doar distinct pentru a scăpa de acestea. (Eu folosesc
parallel::mclapply aici, deoarece acest pas poate fi puțin lent.)

all_tris <- parallel::mclapply(ids, to_triangles, mc.cores = 8) %>%
  bind_rows() %>%
  distinct()
ggplot(all_tris) +
geom_sf(fill = “white”) +
theme_minimal()

Cititorii atenți vor observa că aceste rețele triunghiulare vor include noduri care se află în apă sau în județele învecinate, deoarece hexurile de la marginea fișierului nostru de formă SFBA vor avea inevitabil câțiva vecini care nu sunt conținute în fișierul de formă SFBA.

Deși nu a fost necesar să fac acest lucru pentru analiza mea, acestea pot fi îndepărtate cu ușurință folosind un predicat binar, cum ar fi st_containspentru a nu include niciodată nicio margine care intră în apă sau iese în alt mod din limita fișierului de formă.

contain_result <- st_contains(dissolved_sfba, all_tris)
contained_mesh <- all_tris(unlist(contain_result), )
ggplot() +
  geom_sf(data = dissolved_sfba, fill = "pink") +
  geom_sf(data = contained_mesh, fill = "white") +
  theme_minimal()

Această plasă de navigare poate fi acum salvată folosind funcții precum
write_sf și utilizat în software-ul de analiză din aval.

Exerciții

1. Cum putem evita crearea de plase triunghiulare duplicat?
2. Folosiți a compact reprezentare pentru a genera o plasă triunghiulară cu interioare simplificate.

comp <- cell_to_polygon(h3jsr::compact(ids), simple = FALSE)
ggplot() +
geom_sf(data = dissolved_sfba, fill = NA) +
geom_sf(data = comp, fill = NA, color = “red”) +
theme_minimal()