A simple representation of the road graph

We completely ignore one-way roads and turn restrictions.

diff --git a/Makefile b/Makefile
index 036bcda70d56be1850bac53145d49937501b5ad5..1fe49f8a6dd5a2ca491264ad9d9f5569fe05f58c 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -16,7 +16,7 @@ include $(BUILDSYS)/Maketop
 PROGS+=$(o)/leo
 CFLAGS+=$(LIBUCW_CFLAGS)
 
-LEO_MODULES=leo xml osm svg svg-icon css-parse css-lex style css dict sym sym-point sym-line sym-text map shp fixed
+LEO_MODULES=leo xml osm svg svg-icon css-parse css-lex style css dict sym sym-point sym-line sym-text map shp fixed graph
 LEO_OBJECTS=$(addprefix $(o)/, $(addsuffix .o, $(LEO_MODULES)))
 $(o)/leo: $(LEO_OBJECTS)
 

diff --git a/dict-values.t b/dict-values.t
index 1d30763e12c2fcb7a0e101288ec1604218148940..64c1dc4a89cf0e42cecb01ca8bfffcbd603c8f9d 100644 (file)
--- a/dict-values.t
+++ b/dict-values.t
@@ -17,14 +17,22 @@ italic
 left
 line
 miter
+motorway
+motorway_link
 multipolygon
 no
 none
 normal
 outer
+primary
+primary_link
 right
 round
+secondary
+secondary_link
 square
 top
 true
+trunk
+trunk_link
 yes

diff --git a/graph.c b/graph.c
new file mode 100644 (file)
index 0000000..2b1c36a
--- /dev/null
+++ b/graph.c
@@ -0,0 +1,154 @@
+/*
+ *     Hic Est Leo -- Graph and Routing
+ *
+ *     (c) 2022 Martin Mares <mj@ucw.cz>
+ */
+
+#include <ucw/lib.h>
+#include <ucw/clists.h>
+#include <ucw/mempool.h>
+
+#include <stdio.h>
+#include <math.h>
+
+#include "leo.h"
+#include "osm.h"
+#include "map.h"
+#include "graph.h"
+
+static struct mempool *graph_pool;
+static clist graph_vertices;
+
+struct graph_vertex {
+  cnode n;
+  struct osm_node *node;
+  clist edges;
+};
+
+struct graph_edge {
+  cnode n;                     // In src->edges
+  struct graph_vertex *dest;
+  struct graph_edge *twin;
+  double length;
+  struct osm_way *way;
+};
+
+static uint num_vertices;
+static uint num_edges;
+
+static struct graph_vertex *graph_lookup_vertex(struct osm_node *n)
+{
+  if (!n->vertex)
+    {
+      struct graph_vertex *v = mp_alloc_zero(graph_pool, sizeof(*v));
+      v->node = n;
+      n->vertex = v;
+      clist_init(&v->edges);
+      clist_add_tail(&graph_vertices, &v->n);
+      num_vertices++;
+    }
+  return n->vertex;
+}
+
+static struct graph_edge *graph_add_edge(struct graph_vertex *u, struct graph_vertex *v, struct osm_way *way, double length)
+{
+  struct graph_edge *e1 = mp_alloc_zero(graph_pool, sizeof(*e1));
+  struct graph_edge *e2 = mp_alloc_zero(graph_pool, sizeof(*e2));
+  num_edges++;
+
+  clist_add_tail(&u->edges, &e1->n);
+  e1->dest = v;
+  e1->twin = e2;
+  e1->length = length;
+  e1->way = way;
+
+  clist_add_tail(&v->edges, &e2->n);
+  e2->dest = u;
+  e2->twin = e1;
+  e2->length = length;
+  e2->way = way;
+
+  return e1;
+}
+
+static void graph_optimize(void)
+{
+  struct graph_vertex *v, *tmp;
+
+  CLIST_WALK_DELSAFE(v, graph_vertices, tmp)
+    {
+      uint deg = 0;
+      CLIST_FOR_EACH(struct graph_edge *, e, v->edges)
+       deg++;
+
+      if (deg == 2)
+       {
+         struct graph_edge *e1 = clist_remove_head(&v->edges);
+         struct graph_edge *f1 = clist_remove_head(&v->edges);
+         struct graph_vertex *x = e1->dest;
+         struct graph_vertex *y = f1->dest;
+         clist_remove(&e1->twin->n);
+         clist_remove(&f1->twin->n);
+         num_edges -= 2;
+
+         clist_remove(&v->n);
+         num_vertices--;
+
+         graph_add_edge(x, y, e1->way, e1->length + f1->length);
+       }
+    }
+}
+
+static bool way_is_edge(struct osm_way *w)
+{
+  osm_val_t hwy = osm_obj_find_tag(&w->o, KEY_HIGHWAY);
+  switch (hwy) {
+    case VALUE_MOTORWAY:
+    case VALUE_TRUNK:
+    case VALUE_PRIMARY:
+    case VALUE_SECONDARY:
+    case VALUE_MOTORWAY_LINK:
+    case VALUE_TRUNK_LINK:
+    case VALUE_PRIMARY_LINK:
+    case VALUE_SECONDARY_LINK:
+      return 1;
+  }
+
+  return 0;
+}
+
+static void way_add_edge(struct osm_way *w)
+{
+  struct osm_node *prev_n = NULL;
+  struct graph_vertex *prev_v = NULL;
+
+  OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
+    {
+      struct graph_vertex *v = graph_lookup_vertex(n);
+      if (prev_v)
+       {
+         double length = hypot(n->x - prev_n->x, n->y - prev_n->y);
+         graph_add_edge(prev_v, v, w, length);
+       }
+      prev_n = n;
+      prev_v = v;
+    }
+  OSM_FOR_EACH_END;
+}
+
+void graph_build(void)
+{
+  graph_pool = mp_new(65536);
+  clist_init(&graph_vertices);
+
+  CLIST_FOR_EACH(struct data_source *, ds, map_sources)
+    CLIST_FOR_EACH(struct osm_way *, w, ds->osm->obj_list[OSM_TYPE_WAY])
+      {
+       if (way_is_edge(w))
+         way_add_edge(w);
+      }
+  msg(L_INFO, "Built road graph: %u vertices, %u edges", num_vertices, num_edges);
+
+  graph_optimize();
+  msg(L_INFO, "Optimized road graph: %u vertices, %u edges", num_vertices, num_edges);
+}

diff --git a/graph.h b/graph.h
new file mode 100644 (file)
index 0000000..d3d7ba7
--- /dev/null
+++ b/graph.h
@@ -0,0 +1,12 @@
+/*
+ *     Hic Est Leo -- Graph and Routing
+ *
+ *     (c) 2022 Martin Mares <mj@ucw.cz>
+ */
+
+#ifndef _LEO_GRAPH_H
+#define _LEO_GRAPH_H
+
+void graph_build(void);
+
+#endif

diff --git a/leo.c b/leo.c
index 1e24943e67a98f681b9535274144ecf74f1ed778..1af53c0150819cd163c1a79a280aa3d5913e4c6b 100644 (file)
--- a/leo.c
+++ b/leo.c
@@ -17,6 +17,7 @@
 #include "css.h"
 #include "sym.h"
 #include "map.h"
+#include "graph.h"
 
 uns debug_dump_source, debug_dump_after_proj, debug_dump_after_scaling;
 uns debug_dump_multipolygons, debug_dump_css, debug_dump_styling, debug_dump_symbols;
@@ -120,6 +121,7 @@ int main(int argc UNUSED, char **argv)
   styles_init();
   map_load_styles();
   map_load_sources();
+  graph_build();
   map_set_scale();
   map_generalize();
 

diff --git a/osm.h b/osm.h
index cb6b24e9eb7fb139c6a4302b8cd4f3de67f65f37..d0df0c6240512d8e1bea999b2e1e32dfc584e6b4 100644 (file)
--- a/osm.h
+++ b/osm.h
@@ -53,6 +53,7 @@ struct osm_node {
    * For UTM, x is easting and y northing.
    * After map scaling, x is horizontal (left-to-right) and y vertical (top-to-bottom) on the paper.
    */
+  struct graph_vertex *vertex;
 };
 
 struct osm_way {