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 automatically 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 unwanted markers. Finally, we introduce the notion of relevant crossings and default links that additionally improve direction markers.
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
interesting destinations (e.g. cities, important sights) and know useful locations to place
these signs [
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 compute 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 interesting new destination options for the driver. 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 confirmative 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
navigation problems. Corresponding solutions are integrated into the HomeRun platform
[
As a new donavio function, we want to enrich the road network to carry direction information. 2 2.1
We start with some definitions. Let V denote the set of crossings and E the set of (directed) links between crossings. Further let out(v) denote all outgoing links from and in(v) all incoming links to a crossing v.
For an eE, 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 denote 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 mM 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 approach 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 relation to the landmark or to the respective link. We also do not actually drive from this starting point. However, all links of the corresponding route are directed to the landmark, 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
particular 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 [
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 eE can be sketched as follows: Algorithm compute_dir(V, E, M, c, lm, maxC) dir for each eE { dir[e]={}; } for each mM { create empty arrays g, state, backLink, d; for each vV { backLink[v]undef; } for each vlm(m) { g[v]0; state[v]open; } for each vlm(m) { g[v] -1; state[v]not_visited; } for each eE { d[e]undef; } openListlm(m); while not openList.isEmpty() { vopenList.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 { gnewg[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 eE 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.
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
Even though the majority of directions are reasonable, some assignments are misleading, unexpected or at least not helpful. We can distinguish the following problems as illustrated in Fig. 2. 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 direction. 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 landmark and only place direction markers, if they are sufficiently far away from these (Fig. 3).
not Xf Lf: near virtual starts
not X L : near landmark lm(m)
f(m) Landmark m
X L and Xf Lf range for direction markers
Landmark m 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=(x1,…xn), 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 We require hop to be monotone, i.e.
hop: E X X; e, (x1,…xn) (y1,…yn)
yixi for all i Finally, we need two limits L, Lf. Later, we consider a crossing to be 'not near the landmark', if XL, and 'not near the virtual start', if XfLf. Here denotes pair wise comparison, i.e.
xa1 xb1 xa2 xb2 iff i : xai xbi ... ... xan xbn To give an example: let be X, Xf vectors of three components (x1, x2, x3) with (1) (2) (3) 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 L 0 L 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 performed '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 xa2 , xb2 max(xa1, xb1) .
x.a..n x.b..n max(x.a..n , xbn ) (4) (6) Fig. 4. Updating X (left) and Xf (right) 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_dirf (V, E, M, c, maxC, hop, L, Lf) dir for each eE { dir[e]={}; } for each mM { create empty arrays g, state, backLink, d, x, xf; for each vV { backLink[v]undef; xf[v] undef; } for each vlm(m) { g[v]0; state[v]open; x[v] (0,…, 0)T; } for each vlm(m) { g[v] -1; state[v]not_visited; x[v] undef; } for each eE { d[e]undef; } openListlm(m); while not openList.isEmpty() { vopenList.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 { gnewg[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 vf(m) { xf[v](0,…, 0)T; loop { vnbackLink[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; vvn; } }
} for each e=(v, vn)E with d[e]undef and x[vn]L and xf[v]Lf { dir[e].add(d[e]); } 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 illustrates the range of links considered as direction markers for a certain landmark, i.e. links that hold x[vn]L and xf[v]Lf in the algorithm above. 2.3
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. Relevant crossings are represented by a relation relV 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 eE. 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 outgoing 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-wayjunctions. In this case, we set def(e)=undef. Fig. 6 illustrates some examples for default links. 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 mdir(e) { if rel(v, m) and ( ein in(v) : def(ein)e and mdir(ein) )
then add m to dist(e) }
} 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 independently, the processing can easily be distributed to different CPUs or even computing hosts to parallelize the computation. 3
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 default directions. The approach is successfully integrated into the donavio platform.