We are going to look at two methods of shortest path analysis. One is to use the Road Graph plugin in QGIS, and one is to use the same sort of extentions in software called ArcView (3.x) – Scott’s favorite. Below are the directions for ArcView (as we have not seen this software before). The other from QGIS we will explore as a class.
Extensions necessary for ArcView
We will need the Network Analyst as well as Point and Polyline tools (extensions).
What are we doing?
How do networks in topological layers model in tables (ArcInfo)
Having the ability to find the shortest path from one location to another has been part of GIS analysis before the use of ArcView 3.
The methods employed by using ArcInfo, the table based topology we looked at in lecture, calculated distances by adding up values in a line table. For instance each line knows its to node and from node vales as well as the length between both (all in the table). A routine that follows all connected lines (series of t_node and f_node combinations) to see which combination provided the lowest sum of lengths would thereby the shortest route. There was a whole series of tasks and abilities added to these routines to model routes, segments and events (point locations) along these routes. This constituted dynamic segmentation and was used heavily in ArcInfo.
Network Analyst in ArcView 3x
As we know ArcView uses shape files and does make use of conventional Topology (nodes, lines and polygon relationships. We also know that we can use tools and extensions in ArcView to model concepts associated with topology such as connectedness and adjacency. ESRI has created an extension called network analysis that we are going to use to; find the shortest distances between locations as well as determining catchments areas (similar to what Jessica Place did in her research determining emergency health care distances).
This extension does not use tables to calculate distances, but rather traverses a line layer tracking distances of each line until it reaches the endpoint. It actually makes up a network of related points (where the lines meet) and distances between them. It then can calculate the shortest distance from one point to another. Network Analyst uses Dijkstra’s algorithm to determine these routes. Talk to Scott if you want to understand this more fully, but for now we will carry on with the tutorial.
Lets open up ArcView and load up the layers in the z:/home/labs/geog204/network_tutorial directory called:
z is used for the drive letter as we are running software built for the windows operating systems on Linux
Make sure you load the extensions mentioned at the beginning of the tutorial (network analyst and point and polyline tools).
Fixing the location of points
By using the points and polyline extension (can you find it on ESRI’s ArcScritps web page http://arcscripts.esri.com?), we can fix situations whereby you may need to have points fall on lines in another layer. We are using this extension to help out the network analyst extension, but it can be applied in many other situations (i.e. number of postal codes per distance along a line).
Select snap points to polylines from the P/PL – Tools and follow the wizard to snap the starts layers to the bcrteclip layer. You can use infinite (default) as the fuzzy tolerance, but really you should choose a better distance (why is that?). What are the “Display Units” of this View, and how can you change them? Do not worry about virtually adding vertices to the line layer, but You should select ID as an attribute to carry over to the newly created point layer shape file – why would we not include the lons and lats?. Save the shape file in a directory called network_tut. Repeat this procedure for the stops layer.
To do the snapping properly we should snap using the following input – see how it compares to the snapping done above:
- fuzzy tolerance of .005
- virtual step size of .001
Make the bcrteclip layer active and click on find best route under the network pulldown. You should now get a route 1 panel and a layer called route 1 in the table on contents. In the route 1 control panel click on load stops and load in either the newly snapped layers. You can also place starting nodes (points) manually by using the location button.
Click on the icon in the top right of the panel –> then routes will be calculated. Once complete, you will have a routes to play with. If you open the attribute table, you can select the different routes.
In this case, once you have opened the Fac1 panel (again you find the closest facility panel under the network pulldown, there should be a new layers in the table of contents called Fac1), you will have to choose which layer has the facilities you are looking to be closest to (which layer should be active for launching the panel). The layer you did not choose, will then be the events layer (what do w mean by using the term “event layer”?).
Again, click on the finder button in the top right corner of the panel and determine the nearest facility. You will notice that only the first event was used and if you did not set the number of facilities to be greater that 1, you will only get one line. You can play around with the options in the panel to get different results (including a cut off distance and time to facility instead of distance).
Find Service Area
This function would be used to calculate the population serviced by emergency care within a certain distance or time in the network calculations for Jessica’s work. Open this dialogue, load which ever starts or stops (or both) you wish, play around with the length in miles item and hit the button. Again you can make adjustments to use time.
You can save these layers as shape files to perform further analysis.
The data Scott selected for this tutorial was from stats can – therefore it is in geographic projection. You can do network analysis in metre projections as well. Do you remember how to project data into UTM or BC Albers?