Comment convertir une liste de points spatiaux SF en un graphique routable

Je pense que vous pouvez le résoudre en transformant vos données en un objet igraph et en utilisant les fonctionnalités de la bibliothèque igraph . Vous devez définir les valeurs Arêtes et Vertex ainsi que les valeurs de poids . Dans igraph un Edge est un lien représentant une connexion entre deux nœuds (Source et Target). Dans ce cas, un lien est une "rue" et les points sont les nœuds.

library(igraph)
GraphResult <- data.frame(Source = c(NULL), 
                      Target = c(NULL), 
                      weight  = c(NULL))

for (i in 1:(dim(mydata)[1] - 1)) {

  TempGraphResult <- data.frame(Source = c(0), 
                                Target = c(0), 
                                weight  = c(0))

  TempGraphResult$Source[1] <- mydata$id[i]
  TempGraphResult$Target[1] <- mydata$id[i + 1]
  TempGraphResult$weight[1] <- mydata$length[i]

  GraphResult <- rbind(GraphResult, TempGraphResult) }

MyIgraph <- graph_from_data_frame(GraphResult) 

#In this case works perfectly. But if you have more weight variables and even
#additional variables for the nodes, igraph have functions for constructing the
#igraph object

distances(MyIgraph, "c", "t") #returns 3.254183. Seems correct (0.1914225*17)
SquareMatrix <- distances(MyIgraph)

#*distances() is a function from igraph that performs the routing calculations.

Il est possible de réaliser des réseaux plus complexes et de calculer des itinéraires. Par exemple, vous pouvez définir la direction des routes.

Peut-être que dodger peut gérer le problème, mais je ne suis pas sûr.

La fonction weight_streetnet n'est en réalité conçue que pour gérer les réseaux routiers réels, généralement tels que produits par les fonctions osmdata :: osmdata_sf / sp / sc () . Il peut néanmoins être modifié pour gérer des cas comme celui-ci. La chose principale nécessaire est de convertir les points en quelque chose qui connaît les arêtes entre eux, comme un objet sf :: LINESTRING :

net$d <- net$d_weighted
dodgr_dists (net, from = "c", to = "t") # 3.254183

Cela donne un seul- objet de ligne qui peut ensuite être converti au format dodgr , et les valeurs id mises en correspondance avec les bords

net$d_weighted <- as.numeric (mydata$length [1])
dodgr_dists (net, from = "c", to = "t") # 236.0481

À ce stade, dodgr aura calculé et inséré les distances directement à partir des coordonnées géographiques. Vos distances peuvent alors également être insérées et utilisées pour le routage en remplaçant les valeurs d_weighted :

net <- weight_streetnet (x, type_col = "shape_id", id_col = "id", wt_profile = 1)
net$from_id <- mydata$id [as.integer (net$from_id)]
net$to_id <- mydata$id [as.integer (net$to_id)]

Si vous voulez vraiment que vos distances représentent les distances absolues utilisées pour calculer le résultat final, puis remplacez simplement les valeurs de $ d

x <- sf::st_combine (mydata) %>%
    sf::st_cast ("LINESTRING") %>%
    sf::st_sf ()

Notez que pour des problèmes "simples" comme celui-ci, igraph sera généralement plus rapide, car il calcule les itinéraires en utilisant un seul ensemble de poids. Le seul réel avantage de dodgr dans ce contexte est la possibilité d’utiliser des "doubles pondérations" - les valeurs $ d_weighted et $ d - telles que l'itinéraire est calculé selon $ d_weighted , et les distances finales selon $d.

Si vous souhaitez l'inclure dans un flux de travail «ordonné», vous pouvez également envisager d'utiliser un mélange entre sf et tidygraph . Ce dernier offre un cadre soigné pour les réseaux / graphes, sous la forme d'une classe tbl_graph , qui sous-classe igraph (par conséquent, vous pouvez utiliser tbl_graph objets à l'intérieur de toutes les fonctions igraph comme étant un objet igraph ). Cependant, vous pouvez analyser vos nœuds et arêtes comme étant des tibbles, et utiliser des fonctions comme filter () , select () , mutate () , etc. Bien sûr, ces tibbles peuvent également contenir une colonne de liste de géométrie que nous connaissons de sf , ajoutant des informations géographiques aux nœuds et aux arêtes.

L'approche est encore loin d'être parfaite, et des améliorations seraient très Bienvenue, mais cela montre quand même une autre façon de gérer le problème.

ggplot() +
  geom_sf(data = graph %>% activate(edges) %>% as_tibble() %>% st_as_sf(), col = 'darkgrey') +
  geom_sf(data = graph %>% activate(nodes) %>% as_tibble() %>% st_as_sf(), col = 'darkgrey', size = 0.5) +
  geom_sf(data = path_graph %>% activate(edges) %>% as_tibble() %>% st_as_sf(), lwd = 1, col = 'firebrick') +
  geom_sf(data = path_graph %>% activate(nodes) %>% filter(id %in% c(from_node, to_node)) %>% as_tibble() %>% st_as_sf(), size = 2)

Tout comme dans les autres réponses, nous devons créer des arêtes entre les nœuds. Pour l'instant, je suppose que les points sont simplement reliés par ordre alphabétique. Pour l'approche tidygraph , cependant, nous semblons avoir besoin d'identifiants numériques plutôt que de caractères.

# A tibble: 1 x 1
  total_time
         [h]
1  0.2958348

Cela nous donne le tbl_graph code> objet:

path_graph %>%
    activate(edges) %>%
    as_tibble() %>%
    summarise(total_time = sum(time))

Maintenant, nous avons tout dans une structure graphique, nous pouvons sélectionner le nœud à partir duquel nous voulons acheminer, et le nœud vers lequel nous voulons acheminer, et trouver le chemin le plus court entre eux avec le temps de trajet comme variable de poids, en utilisant la fonction shortest_path de igraph . Nous travaillons maintenant simplement avec une route un-à-un ('c' à 't'), mais ce serait exactement la même chose pour un-à-plusieurs, plusieurs-à-un ou plusieurs-à-plusieurs. p>

# A tbl_graph: 18 nodes and 17 edges
#
# An undirected simple graph with 1 component
#
# Node Data: 18 x 4 (active)
     id id_chr shape_id              geometry
  <int> <chr>     <int>           <POINT [°]>
1     3 c         52421 (-46.56212 -23.52124)
2     4 d         52421 (-46.56202 -23.52118)
3     5 e         52421 (-46.56193 -23.52113)
4     6 f         52421 (-46.56183 -23.52108)
5     7 g         52421 (-46.56181 -23.52121)
6     8 h         52421 (-46.56179 -23.52134)
# … with 12 more rows
#
# Edge Data: 17 x 6
   from    to    length   speed                               geometry      time
  <int> <int>      [km]  [km/h]                       <LINESTRING [°]>       [h]
1     1     2 0.1914225      11 (-46.56212 -23.52124, -46.56202 -23.5… 0.017402…
2     2     3 0.1914225      11 (-46.56202 -23.52118, -46.56193 -23.5… 0.017402…
3     3     4 0.1914225      11 (-46.56193 -23.52113, -46.56183 -23.5… 0.017402…
# … with 14 more rows

Le chemin résultant est une liste avec les nœuds et les arêtes qui composent le chemin.

path_graph <- graph %>%
    subgraph.edges(eids = path$epath %>% unlist()) %>%
    as_tbl_graph()

Nous pouvons créer un sous-graphe du graphe original qui ne contient que les nœuds et les arêtes du chemin le plus court.

$vpath
$vpath[[1]]
+ 18/20 vertices, from e43a089:
 [1]  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20


$epath
$epath[[1]]
+ 17/19 edges from e43a089:
 [1]  3-- 4  4-- 5  5-- 6  6-- 7  7-- 8  8-- 9  9--10 10--11 11--12 12--13
[11] 13--14 14--15 15--16 16--17 17--18 18--19 19--20

# Select the node from which and to which the shortest path should be found.
from_node <- graph %>%
  activate(nodes) %>%
  filter(id_chr == "c") %>%
  pull(id)

to_node <- graph %>%
  activate(nodes) %>%
  filter(id_chr == "t") %>%
  pull(id)

# Find the shortest path between these nodes
path <- shortest_paths(
  graph = graph,
  from = from_node,
  to = to_node,
  output = 'both',
  weights = graph %>% activate(edges) %>% pull(time)
)

Ici, il se passe quelque chose que je n'aime pas. Tidygraph / igraph semble avoir une structure d'ID de nœud interne, et vous voyez que dans le sous-graphe, les colonnes from et to dans les données egdes ne correspondent pas à notre id dans les données des nœuds, mais faites simplement référence aux numéros de ligne des données des nœuds. Je ne sais pas comment résoudre ce problème.

Quoi qu'il en soit, nous avons maintenant notre chemin de «c» à «t» en tant que sous-graphe, et pouvons facilement l'analyser. Par exemple, en calculant le temps de trajet total du chemin (comme c'était la question).

# A tbl_graph: 20 nodes and 19 edges
#
# An undirected simple graph with 1 component
#
# Node Data: 20 x 4 (active)
     id id_chr shape_id              geometry
  <int> <chr>     <int>           <POINT [°]>
1     1 a         52421 (-46.56233 -23.52135)
2     2 b         52421 (-46.56222 -23.52129)
3     3 c         52421 (-46.56212 -23.52124)
4     4 d         52421 (-46.56202 -23.52118)
5     5 e         52421 (-46.56193 -23.52113)
6     6 f         52421 (-46.56183 -23.52108)
# … with 14 more rows
#
# Edge Data: 19 x 6
   from    to    length   speed                               geometry      time
  <int> <int>      [km]  [km/h]                       <LINESTRING [°]>       [h]
1     1     2 0.1914225      11 (-46.56233 -23.52135, -46.56222 -23.5… 0.017402…
2     2     3 0.1914225      11 (-46.56222 -23.52129, -46.56212 -23.5… 0.017402…
3     3     4 0.1914225      11 (-46.56212 -23.52124, -46.56202 -23.5… 0.017402…
# … with 16 more rows

# Add a numeric ID column to the nodes.
nodes <- mydata %>%
    rename(id_chr = id) %>%
    rowid_to_column("id") %>%
    select(id, id_chr, everything())

# Define the source node of each edge, and the target node of each edge.
sources <- nodes %>% slice(-n())
targets <- nodes %>% slice(-1)

# Write a function to create lines between data frames of source and target points.
pt2l <- function(x, y) { st_linestring(rbind(st_coordinates(x), st_coordinates(y))) }

# Create the edges.
edges <- tibble(
        from = sources %>% pull(id), 
        to = targets %>% pull(id), 
        length = sources %>% pull(length), 
        speed = sources %>% pull(speed_kmh),
        geometry = map2(st_geometry(sources), st_geometry(targets), pt2l)
    ) %>% st_as_sf() %>% st_set_crs(st_crs(nodes))

# Add a time column to the edges.
edges <- edges %>%
    mutate(speed = set_units(speed, "km/h")) %>%
    mutate(time = length / speed)

# Clean up the nodes data.
nodes <- nodes %>%
    select(-length, -speed_kmh)

# Create the tbl_graph object out of the nodes and edges.
# Providing the edges as sf object is problematic for tidygraph, unfortunately.
# Therefore, we have to provide them as a tibble.
graph <- tbl_graph(nodes = nodes, edges = as_tibble(edges), directed = FALSE)

Mais il est également facile de le tracer , avec des informations géographiques préservées (simplement en exportant les nœuds et les arêtes en tant qu'objets sf).

# Load libraries.
library(tidyverse)
library(sf)
library(tidygraph)
library(igraph)
library(units)

plot

Un article de blog r-spatial pourrait être publié sur cette approche tidygraph-sf;)