Tag Archives: least cost path

Shortest Path Computation: A Comparative Analysis

Leave a reply
Revised on: 2011-07-22

Current research work into establishing a performance efficiency hierarchy between Java, C++ and ArcView is described and experimentation is performed in order to statistically compare shortest path query execution time, response time and implementation issues.

Continue reading →

MFworks Tutorial

Leave a reply
Revised on: 2015-10-02

MFworks has evolved from MAPFactory, originally designed by C. Dana Tomlin, the father of map algebra.  Conducting network analysis in MFworks comprises iterative steps that lead to a functioning network. These steps will convert map layers with square cells into linear elements that are linked together as lines, with directional flows assigned to each cell, and map layers containing cost variables. This tutorial, developed by husdal.com in 2002, is a showcase on network analysis in MFworks, with step by step instructions and a summary of the theory behind it.

Continue reading →

How to make a straight line square

2 Replies
Revised on: 2011-07-22

Euler’s famous “Königsberg bridge” question, dating back as far as 1736, is often seen as the starting point of modern path finding – was it possible to find a path through the city of Königsberg crossing each of its seven bridges once and only once and then returning to the origin? Euler’s methods formed the basis of what is known as graph theory, and which in turn paved the way for path finding algorithms. Traditionally, network analysis, path finding and route planning have been the domain of graph theory and vector GIS, which is where most algorithms find their application. Contrary to such common wisdom, the research of this thesis for the Msc in GIS explores the topic of network analysis in raster GIS, using MFworks as example software. Current algorithms, procedures and network modelling techniques are investigated and common artefacts are explained.

Continue reading →

Fastest path problems in dynamic transportation networks

4 Replies
Revised on: 2011-07-22

This research essay and literature review investigates some of the gateways to path finding in static and dynamic networks that are listed in present research literature. A selected set of different approaches are highlighted and set in a broader context, illustrating the various aspects of path finding in static and dynamic networks. It is shown that the A* algorithm is the dominant algorithm for solving fastest path problems. A further attempt is made to draw attention to the advances that have been made in path finding in the field of robotics, in order to establish a lateral relation that can form the basis of further exploration and fruitful merger of the two research fields.

Continue reading →

Network analysis – raster versus vector – A comparison

3 Replies
Revised on: 2015-10-05

Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Real world networks, such as a road system, must be modelled appropriately to fit into the different spatial models. Even though the models differ, the solution to different transportation problems in either raster or vector GIS uses the same path finding algorithms. Whether raster or vector GIS is to be preferred is more a question of choice than of accuracy.

Continue reading →