Change search
ReferencesLink to record
Permanent link

Direct link
Computing the fewest-turn map directions based on the connectivity of natural roads
Geomatics, University of Gävle.
2011 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1362-3087, Vol. 25, no 7, 1069-1082 p.Article in journal (Refereed) [Artistic work] Published
Abstract [en]

In this paper, we introduced a novel approach to computing the fewest-turn map directions or routes based on the concept of natural roads. Natural roads are joined road segments that perceptually constitute good continuity. This approach relies on the connectivity of natural roads rather than that of road segments for computing routes or map directions. Because of this, the derived routes posses the fewest turns. However, what we intend to achieve are the routes that not only possess the fewest turns, but are also as short as possible. This kind of map direction is more effective and favorable by people, because they bear less cognitive burden. Furthermore, the computation of the routes is more efficient, since it is based on the graph encoding the connectivity of roads, which is significantly smaller than the graph of road segments. We made experiments applied to eight urban street networks from North America and Europe in order to illustrate the above stated advantages. The experimental results indicate that the fewest-turn routes posses fewer turns and shorter distances than the simplest paths and the routes provided by Google Maps. For example, the fewest-turn-and-shortest routes are on average 15% shorter than the routes suggested by Google Maps, while the number of turns is just half as much. This approach is a key technology behind - a web mapping service using openstreetmap data.

Place, publisher, year, edition, pages
Taylor & Francis Group, 2011. Vol. 25, no 7, 1069-1082 p.
Keyword [en]
routing, map directions, human navigation, natural roads, openstreetmap, FromToMap
National Category
Geotechnical Engineering
URN: urn:nbn:se:kth:diva-51240DOI: 10.1080/13658816.2010.510799ISI: 000295467600002ScopusID: 2-s2.0-79961243742OAI: diva2:463680

QC 20130422

Available from: 2013-04-22 Created: 2011-12-10 Last updated: 2013-04-22Bibliographically approved
In thesis
1. The Principle of Scaling of Geographic Space and its Application in Urban Studies
Open this publication in new window or tab >>The Principle of Scaling of Geographic Space and its Application in Urban Studies
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Geographic space is the large-scale and continuous space that encircles the earth and in which human activities occur. The study of geographic space has drawn attention in many different fields and has been applied in a variety of studies, including those on cognition, urban planning and navigation systems. A scaling property indicates that small objects are far more numerous than large ones, i.e., the size of objects is extremely diverse. The concept of scaling resembles a fractal in geometric terms and a power law distribution from the perspective of statistical physics, but it is different from both in terms of application. Combining the concepts of geographic space and scaling, this thesis proposes the concept of the scaling of geographic space, which refers to the phenomenon that small geographic objects or representations are far more numerous than large ones. From the perspectives of statistics and mathematics, the scaling of geographic space can be characterized by the fact that the sizes of geographic objects follow heavy-tailed distributions, i.e., the special non-linear relationships between variables and their probability.

In this thesis, the heavy-tailed distributions refer to the power law, lognormal, exponential, power law with an exponential cutoff and stretched exponential. The first three are the basic distributions, and the last two are their degenerate versions. If the measurements of the geographic objects follow a heavy-tailed distribution, then their mean value can divide them into two groups: large ones (a low percentage) whose values lie above the mean value and small ones (a high percentage) whose values lie below. This regularity is termed as the head/tail division rule. That is, a two-tier hierarchical structure can be obtained naturally. The scaling property of geographic space and the head/tail division rule are verified at city and country levels from the perspectives of axial lines and blocks, respectively.

In the study of geographic space, the most important concept is geographic representation, which represents or partitions a large-scale geographic space into numerous small pieces, e.g., vector and raster data in conventional spatial analysis. In a different context, each geographic representation possesses different geographic implications and a rich partial knowledge of space. The emergence of geographic information science (GIScience) and volunteered geographic information (VGI) greatly enable the generation of new types of geographic representations. In addition to the old axial lines, this thesis generated several types of representations of geographic space: (a) blocks that were decomposed from road segments, each of which forms a minimum cycle such as city and field blocks (b) natural streets that were generated from street center lines using the Gestalt principle of good continuity; (c) new axial lines that were defined as the least number of individual straight line segments mutually intersected along natural streets; (d) the fewest-turn map direction (route) that possesses the hierarchical structure and indicates the scaling of geographic space; (e) spatio-temporal clusters of the stop points in the trajectories of large-scale floating car data.

Based on the generated geographic representations, this thesis further applies the scaling property and the head/tail division rule to these representations for urban studies. First, all of the above geographic representations demonstrate the scaling property, which indicates the scaling of geographic space. Furthermore, the head/tail division rule performs well in obtaining the hierarchical structures of geographic objects. In a sense, the scaling property reveals the hierarchical structures of geographic objects. According to the above analysis and findings, several urban studies are performed as follows: (1) generate new axial lines based on natural streets for a better understanding of urban morphologies; (2) compute the fewest-turn and shortest map direction; (3) identify urban sprawl patches based on the statistics of blocks and natural cities; (4) categorize spatio-temporal clusters of long stop points into hotspots and traffic jams; and (5) perform an across-country comparison of hierarchical spatial structures.

The overall contribution of this thesis is first to propose the principle of scaling of geographic space as well as the head/tail division rule, which provide a new and quantitative perspective to efficiently reduce the high degree of complexity and effectively solve the issues in urban studies. Several successful applications prove that the scaling of geographic space and the head/tail division rule are inspiring and can in fact be applied as a universal law, in particular, to urban studies and other fields. The data sets that were generated via an intensive geo-computation process are as large as hundreds of gigabytes and will be of great value to further data mining studies.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2012. xii, 90 p.
geographic space, scaling, GIScience, VGI, OSM, heavy-tailed distribution, the head/tail division rule, space syntax, nature street, urban sprawl, floating car data, hierarchical spatial structure
National Category
Geotechnical Engineering
urn:nbn:se:kth:diva-90832 (URN)978-91-7501-277-3 (ISBN)
Public defence
2012-03-15, D2, Lindstedtsvägen 5 Entreplan, Royal Institute of Technology, Stockholm, 13:30 (English)
Hägerstrand project entitled “GIS-based mobility information for sustainable urban planning and design”

QC 20120301

Available from: 2012-03-01 Created: 2012-02-29 Last updated: 2015-06-16Bibliographically approved

Open Access in DiVA

Computing the Fewest-turn Map Directions based on the Connectivity of Natural Roads(1062 kB)114 downloads
File information
File name FULLTEXT01.pdfFile size 1062 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusPublisher's website

Search in DiVA

By author/editor
Bin, JiangXintao, Liu
In the same journal
International Journal of Geographical Information Science
Geotechnical Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 114 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 83 hits
ReferencesLink to record
Permanent link

Direct link