Finding the shortest path between two points is a typical task. Usually we find such a shortest path through a network made up of road lines. At times we may want to find the shortest path between two locations that satisfies other criteria in a region where there is no road network. For example, we might want to find the shortest path between two points that does not cross any water bodies, or we may want to find the shortest path between two points that never rises above a given terrain elevation, avoids certain obstacles or otherwise is constrained.
This example considers the general problem of finding the shortest distance between two points when travel is allowed only within a specified region. In the example we will find the shortest distance between two points where travel must occur on land within Mexico.
The general solution to this and other similar problems is to first build a network that exists only within the allowed region. We can then use the network to find a shortest path. Most of the procedure's steps are creating the network. Once we have the network the rest is easy. To build a network we will create a regular grid of points. We will then remove all points that do not lie on land. We then build the network using the remaining points.
This is an unusually long example that will seem very intricate to a newcomer. For experienced hands it is very rapidly done. Beginners should have faith that mastery of elementary maneuvers in Manifold will allow them to speed through tasks like this example.
Step 1: Import drawing and prepare drawing
We begin by importing the mexico_eg.mif sample drawing. Open the drawing and choose Edit - Change Projection to open the projection dialog.
Project the drawing into Orthographic projection using the default parameters offered by pressing the Suggest button. Press OK.
The drawing will now appear in Orthographic projection. It is important to project the drawing so default measurements appear in meters.
Later in this example we will use spatial overlays to transfer field values for objects over land. To facilitate use of spatial overlays, we will add a field to the drawing's table. To add a field, open the drawing's table, right click onto any column head and choose Add - Column from the context menu.
In the Add Column dialog, choose the name Land for the new field and press OK to create the new field using the default type of Integer (32-bit). [We could, of course, create this as a Boolean field if desired since we will use this field to flag land areas. We used the integer type out of sheer laziness because it is the default.]
A new column called Land appears in the table. We now will set the value of Land to 1 for all land areas.
To do this, we press CTRL-A to select all the records in the table. We could have also chosen Edit - Select All from the menu.
We double click into any of the Land cells and enter the value 1 and press Enter.
This enters the value 1 into the Land column for all selected records. Next, we need to set the Transfer Rule for this column. To do so, we right click onto the Land column head and choose Transfer Rules from the context menu.
In the Column Transfer Rules dialog we choose Copy for the 1 to N rule. The transfer rule tells Manifold how to allocate the value in this column when it is transferred to other objects. The 1 to N rule is used when one of the objects (such as an area) transfers its value to many other objects (such as points within that area). The Copy rule tells Manifold to take the value in the object and to copy it into all of the receiving objects.
Step 2: Create a grid of points
Click back onto the drawing to move the focus there. We will now create a grid of points in the drawing. Begin by pressing View - Grid.
The Grid dialog opens with values estimated from the size of the open drawing window. We will change the spacing parameter to 100000 meters. This will create a grid of lines separated by horizontal and vertical intervals of 100 km. That's a fairly coarse grid but suitable for our example. Create the grid by pressing the Create button. This creates a grid of line objects in the drawing.
The choice of a grid interval is an important matter for the approximations that follow. The finer the grid, the finer will be the network we build from it. The finer the network, the greater the accuracy of the shortest path approximation. However, the finer the grid the greater the network analytic task as well as all geometric tasks involved in the construction of the network. We strongly urge the new user to begin with very coarse grids to master the technique. One can later progress to denser grids in gradual steps to see where performance becomes unacceptably slow. Experts who are sure of their technique may use dense grids that could take a weekend of processing to perform some tasks for a final result.
The Grid dialog is a dual-purpose dialog. It can be used to show a grid of lines created by the system that "floats" above the drawing but is not a part of it. In addition, it can be used to create line objects in the drawing in the shape of the grid. We've used the Grid dialog to create a grid of line objects. However, we do not want to show a grid overlay in addition to that. So, we uncheck the Show grid box and press OK to exit the Grid dialog.
In the drawing we now have a grid of lines spaced at 100 km vertical and horizontal intervals. We will create points at their intersections.
To do so, we first select all of the lines. Do this by pressing in the Select Lines select objects button and pressing out the Select Areas and Select Points buttons. We can then press CTRL-T or choose Edit - Select By Type from the menu to select all of the lines. [This is such a common task that it is good to become accustomed to pressing CTRL-T for faster editing.]
In the Transform toolbar , choose the [Selection] as the scope and Points as the transform operator. This will create points at the ends of all lines in the selection.
The result is the creation of many points that are separated from each other by the same vertical and horizontal interval, 100 km, used to create the lines.
While the points are selected, we can use the Remove Duplicates transform operator to eliminate any duplicated points. There will be duplicated points since four lines come together at each intersection and thus creating a point at the end of each line results in coincident points at the intersections.
We don’t need the lines anymore so we can delete them. The easiest way to do this is to press CTRL-T to select by type again (the selection modes should still be set to select lines only) and then press Delete to blow away the lines.
The result is a grid of points that are separated by 100 kilometers.
Step 3: Eliminate points over water using Spatial Overlays
Our next task is to eliminate all points that are not located over land areas. We begin the task by selecting all points and saving them (using the Selections pane ) to a saved selection called Points. To do so, open the Selections pane.
Select all of the points by pushing in Select Points select objects button only and pressing CTRL-T to select by type. Save the selection into the Selections pane and name it Points.
We also need to save the areas. To do so, push in the Select Areas select objects button only and press CTRL-T to select by type. Save the selection into the Selections pane and name it Areas.
The above two steps are not illustrated. Note the use of CTRL-T for speed. We could have also used the Edit - Select By Type menu choice if preferred.
In the Selections pane we now have two saved selections. One saved selection is called Areas and the other is called Points. We will use these saved selections with the Spatial Overlay dialog.
Launch the Spatial Overlays dialog by choosing Drawing - Spatial Overlays. In the dialog choose the saved selection called Areas as the Source and the saved selection called Points as the Target. Choose Areas to contained points as the Method. This tells Manifold to transfer the field values in accordance with the Transfer Rules from those objects in the source set to those objects in the target. We will transfer the field values from the areas to all points within the areas. Press OK.
In complex maps or those with many intricate areas, spatial overlays can take a long time to run. The geometric computation to determine if a point is inside or outside a given area can be very complex. Remember that areas in Manifold can be topologically branched objects where a single area object can have holes and islands. The computation to deal with arbitrarily complex topology can be very time consuming. This particular example will take approximately five to fifteen minutes to compute on desktop machines in the 500Mhz to 1 gigahertz range. Increasing the number of points or the number or complexity of the areas will increase the time required.
The spatial overlays operation will copy the field values from the areas to the points they contain. Every point located over a land area will receive the value 1 in its Land column. All points over water will stay with the default value of 0 in their Land column which was placed there when they were created from the grid of lines using the Points transform.
To create a grid of points that exists over land areas, all we need do now is select all points with a value of 0 and delete them. There are many ways of doing this, but we will use a somewhat indirect method to illustrate a few more techniques in Manifold.
Open the drawing's table and click on the Land column to sort the table by that column. Scroll down to the first record with a value of 1 in the Land column. Ctrl-click on that record to select it. Scroll down to the bottom of the table to the last record with a value of 1 in the Land column and SHIFT-CTRL-click on that record to select all the records between the two clicks, thus selecting all objects with a value of 1 in the Land column.
In the drawing window, we can see that this has selected all of the land areas as well as the points over land. To eliminate the points over water, we can choose Edit - Select Inverse (which selects only the points over water) and press Delete.
From here on in it is more convenient to work in a map window. We create a map from the Mexico_eg Drawing and add a drawing layer to the map that we call Nodes. We will also add a drawing layer we call Links. We will move the points from the Mexico drawing to the Nodes drawing layer. First, we select all of the points (using CTRL-T or Edit - Select By Type) and then we cut the points using CTRL-X or Edit - Cut, click on the Nodes layer tab and then paste the points using CTRL-V or Edit - Paste.
When pasting the points into the new layer, Manifold will raise a dialog asking us how to paste the fields for the points. We don't really need any of the fields any more so it doesn't matter whether we paste the fields or not. The result will be a new drawing layer filled with points that are all above land areas in Mexico, as seen in the illustration above.
Step 4: Build a network
Our task now is to use the grid of points to build a network. We will use the Distance Network transform to wire up links between nearby points. To use this transform sensibly we have to figure out what the right distance is to specify that will create links between neighboring points.
The Tracker tool can help us. We will use the tool to measure distances.
Using the tracker tool, we can measure the distance from one point to its diagonal neighbor. It turns out this distance is approximately 141 kilometers (as the more mathematically inclined reader already knew, since the grid of points is 100 kilometers apart). The illustration above shows the use of the tracker together with the Snap to achieve precise measurement of distance between points.
That distance measurement means that if we want the Distance Network to build links to the immediate horizontal, vertical and diagonal neighboring points we should use a distance of 150000 meters. Click on the Links layer in the map so that the new lines will be created there. We then load the transform toolbar as seen above and press Apply.
The result is that the lines created by the Distance Network appear in the Links layer in our map. [For the illustration above we have also formatted the Nodes layer so that points in the layer are bright green dots.]
Some housekeeping: The Distance Network solver will create duplicates of some links. We eradicate these by running the Remove Duplicates transform in the Links layer.
One other item of housekeeping: At least one link has been created over water, across the Sea of Cortez between the Baja peninsula and mainland Mexico.
We can zoom into the map, select the unwanted link and press the Delete key to delete it.
For a small map and a small network as used in this example it is easiest to delete any links created over water by hand. For more complex networks, we can use spatial overlays once more to transfer the value 1 to all links that are contained by the land areas. We can then remove all links with a value of 0.
Step 5: Find the shortest path
All of the above steps, for all of their apparent intricacy served only to create the network we will now use to find shortest paths. The geometry of the network captures the essential information, where are paths that go over land and where are water regions to be avoided. All the rest is just a trivial matter of finding the shortest path through a network.
To find the shortest path between two points we click on the Nodes layer and select two points. In the example above, we've selected one point at the tip of the Baja peninsula and another point at near the eastern end of Mexico.
We then click on Links and select all of the lines in that layer (we do this by pressing CTRL-A or choosing Edit - Select All since there are only lines in this layer).
We then load the transform toolbar with the settings seen above. This instructs Manifold to use the current selection (two points and a network of lines) with the Select Shortest Path transform operator to select the links that comprise the shortest path between the two points.
Press Apply and the shortest path will be selected.
To see the shortest path better, we can press CTRL-C or Edit - Copy to copy the links involved and then paste them into a new drawing layer called Path. We can then format the lines in Path in a larger size so they stand out better.
Discussion
Clearly, the above method results in an approximation to the "perfect" shortest path. As the grid of points and resultant network get denser the approximation comes closer and closer to the shortest path that would be obtained if the path were not constrained to travel over a network.
Note also that the above procedure can be generalized to build networks within given regions. For example, suppose we had a surface that showed the terrain elevations in Mexico. Perhaps we are interested not just in overland paths, but only in those overland paths that stay below an elevation of 1000 meters. We could use the surface to build contour areas. We could then use spatial overlays to mark all points in the grid that fall within contour areas that are lower than 1000 meters in elevation and eliminate higher points. If we build a distance network using the remaining points we will have a network that exists only in those overland locations that are below 1000 meters elevation.
Suppose we were interested in travel between random points and not just those points on our grid? Perhaps, for example, we study Mayan civilization and we want to know the shortest paths between various Mayan cities. These are easy to add: after creating a regular grid of points we simply copy the points showing the locations of the cities and add them to the layer in which the grid of points is located. We then create a distance network using the combined grid of points and the irregularly arranged city points. To find shortest paths we can then use our layer of city points to select start and end points. Since copies of these points were part of the set of points used to create the distance network we know that each of the city points is correctly located at the end of links in the network.
This procedure describes a highly interactive approach to creating and using networks for special purposes. We might want to add some analytic dimension, such as a Viewbot that reports the sum of the lengths of lines in the selection. If we select the shortest path using the Select Shortest Path transform we can then see immediately the length of the shortest path.
If we like, we might copy the shortest path and place it in its own layer where we can run the Join Lines transform to create one line from the path.
We could then create a label using the Length (I) intrinsic field to label the shortest path with the length, as seen above. If we had many shortest paths in our map, such as the various shortest paths between cities, we could label all of the shortest paths with their lengths.
We used the above example to mark points that occurred over a relatively simple landform. The same procedure would have worked fine had the landforms included lakes or other more complex water features.