JOSM/Plugins/JunctionChecking

From OpenStreetMap Wiki
< JOSM‎ | Plugins
Jump to navigation Jump to search
Junctionchecking plugin

Junctionchecking is a plugin for JOSM based upon the RoadNetworkAlgorithms which identifies junctions as sets of channels in terms of their locomotion affordance: e.g. a 3-way junction affords people to move from every one of 3 junction entries to every one of its 3 exits (n times n). An example is a T intersection. So a junction is a road network feature that allows for a certain kind of constrained navigational choice. Classical 4-way junctions are e.g. cloverleaf interchanges. Note that from an affordance perspective, the junctions found may not always perfectly correspond to what you would intuitively consider the junction, since it may contain smaller parts that already satisfy the affordance criterion. Therefore our definition is based additionally on a minimality criterion. There are also road configurations that look similar but do not allow for n times n ways. Note that the algorithm is roughly quadratic in the number of channels you search in, so to search in large amounts of data is not recommendable. Note also that the correctness of the algorithm is dependent on the availability and correctness of turn-off-restrictions specified in the OSM "restriction relation". In case these are missing, the algorithm makes the (often false) assumption that all turn-offs are allowed. The plugin and the channel digraph theory is developed at the SeresII working group at the institute for geoinformatics at the university of Münster.

Features

  • creation of a channel digraph from existing osm data
  • visualization of a channel digraph in JOSM
  • verification of a subset of channels of junction criteria
  • searches for junctions in a subset of channels
  • consideration of existing turn restriction relations

Overview channel digraph/junctions in channel digraphs

Channel digraph

Even though there are informal standards for road network labeling available (e.g.the GDF standard, ISO 14.825:2004), geometries and category labels in different commercial road network data are far from denoting equivalent things. Furthermore, the available categories often lack high-level features, such as junctions and roads, as well as labels for applications that go beyond navigation systems. In RoadNetworkAlgorithms, we have proposed a theory of channel networks which is grounded in observable locomotion affordances. Into this theory, road network data, data schemata and related ontologies map in an obvious way. We have given affordance-based definitions of a channel network and an n-way junction, and showed that the junction definition is satisfied by a collection of most common junction types, for example 4-way-intersections, diamond interchanges, jughandles and cloverleafs. Using this theory to semantically annotate, check and translate data about road networks requires to have tractable algorithms available. These algorithms were implemented in the junctionchecking plugin.

Junctions in channel digraphs

An n-way junction is an induced subgraph F of a channel digraph D, which

  1. affords n − 1 (n ≥ 3) navigational choices for n entries, as there is a walk from each of the n entries to n − 1 exits (except into the opposite direction), and from n − 1 entries to each of n exits (total reachability),
  2. affords movements to enter and leave through gates (discreteness of navigational action),
  3. does not contain a smaller n-way junction (minimality I) and
  4. has entries and exits with a minimal vertex degree of two. Entries have either more than one internal successor or an internal predecessor. Analogously, exits have either more than one internal predecessor or an internal successor (minimality II).

Installation

Install the plugin with the JOSM plugin manager or install manual the jar-file

Plugin usage

After installation there is a button on the left side of josm. Click this button to activate the plugin dialog which is shown on the right side of josm.

Channel Digraph Creation

To create a channel digraph osm data must be opened in a layer and this layer must be active. Click on the "Create" button to produce a channel digraph from the whole osm data of the layer. There is one option:

  • calculation of the strong connected components: the channel digraph is checked for strong connected components after creation. all channels which are not strong connected were marked in a different colour (purple). Junction checks with channels which are not strong connected should not be performed because these channels produce errors in the calculations.

Junction check in a subset of channels

The user can mark channels in the created channel digraph layer for junction tests. The user need to set to set the junction order in the plugin dialog window (default value is 3 for a 3 ways junction). To start the junction check the user must press the "Check" button. There are 3 possible results:

  1. positive: the marked channels represent a junction. In this case (and if a default option is chosen), an OSM relation will be generated that contains the junction and stores its order. The discovered junction will be displayed in another colour.
  2. negative: the marked channels do not satisfy all of the junction criteria total reachability, discreteness of navigational action and minimality II (Section 4). In this case the user will be informed in an additional dialog window.
  3. negative: the marked channels satisfy the three junction criteria total reachability, discreteness of navigational action or minimality II, but not the criteria minimality I. This means the subgraph contains a smaller junction. The minimality I test stops as soon as it finds a subgraph within the original subgraph that satisfies the three other junction criteria. This subgraph is displayed in another colour and represents another junction candidate for testing. To check this candidate the user has to push the junction test button again.

Junction search in a subset of channels

  • Adjust n, the number of ways a junction consists of (minimum 3)
  • Mark a set of channels and click on "search" to detect all n-way junctions
  • For each junction it is possible to produce an Openstreetmap Relation

creation of junction osm relations

It is possible to produce osm relations from discovered junctions. These relations were saved in the original osm data layer, the user can activate/deactivate the creation in the plugin dialog ("produce OSM relation: junction"). A junction relation consists of the member of the junction and the junction order.

Example of a junction check

ursprüngliche Channelauswahl

In the figure you see the strong connected channels of the Koldering/Weseler Straße in Münster, Germany. The junction order is 3 because there are 3 possibilities to enter the junction and 3 possibilities to leave. The red marked channels are the subset of the junction check.


ursprüngliche Channelauswahl

This figures shows the result of the check: there is one smaller junction candidate. It could be a junction but only 3 from 4 criteria were tested. total reachability, discreteness of navigational action und minimality II. The subset in the figure can contain also a smaller junction. To test this it is necessary to check the subset.


ursprüngliche Channelauswahl

The result of the second check is also a smaller junction candidate. This subset must also be tested for minimality I. But in this case there is no smaller junction discovered and that means the marked subset in the figure is a junction.

This example shows that in the osm data are not all necessary turn restrictions. In the osm data there is only the turn restriction displayed in the second and third figure but there must be 2 more which are displayed in the first figure. If these turn restrictions exist in the osm data the result would be another one: the marked subset in the first figure would be a junction because it does not contain smaller ones..


Known bugs

  • if josm crashes during calculation of the strong connected components start josm with these (additional) parameters: java -jar -Xss30M josm-latest.jar
  • discovered junctions are coloured white only after zooming or scrolling in the channel digraph layer

links

Contact

Contact the author: mail