Automated Roading

To view the tour, click here.

BCS has developed a procedure for automated generation of a road network within a geographic region, taking existing roads into account. This procedure uses a digital elevation model (DEM) and 3-D hydrography data to determine minimum-cost routes that interconnect a number of pre-specified source and sink points within the region. The initial application of this procedure is in spatially explicit timber supply modeling, to support the need for a forest road network that connects the cutblocks (sources) to exit points (sinks).

The automated roading procedure involves three stages:

1. In the first stage, the source and sink points for the road network are identified. Then these points, along with the points in the DEM and those contained in the hydrography and existing roads linework, are triangulated using an algorithm developed by BCS that preserves this linework as edges in the triangulation. Each edge in this triangulation defines a potential road segment.
2. In the second stage, the edges of the triangulation are assigned costs based on their properties. These can include length, forward slope, cross slope, need for bridging, and whether the edge coincides with an existing road or a hydrographic feature.
3. In the third stage, a variant of Dijkstra's minimum-cost algorithm is applied to generate the road network. The technique starts at the sink points and determines the minimum-cost paths connecting the sink points to the source points.

Appropriate choices for the costs can lead to very realistic paths (e.g., maintaining gentle slopes, switch-backing up a hillside, and/or minimizing the number of waterbody crossings). An extension of the algorithm also allows paths to be produced that discourage sharp turns, further enhancing the realism of the resulting paths.

The tour shows the input data and the final computed road network (a set of road trees) for a coastal region of British Columbia. Several details illustrating the stages of the automated roading process, and showing the DEM points and the triangulation, are also shown in the tour. It can be seen that the computed network makes substantial use of existing roads, and tends to follow contours or take gently sloping paths when building new roads.

Note on viewing images. Comparison between the full images in this tour is most effective if the entire image fits on the screen. If only a portion of the image appears on your screen, try pressing the F11 key to toggle full-screen mode, or try increasing your screen resolution.