=Paper=
{{Paper
|id=Vol-2020/paper7
|storemode=property
|title=Automatic Generation of Meaningful Virtual Direction Markers in Road Networks 
|pdfUrl=https://ceur-ws.org/Vol-2020/paper7.pdf
|volume=Vol-2020
|authors=Jörg Roth
|dblpUrl=https://dblp.org/rec/conf/lbas/Roth17
}}
==Automatic Generation of Meaningful Virtual Direction Markers in Road Networks ==
<pdf width="1500px">https://ceur-ws.org/Vol-2020/paper7.pdf</pdf>
<pre>
    Automatic Generation of Meaningful Virtual Direction
                Markers in Road Networks

                                           Jörg Roth

           Department of Computer Science, Nuremberg Institute of Technology,
                      Kesslerplatz 12, 90489 Nuremberg, Germany
                         Joerg.Roth@th-nuernberg.de



           Abstract. Direction markers are widely used in real road networks. They
       show directions to important destinations such as cities, industrial areas, airports
       or touristic sights. In this paper, we introduce virtual direction markers that only
       exist digitally in, e.g., a navigation application. We present an approach to auto-
       matically compute and place such markers without additional manual editing.
       Our assumption: a direction marker resides on an optimal path from an arbitrary
       start to the respective target. However, a naïve approach would place confusing
       or misleading markers. Thus, we add the concept of cropping that removes un-
       wanted markers. Finally, we introduce the notion of relevant crossings and de-
       fault links that additionally improve direction markers.


       Keywords: Road network, Direction marker, Navigation


1      Introduction

Direction markers in road networks are widely known (Fig. 1). They indicate highway
exits or suggest turning at a crossing for a certain destination. Real direction markers
are placed by, e.g., road traffic departments. These have local knowledge about inter-
esting destinations (e.g. cities, important sights) and know useful locations to place
these signs [9]. In addition to standardized traffic signs, we also observe traditional and
historic signs, very often for pedestrians [8].
   In this paper, we introduce virtual direction markers that only appear as data in, e.g.,
a navigation application. Our virtual direction markers are automatically computed
from an existing road network, without additional manual editing. This enables to com-
pute meaningful direction markers even on large road networks with many millions of
links and crossings.
   Virtual direction markers are useful for several applications:

 For a trip that is guided by a navigation application, direction markers placed on a
  map may indicate a crossing situation more clearly.
 For non-guided, explorative driving, meaningful directions markers may show in-
  teresting new destination options for the driver.
94                                                                               LBAS 2017




 Fig. 1. Examples of real direction markers


 An automatically generated driver's logbook may contain textual trip entries that are
  sequences of turns and straight driving. The turns may be expressed by direction
  markers, e.g. "10 km straight, turned left to 'Nuremberg', 5 km straight, turned right
  to 'New Museum of Arts'…".
In addition, such markers can be placed on automatically generated maps that e.g. are
printed.
   We distinguish confirmative und distinctive direction markers. The difference is,
whether the driver is confirmed to stay on the current route or whether the crossing
distinguishes between different targets and tells a driver to turn or exit. Typical con-
firmative markers are signs placed on highways that indicate, the distance to certain
city 'straight ahead' is, e.g., 100 km. In contrast, distinctive direction markers require a
driver to make a certain decision, e.g. to turn left for city A, or to turn right for city B.
For a typical application, distinctive markers are more interesting.
   Our goal is to compute a set of confirmative and distinctive direction markers for
every crossing in the road network and for any interesting destination. In addition to the
algorithmic problem, we have to face some questions to perform this task:

 What are suitable destinations?
 At which crossing are direction markers useful for a certain destination?
 How do we formally separate distinctive from confirmative markers?
As the computation may be part of a mastering step of geo data (e.g. for a navigation
application) it is not time-critical. However, an approach must be suitable for many
millions of crossings and destinations.
   The following approach is based on a long research in the area of untraditional nav-
igation problems. Corresponding solutions are integrated into the HomeRun platform
[2], more specifically into the donavio component for navigational functions [3]. Be-
sides the traditional point-to-point route planning, donavio covers a wide range of fur-
ther solutions:
Ortsbezogene Anwendungen und Dienste 2017                                                    95


 computation of all alternative routes that hold a certain cost limit [7],
 computation of suitable stop-over-points of a certain type (e.g. fuel station) that
  downgrade the optimal route not too much [7],
 computation of m  n optimal routes between m starts and n targets without the need
  to compute all m  n individual paths [5],
 computation of traveling salesman routes on real road networks (i.e. the distance
  between stop-over-points are not approximated, but real costs) [5],
 computation of isochrones, i.e. the area of targets that can be reached within a given
  cost limit; also multi-isochrones (i.e. from multiple starts),
 prediction of a target from a partially observed route [4],
 prediction of a driven route from imprecise position sensors based on the optimal
  route assumption [6].
As a new donavio function, we want to enrich the road network to carry direction in-
formation.


2      Computing Virtual Direction Markers

2.1    A First Approach
We start with some definitions. Let V denote the set of crossings and E the set of (di-
rected) links between crossings. Further let out(v) denote all outgoing links from and
in(v) all incoming links to a crossing v.
   For an eE, vbegin(e) denotes the start crossing, vend(e) the end crossing. We simply
write e=(vbegin(e), vend(e)). In addition we call e =(vend(e), vbegin(e)) the reverse link of e.
   Links have costs, denoted by c(e) or c(v1, v2). Costs are the measure that a certain
direction wants to minimize. In other words: following a certain direction marker, the
total costs to the direction is less than going via another direction. Typical costs are
driving time or driving distance.
   Finally, we need a set of interesting direction targets, we call landmarks. Let M de-
note the set of all landmarks. We assume M neither is a subset of E nor V, but there is
an obvious relation lm(m)V for mM that maps a landmark m to a subset of crossings.
For area-like landmarks (e.g. cities), a reasonable lm identifies all crossings within the
surface area of m.
   We are now looking for all direction markers for all links. For a certain link e we
call dir(e)M the set of these markers. We can express the basic idea of the first ap-
proach to compute dir(e) as follows:

               All direction markers to a landmark reside on an optimal
                  route from a virtual starting point to this landmark.

Here, 'virtual starting point' means: we can choose any crossing that has no actual re-
lation to the landmark or to the respective link. We also do not actually drive from this
96                                                                             LBAS 2017


starting point. However, all links of the corresponding route are directed to the land-
mark, thus can create our direction markers.
   A naïve approach would compute optimal routes from all crossings to all landmarks.
This however, would be too time-consuming. A first simplification is thus: we reverse
the direction of route computation and start from the landmarks. Important: we do not
reverse the driving direction, but only the ordering of visiting the links. This in partic-
ular is important, as links in road networks are directed and have to respect one-ways
or different speed limits for different directions. To compute all links to the landmark
we use a Dijkstra-like approach [1].
   A second simplification: we limit the range for directions. Only within a range from
a landmark, we assign direction markers. We, e.g., would not expect a direction marker
'Rome in 2000 km', but only within 500 km. We call the maximum range maxC(m) – it
depends on the respective landmark.
   An algorithm to compute dir(e) for each eE can be sketched as follows:


     Algorithm compute_dir(V, E, M, c, lm, maxC)  dir
     for each eE { dir[e]={}; }
     for each mM {
         create empty arrays g, state, backLink, d;
         for each vV { backLink[v]undef; }
         for each vlm(m) { g[v]0; state[v]open;                   }
         for each vlm(m) { g[v] -1; state[v]not_visited; }
         for each eE { d[e]undef; }
         openListlm(m);
         while not openList.isEmpty() {
             vopenList.poll();          // get crossing with state open and minimal g
             if g[v]>maxC(m) then break; // limit of interest reached
             state[v]closed;
             for all e=(v, vn)out(v) with state[vn]closed {
                 gnewg[v]+c(v, vn);
                 if state[vn]=not_visited or gnew<g[vn] {
                     g[vn]gnew; backLink[vn]v;
                     state[vn]open; openList.add(v);
                     d[e]m;
                 }
             }
         }
         for each eE with d[e]undef { dir[e].add(d[e]); }
     }


The openList is always sorted by g, to quickly get the crossing with minimal g. Possible
data structures for these are Fibonacci Heap or Priority Queue.
Ortsbezogene Anwendungen und Dienste 2017                                             97


   The algorithm above computes only the directions. If we additionally request the
distance to the landmark, we could extend the data structure of d (dir respectively) to
also store distance information. E.g., we could change d[e]=m to d[e]=(m, gnew).


2.2    Improving this Approach, Cropping
Even though the majority of directions are reasonable, some assignments are mislead-
ing, unexpected or at least not helpful. We can distinguish the following problems as
illustrated in Fig. 2.




 Fig. 2. Problems with the naïve approach


 Fig. 2 left: If we are very close to the landmark ('Munich'), directions are confusing.
  The problem is even worse, if we are close and the respective link points away from
  the landmark – even if this was the optimal path.
 Fig. 2 middle: A starting link could point away from the landmark ('Hamburg'), but
  it could still be on the optimal path, as some further links could perform a 180° turn.
  This is very common on highways. Consider the highway to 'Munich' shortly before
  an exit. This link also is the shortest path to the opposite direction 'Hamburg' as an
  optimal path would exit, cross the highway and enter the highway in the other direc-
  tion.
 Fig. 2 right: A starting link could be in countryside region ('village'). However, such
  links tend to be a starting point to nearly any landmark.
The approach to solve these problems is to cut all virtual routes to the landmark both
from the virtual start and from the target. We call this mechanism cropping. This means
from each virtual route, we remove a certain amount of length from the start and land-
mark and only place direction markers, if they are sufficiently far away from these (Fig.
3).
98                                                                             LBAS 2017


                          not X L :              lm(m)              f(m)
  not Xf Lf:            near landmark
near virtual
      starts                         Landmark m




                                                X L and Xf Lf
                                              range for direction
                                                   markers

                                                             Landmark m




 Fig. 3. The idea of cropping

It turned out that a similar mechanism such as the maxC to express distances is not
suitable, as we have to express much more complex notions of distance. We e.g. want
to express 'we have to drive at least 1 km on country roads from the start'. For this, we
introduce two application-dependent metric vectors X=(x1,…xn), Xf=(xf1,…xfn) that
formalize the desired distance properties. Here X describes the metric value going from
the landmark, Xf from the (virtual) starting point. Later, each crossing on a virtual route
carries an individual pair of (X, Xf).
    To increase the metric value if we pass a link, we need a function

                     hop: E  X  X; e, (x1,…xn)  (y1,…yn)                           (1)

We require hop to be monotone, i.e.

                                     yixi for all i                                  (2)

Finally, we need two limits L, Lf. Later, we consider a crossing to be 'not near the
landmark', if XL, and 'not near the virtual start', if XfLf. Here  denotes pair wise
comparison, i.e.

                           xa1   xb1 
                          x  x 
                           a 2    b 2  iff i : xai  xbi                        (3)
                           ...   ... 
                            xan   xbn 

To give an example: let be X, Xf vectors of three components (x1, x2, x3) with
Ortsbezogene Anwendungen und Dienste 2017                                                                             99


 x1 is the total amount of meters of the route from landmark or start respectively,
 x2 is the amount of meters going over country roads or higher classified roads,
 x3 is the amount of meters going over municipal road or lower classified roads.
We consider crossing 'not near the landmark', if it is more than 5 km away and the route
to the landmarks goes at least over one country road (or higher class). We consider a
crossing 'not near the virtual start', if it is more than 1 km from the start and we had to
drive at least 100 m over municipal roads (or lower class). We express this by

                                                 5000     1000 
                                           L     L f   0                                                    (4)
                                                 0         100 
                                                               

whereas  is the smallest distance greater than zero. Note that these definitions for X,
Xf, L and Lf are our suggestion for landmarks such as cities or villages.
   To effectively compute Xf, we later require the set of virtual start crossings denoted
by f. These are crossings that have a backLink entry, but to do appear themselves as
backLink endpoint, i.e.

     f(m)={ v | backLink[v]undef } \ { backLink[v] | backLink[v]undef }                                           (5)

Note that a backLink always points to the landmark.
   We now have all tools to compute the X and Xf. The computation of X can be per-
formed 'on the fly' when visiting all crossings up to costs maxC. For Xf we have to face
a problem: a certain crossing may be on an optimal route from multiple virtual starts.
We thus have to aggregate a single Xf from multiple routes. Our approach is, to choose
the maximum value of the two routes, whereas max is defined

                                   xa1   xb1    max( xa1, xb1 ) 
                                                                     
                              max  xa 2 ,  xb 2     max( xa1, xb1 )  .                                     (6)
                                   ...   ...         ...        
                                  x                   
                                   an   xbn    max( xan , xbn ) 

Fig. 4 illustrates the mechanism.

                                                                         0                     xb1 
                                                                         0                     
                   y1                                                   ...                  xb2 
                  y                                        0         0                     ... 
                                                                                                 
                   2                                       0                              x 
                                                                                                  bn
                   ...                                    ... 
                    yn                                     0       0             xa1               y1 
                                                                     0                              y 
                                  x1                                  ...         xa2                2
                                                                                                           ...
                                 x 
                                                                       0
                                                                                       ... 
                                                                                      x                  y 
                                  2              0                                 an                 n
                                    ...
                                  x 
                                                   0
                                   n              ... 
                                                    
                                                   0
                                                                           0
                                                                           0
                                                                            ...         0
                                                                           0            0
                                                                            
                                                                                           ... 
                                                                            0            
                                                                            0           0
                                                                             ... 
                                                                            0
                                                                             


 Fig. 4. Updating X (left) and Xf (right)
100                                                                           LBAS 2017


Now we are able to present the improved algorithm that computes virtual direction
markers with cropping (modifications to the naïve algorithm are printed bold):


      Algorithm compute_dirf (V, E, M, c, maxC, hop, L, Lf)  dir
      for each eE { dir[e]={}; }
      for each mM {
          create empty arrays g, state, backLink, d, x, xf;
          for each vV { backLink[v]undef; xf[v] undef; }
          for each vlm(m) { g[v]0; state[v]open;                  x[v] (0,…, 0)T; }
          for each vlm(m) { g[v] -1; state[v]not_visited; x[v] undef; }
          for each eE { d[e]undef; }
          openListlm(m);
          while not openList.isEmpty() {
              vopenList.poll();          // get crossing with state open and minimal g
              if g[v]>maxC then break; // limit of interest reached
              state[v] closed;
              for all e=(v, vn)out(v) with state[vn]closed {
                  gnewg[v]+c(v, vn);
                  if state[vn]=not_visited or gnew<g[vn] {
                      g[vn]gnew; backLink[vn]v;
                      state[vn]open; openList.add(v);
                      x[vn]hop(e, x[v]);
                      d[e]m;
                  }
              }
          }
          compute f(m);
          for each vf(m) {
              xf[v](0,…, 0)T;
              loop {
                  vnbackLink[v];
                  xfnew hop((v,vn), xf[v]);
                  if xf[vn]=undef then xf[vn]xfnew;
                                    else xf[vn]max(xf[vn], xfnew);
                  if value of xf[vn] not changed then break loop;
                  vvn;
              }
          }
          for each e=(v, vn)E with d[e]undef and x[vn]L and xf[v]Lf
          { dir[e].add(d[e]); }
      }
Ortsbezogene Anwendungen und Dienste 2017                                               101


Whereas the computation of X is integrated into the main loop, Xf has to be computed
after each landmark iteration. However, the computation still is efficient, as it linearly
depends on the visited crossings and only loops through the crossings within maxC.




 Fig. 5. Range of links considered for direction markers for the landmark 'Nuremberg'

Fig. 5 illustrates the range of links considered as direction markers for a certain land-
mark, i.e. links that hold x[vn]L and xf[v]Lf in the algorithm above.


2.3    Distinctive Direction Markers, Relevant Crossings
Up to now, we compute all directions for a link, even if they are confirmative, i.e. only
encourage the driver to stay on the current route to find the landmark. We now want to
switch to distinctive direction markers that push the driver to make a decision. For this,
we introduce two concepts:

 relevant crossings: these are crossings that are considered to be appropriate for a
  certain landmark;
 default links: these are links that are considered to be walking or driving straight
  ahead, in particular not turn or exit.
102                                                                                LBAS 2017


Relevant crossings are represented by a relation relV  M, where rel(v, m) means: the
crossing v is relevant to be a position for a direction marker to landmark m. The relation
rel is application-dependent. As an example: a crossing in an industrial area is probably
not suitable for direction markers to touristic sights. We can easily set up a relation rel
based on the road network and further digital map data.
   As a second concept, we need default links. Let def(e) denote the default link for a
link eE. The default link is an outgoing link to the incoming link e, but not e , i.e.

                              def(e)out(vend(e))\{ e }                                       (7)

Similar to rel, def is application-dependent. This means, we cannot compute def solely
from the road topology, but we have to introduce certain rules to identify the one out-
going link that is considered to drive 'straight ahead'. These rules may take into account

 the road geometry, in particular the incoming angle to and outgoing angle from the
  crossing;
 road types, e.g. highway, exits, road classifications;
 priority rules, rights of way;
 road identities, road names.
As an example: if the difference of incoming to outgoing angle is less than 30°, the road
name remains the same and the driver still has right of way, then the corresponding
outgoing link is the default link.
   The rule set may be very large and cover different scenarios. Sometimes it is simpler
to decide, which link is not the default link, e.g. a highway exit never is the default link.
Some incoming connections do not have any default link at all, e.g. think of three-way-
junctions. In this case, we set def(e)=undef. Fig. 6 illustrates some examples for default
links.




 Fig. 6. Default link examples (incoming and default link: black, non-default-link: yellow)
Ortsbezogene Anwendungen und Dienste 2017                                            103


We now are able to introduce distinctive directions dist(e): they are relevant according
to rel and do not reside on the default link according to def. We are able to compute
dist from a formerly computed dir with the following algorithm:


     Algorithm compute_distinctives(V, E, M, dir, rel, def)  dist
     for each e=(v, vn)E {
         dist(e){};
         for each mdir(e) {
             if rel(v, m) and ( ein  in(v) : def(ein)e and mdir(ein) )
                then add m to dist(e)
         }
     }


Fig. 7 shows some examples of computed distinctive direction markers.




 Fig. 7. Examples of distinctive direction markers

Some words about the performance: as a first observation, we consider performance
not as a critical issue. The computation of direction markers is not performed at runtime
but in the context of mastering and bundling the geo data for an application. Thus, it
may take some hours without any drawback. Second: as the landmarks are processed
104                                                                               LBAS 2017


independently, the processing can easily be distributed to different CPUs or even com-
puting hosts to parallelize the computation.


3      Conclusions

In this contribution, we presented an approach to automatically compute direction
markers that point to landmarks in road networks. We distinguished confirmative and
distinctive markers. The main idea: every direction marker resides on an optimal path
from a virtual starting point to the landmark. As nearby the virtual starting point and
nearby the landmark such markers were misleading, we introduced the mechanism of
cropping that cuts the virtual paths with the help of application-defined metrics. We
presented an efficient approach to propagate these metrics among the network. To only
get distinctive direction markers, we additionally introduced relevant crossings and de-
fault directions. The approach is successfully integrated into the donavio platform.


References
 1. Dijkstra E.W: A note on two problems in connexion with graphs, Numerische Mathematik
    1, 269–271 (1959)
 2. Roth, J.: Die HomeRun-Plattform für ortsbezogene Dienste außerhalb des Massenmarktes,
    in A. Zipf, S. Lanig, M. Bauer (eds.) 6. GI/ITG KuVS Workshop Location based services
    and applications, Heidelberger Geographische Bausteine, Vol. 18 (in German) (2010)
 3. Roth, J.: Modularisierte Routenplanung mit der donavio-Umgebung, in Werner M., Hau-
    stein M. (eds.): 9. GI/ITG KuVS Workshop Location based services and applications, Sept.
    13-14, 2012, TU Chemnitz, Universitätsverlag Chemnitz, 119-131 (in German) (2013)
 4. Roth, J.: Predicting Route Targets Based on Optimality Considerations, International Con-
    ference on Innovations for Community Services (I4CS), Reims (France) June 4-6, 2014,
    IEEE xplore, 61-68 (2014)
 5. Roth, J.: Efficient many-to-many path planning and the Traveling Salesman Problem on
    road networks, International Journal of Knowledge-based and Intelligent Engineering Sys-
    tems Vol. 20 (2016), IOS Press, 135–148 (2016)
 6. Roth, J.: The Offline Map Matching Problem and its Efficient Solution, 16th International
    Conference on Innovations for Community Services (I4CS), Vienna, Austria, June 27-29,
    2016, Springer CCIS 648, 23-38 (2016)
 7. Roth, J.: Efficient Computation of Bypass Areas, Gartner, Huang (eds): Progress in Loca-
    tion-Based Services 2016, Proc. of the 13th International Conference on Location-Based
    Services, Vienna, Austria, Nov. 14–16, 2016, Springer LNG&C, 193-210 (2016)
 8. Traditional Direction Signs. Traffic Advisory Leaflet 6/05, Department for Transport, Lon-
    don (2005)
 9. Vienna Convention on Road Signs and Signals. United Nations Economic and Social Coun-
    cil, March, 28th (2006)

</pre>