On this page you find the proof of concept source code accompaning the Journal Paper “On d-regular Schematization of Embedded Paths” by Daniel Delling, Andreas Gemsa, Martin Nölenburg, Thomas Pajor and Ignaz Rutter.

@article{dgnpr-dsep-13,
title = “On d-regular schematization of embedded paths ”,
journal = “Computational Geometry”,
volume = “”,
number = “0”,
pages = “–”,
year = “2013”,
doi = “http://dx.doi.org/10.1016/j.comgeo.2013.10.002”,
url = “http://www.sciencedirect.com/science/article/pii/S0925772113001156”,
author = “Daniel Delling and Andreas Gemsa and Martin Nöllenburg and Thomas Pajor and Ignaz Rutter”
}

One important use of visualizations of routes in road networks is to help orientation while driving. Traditional road maps with their uniform scale are good for giving a general idea of the route, but often do not succeed in showing details of the route within the start and destination region.

Manually generated route sketches do not suffer from this problem. Hence, we consider the problem of automatically generating route sketches. Users generally have a rough conception—the mental map—of the route, hence, the sketch must sufficiently resemble the original route. We achieve this by requiring that in the new drawing the left-right and top-bottom relationship between all important nodes in the original route is maintained. Further, to enhance readability a minimum edge length is introduced and to reduce the visual complexity the admissible edge slopes are restricted.

Three different visualizations of the same route. Left to right: google maps, hand-drawn route sketch, automatically generated route sketch

The example route from Karlsruhe, Germany to Konstanz, Germany shows the result of our method. The traditional road map (picture on the left) and the hand-drawn route sketch differ in that the latter displays road details in Karlsruhe and in Konstanz more clearly. While in the hand-drawn route sketch all parts of the route are clearly visible, the road map provided by google maps only shows the highways in sufficient detail. Although the route is skewed in the hand drawn route sketch the overall shape, i.e., the mental map, is preserved. Our algorithms automatically generate route sketches that mimick the major characteristics of hand drawn route sketches. So, each street is discernable while the rough shape of the original route can be recognized. An experimental evaluation showed that our technique generates good route sketches within a reasonable time frame.

Since this is a simple proof of concept we do generally do not provide support or help in compiling this. However, you can still try and contact Andreas Gemsa at andreas.gemsa@kit.edu for questions regarding the source code.

This program/source code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

routesketch.zip

1. Daniel Delling, Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
   On d-regular Schematization of Embedded Paths.
   Computational Geometry: Theory and Applications, 2013.
   Published online.
   [ html ]