Topic 9 – Slope, Distance and Connectivity Algorithms Beyond Mapping book

There’s More Than One Way to Figure Slope  describes procedures for calculating surface slope and its varied applications

Distance Is Simple and Straight Forward  describes simple distance calculation as a propagating wavefront

Rubber Rulers Fit Reality Better  describes procedures for calculating effective distance that considers intervening absolute and relative barriers

describes procedures for calculating optimal paths and routing corridors

describes viewshed and visual exposure procedures

Note: The processing and figures discussed in this topic were derived using MapCalcTM software.  See www.innovativegis.com to download a free MapCalc Learner version with tutorial materials for classroom and self-learning map analysis concepts and procedures.

______________________________

There’s More Than One Way to Figure Slope

(GIS World, September 1992)

…“you knowest me not” (Shakespeare’s Romeo and Juliet)

Romeo speaks these famous lines as he attempts to befriend his family's enemy, Tybalt.  However, as the scene unfolds, Romeo wields his sword and runs him through-- maybe Tybalt knowest him too well?  No, it's just plain old ignorance.  Romeo knowest his secret marriage to Juliet maketh him Tybalt's brother, but Tybalt knowest not such portentous information.

What's all this got to do with GIS?  A simple lesson-- knowest thy GIS operations, or thee shalt be gored.  Take the simple concept of slope.  We all remember Ms. Deal's explanation (the generic geometry persona) of "rise over run."  If the rise is 10 feet when you walk (or run) 100 feet, then the slope is 10/100 * 100%= 10 percent slope.  There, the concept is easy.  So is the practice.  Boy Scouts and civil engineers should recall sighting through their clinometers and dumpy levels to measure slope.

But what's a slope map?  Isn't it just the same concept and practice jammed into a GIS?  Or is it something else, you may knowest not?  In a nutshell, it is a continuous distribution of slope (rise over run) throughout an area.  Or stated another way, it is the trigonometric tangent taken in all directions.  Or, the three-dimensional derivative of a digital terrain model.  Bah!  You might be thinking, "this stuff is too techy, I'll just ignore it and stick with Ms. Deal's comfortable concept."

No, try sticking it out.  For those with GW issues going way back, an overview of this subject was made in the June '90 issue (GIS World, Vol. 3 No. 3).  But for now let's get down to the nitty-gritty-- how you derive a slope map.  In most offices it is an ocular/manual process.  You look at a map and if the contour lines are close together, you mark the area as "steep."   If they are far apart, you circle it as "gentle."  Anything you didn't mark must be "moderate."   As a more exacting alternative, you could count the number of contour lines per unit of distance and calculate the percent slope, but that's a lot of work.  You might construct a ruler-like guide, but using it is still inhumane.

More importantly, the procedure is assessing slope along a single transect.  As you stand on the side of a hill, isn't there a bunch of different slope transects-- down, up, and across from you?  A water drop recognizes the steepest.  A weary hiker responses to the minimum slope.  A developer usually assesses the overall slope.  In the real world, we need several different slope algorithms for different application requirements.

An interesting physical slope procedure involves creating a black and white negative of a map's contour lines.  In printing the negative, the paper is rapidly "wiggled" about a pivot at its center.  Those areas with closely spaced contours (steep) do not expose the paper to as much light as those areas where the contours are far apart (gentle).  The result is a grey-scale map progressing from dark areas having gentle slopes to light areas having steep slopes.  Now we have a real slope map-- a robust range of slope conditions and a procedure considering all of the slopes about each location throughout an area.

In a somewhat analogous fashion, a series of grid cells can be overlaid on a map of contour lines.  The number of lines within each cell is counted-- the more lines the steeper the slope.  This approach was used in early vector systems, but requires considerable computation and is sensitive to the spacing and positioning of the analysis grid.

Most slope processing is done with data formatted as a Digital Elevation Model (DEM).  The DEM uses a raster format of regularly spaced elevation data.  Figure 1 shows a small portion of a typical data set, with each cell containing a value approximating its overall elevation.  As there is only one value in each cell we can't compute a slope for an individual cell without considering the values surrounding it.  In the highlighted 3x3 window there are eight individual slopes, as shown in the calculations accompanying the figure.  The steepest slope of 52% is formed with the center and the cells to its NW and W.  The minimum slope is 10% in the SW direction.

But what about the general slope throughout the entire 3x3 analysis window?  One estimate is 30%, the average of the eight individual slopes.  Another general characterization could be 31%, the median of slopes.  To get an appreciation of this processing, shift the window one column to the right and run through the calculations using the value 459 as the center.  Now imagine doing that a million times with an impatient and irate human pounding at your peripherals.  Show some compassion for your computer-- the basis of a meaningful GIS relationship.

Figure 1.  Example Elevation Data.

An alternative format to DEM is Triangulated Irregular Network (TIN) using irregularly spaced elevation points to form a network of "triangular facets."  Instead of a regular DEM spacing, areas of rapidly changing terrain receive more points than relatively flat areas.  Any three elevation points, when connected, form a triangle floating in three-dimensional space.  Simple (ha!) trigonometry is used to compute the slope of the tilted triangular facets, which are stored as a set of adjoining polygons in conventional vector format.  TIN algorithms vary widely in how they develop the irregular network of points, so their slope maps often are considerably different.

A related raster-approach treats the octants about the center position in the 3x3 window as eight triangular facets.  The slopes of the individual facets are computed and generalized for an overall slope value.  To bring things closer to home, the elevations for the cardinal points along the center cell's sides can be interpolated from the surrounding DEM values.  This refinement incorporates the lateral interactions among the elevation points and often produces different results than those directly using the DEM values.

Now let's stretch our thinking a bit more.  Imagine that the nine elevation values become balls floating above their respective locations, as shown in Figure 2.  Mentally insert a plane and shift it about until it is positioned to minimize the overall distances to the balls.  The result is a "best-fitted plane" summarizing the overall slope in the 3x3 window.

The techy-types will recognize this process as similar to fitting a regression line to a set of data points in two-dimensional space.  In this case, it is a plane in three-dimensional space.  It is an intimidating set of equations, with a lot of Greek letters and subscripts to "minimize the sum of the squared deviations" from the plane to the points.  Solid geometry calculations, based on the plane's "direction cosines," determine the slope (and aspect) of the plane.

This approach can yield radically different slope estimates to the others discussed.  Often the results are closer to your visceral feeling of slope as stand on the side of a hill... often they are not.  Consider a mountain peak, or a terrain depression.  Geometry characterizes these features as a cone, with eight steeply sloped sides-- result is very steep.  The fitted-plane approach considers these features as a balanced transition in slopes-- result is perfectly flat.  Which way do you view it?

Figure 2.  "Best-Fitted" Plane Using Vector Algebra.

Another procedure for fitting a plane to the elevation data uses vector algebra, as illustrated in the right portion of figure 2.  In concept, the mathematics draws each of the eight slopes as a line in the proper direction and relative length of the slope value (individual vectors).  Now comes the fun part.  Starting with the NW line, successively connect the lines as shown in the figure (cumulative vectors).  The civil engineer will recognize this procedure as similar to the latitude and departure sums in "closing a survey transect."  The physicist sees it as the vector sums of atomic movements in a cloud chamber.  We think of it as the serpentine path we walked in downtown Manhattan.

If the vector sum happens to close on the starting point, the slope is 0%.  A gap between the starting and end points is called the "resultant vector."  The length of the resultant vector is the slope of a plane fitting the floating data points, which in turn, is interpreted as the general slope of the terrain.  In the example, the resultant slope is 36%, oriented toward the NW.

Considering our calculations, what's the slope-- 52, 10, 30, 31, or 36?  They're all correct.  The point is, it depends... it depends on your understanding of the application's requirement and the algorithm's sensitivity.  A compatible marriage between application and algorithm must be struck.  "With this kiss, I die" might be your last words if you "knowest not" your GIS operations and blindly apply any old GIS result from clicking your mouse on the slope icon.

Distance Is Simple and Straight Forward

(GIS World, October 1992)

For those with a GIS World archive, an overview of the evolving concept of distance was made in the September 1989 issue (GIS World, Vol. 2, No. 5).  The objective of this revisiting of the subject focuses on the real stuff-- how a GIS derives a distance map.  The basic concept of distance measurement involves two things-- a unit and a procedure.  The tic-marks on your ruler establishes the unit.  If you are an old wood-cutter like me, a quarter of an inch is good enough.  If more accuracy is required, you choose a ruler with finer spacing.  The fact that these units are etched on side of a straight-edge implies that the procedure of measurement is "shortest, straight line between two points."  You align the ruler between two points and count the tic-marks.  There, that's it-- simple, satisfying and comfortable.

But what is a ruler?  Actually, it is just one row of an implied grid you have placed over the map.  In essence, the ruler forms a reference grid, with the distance between each tic-mark forming one side of a grid cell.  You simply align the imaginary grid and count the cells along the row.  That's easy for you, but tough for a computer.  To measure distance like this, the computer would have to recalculate a transformed reference grid for each measurement.  Pythagoras anticipated this potential for computer-abuse several years ago and developed the Pythagorean Theorem.  The procedure keeps the reference grid constant and relates the distance between two points as the hypotenuse of a right triangle formed by the grid's rows and columns.  There that's it-- simple, satisfying and comfortable for the high school mathematician lurking in all of us.

Figure 3.  Characterizing Simple Proximity.

A GIS that's beyond mapping, however, "asks not what math can do for it, but what it can do for math."  How about a different way of measuring distance?  Instead of measuring between just two points, let's expand the concept of distance to that of proximity-- distance among sets of points.  For a raster procedure, consider the analysis grid on the left side of figure 3.  The distance from the cell in the lower-right corner (Col 6, Row 6) to each of its three neighbors is either 1.000 grid space (orthogonal), or 1.414 (diagonal).  Similar to the tic-marks on your ruler, the analysis grid spacing can be very small for the exacting types, or fairly course for the rest of us.

The distance to a cell in the next "ring" is a combination of the information in the previous ring and the type of movement to the cell.  For example, position Col 4, Row 6 is 1.000 + 1.000= 2.000 grid spaces as the shortest path is orthogonal-orthogonal.  You could move diagonal-diagonal passing through position Col 5, Row 5, as shown with the dotted line.  But that route wouldn't be "shortest" as it results in a total distance of 1.414 + 1.414= 2.828 grid spaces.  The rest of the ring assignments involves a similar test of all possible movements to each cell, retaining the smallest total distance.  With tireless devotion, your computer repeats this process for each successive ring.  The missing information in the figure allows you to be the hero and complete the simple proximity map.  Keep in mind that there are three possible movements from ring cells into each of the adjacent cells.  (Hint-- one of the answers is 7.070).

This procedure is radically different from either your ruler or Pythagoras's theorem.  It is more like nailing your ruler and spinning it while the tic-marks trace concentric circles-- one unit away, two units away, etc.  Another analogy is tossing a rock into a still pond with the ripples indicating increasing distance.  One of the major advantages of this procedure is that entire sets of "starting locations" can be considered at the same time.  It's like tossing a handful of rocks into the pond.  Each rock begins a series of ripples.  When the ripples from two rocks meet, they dissipate and indicate the halfway point.  The repeated test for the smallest accumulated distance insures that the halfway "bump" is identified.  The result is a distance assignment (rippling ring value) from every location to its nearest starting location.

If your conceptual rocks represented the locations of houses, the result would be a map of the distance to the nearest house for an entire study area.  Now imagine tossing an old twisted branch into the water.  The ripples will form concentric rings in the shape of the branch.  If your branch's shape represented a road network, the result would be a map of the distance to the nearest road.  By changing your concept of distance and measurement procedure, proximity maps can be generated in an instant compared to the time you or Pythagoras would take.

However, the rippling results are not as accurate for a given unit spacing.  The orthogonal and diagonal distances are right on, but the other measurements tend to overstate the true distance.  For example, the rippling distance estimate for position 3,1 is 6.242 grid spaces.  Pythagoras would calculate the distance as C= ((3**2 + 5**2)) **1/2)= 5.831.  That's a difference of .411 grid spaces, or 7% error.  As most raster systems store integer values, the rounding usually absorbs the error.  But if accuracy between two points is a must, you had better forego the advantages of proximity measurement.

A vector system, with its extremely fine reference grid, generates exact Pythagorean distances.  However, proximity calculations are not its forte.  The right side of the accompanying figure shows the basic considerations in generating proximity "buffers" in a vector system.  First, the "reach" of the buffer is established by the user-- as before, it can be very small for the exacting types, or fairly course for the rest of us.  For point features, this distance serves as the increment for increasing radii of a series of concentric circles.  Your high school geometry experience with a compass should provide a good conceptualization of this process.  The GIS, however, evaluates the equation for a circle given the center and radius to solve for the end points of the series of line segments forming the boundary.

For line and area features, the reach is used to increment a series of parallel lines about the feature.  Again, your compass work in geometry should rekindle the draftsman's approach.  The GIS, on the other hand, uses the slope of each line segment and the equation for a straight line to calculate the end points of the parallel lines.  "Crosses" and "gaps" occur wherever there is a bend.  The intersection of the parallel lines on inside bends are clipped and the intersection is used as the common end point.  Gaps on outside bends present a different problem.  Some systems simply fill the gaps with a new line segment.  Others extend the parallel lines until they intersect.  The buffers around the square feature shows that these two approaches can have radically different results.  You can even take an additional step and fit a spline-fitting algorithm to smooth the lines.

A more important concern is how to account for "buffer bumping."  It's only moderately taxing to calculate the series buffers around individual features, but it's a monumental task to identify and eliminate any buffer overlap.  Even the most elegant procedure requires a ponderous pile of computer code and prodigious patience by the user.  Also, the different approaches produce different results, affecting data exchange and integration among various systems.  The only guarantee is that a stream proximity map on system A will be different than a stream proximity map on system B.

Another guarantee is that new concepts of distance are emerging as GIS goes beyond mapping.  The next section will focus on the twisted concept of "effective" proximity which is anything but simple and straight forward.

_____________________

As with all Beyond Mapping articles, allow me to apologize in advance for the "poetic license" invoked in this terse treatment of a complex subject.  Readers interested in more information on distance algorithms should consult the classic text, The Geography of Movement, by Lowe and Moryadas, 1975, Houghton Miffen publishers.

Rubber Rulers Fit Reality Better

(GIS World, November 1992)

It must be a joke, like a left-handed wrench, a bucket of steam or a snipe hunt.  Or it could be the softening of blows in the classroom through enlightened child-abuse laws.  Actually, a rubber ruler often is more useful and accurate than the old straight-edge version.  It can bend, compress and stretch throughout a mapped area as different features are encountered.  After all it's more realistic, as the straight path is rarely what most of us follow.

The last section established the procedure for computing simple proximity maps as forming a series of concentric rings.  The ability to characterize the continuous distribution of simple, straight-line distances to sets of features like houses and roads is useful in a multitude of applications.  More importantly, the GIS procedure allows measurement of effective proximity recognizing absolute and relative barriers to movement, as shown in figure 1.

As discussed in the last issue, the proximity to the starting location at Col 6, Row 6 is calculated as a series of rings.  However, this time we'll use the map on the left containing "friction" values to incorporate the relative ease of movement through each grid cell.  A friction value of 2.00 is twice as difficult to cross as one with 1.00.  Absolute barriers, such as a lake to a non-swimming hiker, are identified as infinitely far away and forces all movement around these areas.

Step Distance= .5 * (GSdistance * FfactorN)

Accumulated Distance= Previous + Sdistance1 + Sdistance2

Minimum Distance is Shortest, Non-Straight Distance

Figure 1.  Characterizing Effective Proximity.

A generalized procedure for calculating effective distance using the friction values is as follows (refer to the figure).

Step 1 - identify the ring cells ("starting cell" 6,6 for first iteration).

Step 2 - identify the set of immediate adjacent cells (positions 5,5; 5,6; and 6,5 for first iteration).

Step 3 - note the friction factors for the ring cell and the set of adjacent cells (6,6=1.00; 5,5=2.00; 5,6=1.00; 6,5=1.00).

Step 4 - calculate the distance, in half-steps, to each of the adjacent cells from each ring cell by multiplying 1.000 for orthogonal or 1.414 for diagonal movement by the corresponding friction factor...

.5 * (GSdirection * Friction Factor)

For example, the first iteration ring from the center of 6,6 to the center of position

5,5 is    .5 * (1.414 * 1.00)=         .707

.5 * (1.414 * 2.00)=         1.414

2.121

5,6 is    .5 * (1.000 * 1.00)=         .500

.5 * (1.000 * 1.00)=         .500

1.000

6,5 is    .5 * (1.000 * 1.00)=         .500

.5 * (1.000 * 1.00)=         .500

1.000

Step 5 - choose the smallest accumulated distance value for each of the adjacent cells.

Repeat - for successive rings, the old adjacent cells become the new ring cells (the next iteration uses 5,5; 5,6 and 6,5 as the new ring cells).

Whew!  That's a lot of work.  Good thing you have a silicon slave to do the dirty work.  Just for fun (ha!) let's try evaluating the effective distance for position 2,1...

If you move from position 3,1 its—

.5 * (1.000 * 3.00)=                     1.50

.5 * (1.000 * 3.00)=                     1.50

3.00

plus previous distance=                                   16.93

equals accumulated distance=                                     19.93

…If you move from position 3,2 its—

.5 * (1.414 * 4.00)=                     2.83

.5 * (1.414 * 3.00)=                     2.12

4.95

plus previous distance=                                   15.78

equals accumulated distance=                         20.73

…If you move from position 2,2 its—

.5 * (1.000 * 2.00)=                     1.00

.5 * (1.000 * 3.00)=                     1.50

2.50

plus previous distance=                    18.36

equals accumulated distance=                   20.86

Finally, choose the smallest accumulated distance value of 19.93, assign it to position 2,1 and draw a horizontal arrow from position 3,1.  Provided your patience holds, repeat the process for the last two positions on your own.

The result is a map indicating the effective distance from the starting location(s) to everywhere in the study area.  If the "friction factors" indicate time in minutes to cross each cell, then the accumulated time to move to position 2,1 by the shortest route is 19.93 minutes.  If the friction factors indicate cost of haul road construction in thousands of dollars, then the total cost to construct a road to position 2,1 by the least cost route is \$19,930.  A similar interpretation holds for the proximity values in every other cell.

To make the distance measurement procedure even more realistic, the nature of the "mover" must be considered.  The classic example is when two cars start moving toward each other.  If they travel at different speeds, the geographic midpoint along the route will not be the location the cars actually meet.  This disparity can be accommodated by assigning a "weighting factor" to each starter cell indicating its relative movement nature-- a value of 2.00 indicates a mover that is twice as "slow" as a 1.00 value.  To account for this additional information, the basic calculation in Step 4 is expanded to become

.           5 * (GSdirection * Friction Factor * Weighting Factor)

Under the same movement direction and friction conditions, a "slow" mover will take longer to traverse a given cell.  Or, if the friction is in dollars, an "expensive" mover will cost more to traverse a given cell (e.g., paved versus gravel road construction).

I bet your probing intellect has already taken the next step-- dynamic effective distance.  We all know that real movement involves a complex interaction of direction, accumulation and momentum.  For example, a hiker walks slower up a steep slope than down it.  And, as the hike gets longer and longer, all but the toughest slow down.  If a long, steep slope is encountered after hiking several hours, most of us interpret it as an omen to stop for quiet contemplation.

The extension of the basic procedure to dynamic effective distance is still in the hands of GIS researchers.  Most of the approaches use a "look-up table" to update the "friction factor" in Step 4.  For example, under ideal circumstances you might hike three miles an hour in gentle terrain.  When a "ring" encounters an adjacent cell which is steep (indicated on the slope map) and the movement is uphill (indicated on the aspect map), the normal friction is multiplied by the "friction multiplier" in the look-up table for the "steep-up" condition.  This might reduce your pace to one mile per hour.  A three-dimensional table can be used to simultaneously introduce fatigue-- the "steep-up-long" condition might equate to zero miles per hour.

See how far you have come?  From the straight forward interpretation of distance ingrained in your ruler and Pythagoras's theorem, to the twisted movement around and through intervening barriers.  This bazaar discussion should confirm that GIS is more different than it is the same as traditional mapping.  The next issue will discuss how the shortest, but "not necessarily straight path," is identified.

_____________________

As with all Beyond Mapping articles, allow me to apologize in advance for the "poetic license" invoked in this terse treatment of a complex subject.  Readers with the pMAP Tutorial disk should review the slide show and tutorial on "Effective Sediment Loading."  An excellent discussion of effective proximity is in C. Dana Tomlin's text, Geographical Information Systems and Cartographic Modeling, available through the GIS World Bookshelf.

Twists and Contortions Lead to Connectivity

(GIS World, December 1992)

…identifying optimal paths and routing corridors.

The last couple of sections challenged the assumption that all distance measurement is the "shortest, straight line between two points."  The concept of proximity relaxed the "between two points" requirement.  The concept of movement, through absolute and relative barriers, relaxed the "straight line" requirement.  What's left? --"shortest," but not necessarily straight and often among sets points.

Where does all this twisted and contorted logic lead?  That's the point-- connectivity.  You know, "the state of being connected," as Webster would say.  Since the rubber ruler algorithm relaxed the simplifying assumption that all connections are straight, it seems fair to ask, "then what is the shortest route, if it isn't straight."  In terms of movement, connectivity among features involves the computation of optimal paths.  It all starts with the calculation of an "accumulation surface," like the one shown on the left side of the accompanying figure.  This is a three-dimensional plot of the accumulated distance table you completed last month.  Remember?  Your homework involved that nasty, iterative, five-step algorithm for determining the friction factor weighted distances of successive rings about a starting location.  Whew!  The values floating above the surface are the answers to the missing table elements-- 17.54, 19.54 and 19.94.  How did you do?

But that's all behind us.  By comparison, the optimal path algorithm is a piece of cake-- just choose the steepest downhill path over the accumulated surface.  All of the information about optimal routes is incorporated in the surface.  Recall, that as the successive rings emanate from a starting location, they move like waves bending around absolute barriers and shortening in areas of higher friction.  The result is a "continuously increasing" surface that captures the shortest distance as values assigned to each cell.

In the "raster" example shown in the figure, the steepest downhill path from the upper left corner (position 1,1) moves along the left side of the "mountain" of friction in the center.  The path is determined by successively evaluating the accumulated distance of adjoining cells and choosing the smallest value.  For example, the first step could move to the right (to position 2,1) from 19.54 to 19.94 units away.  But that would be stupid, as it is farther away than the starting position itself.  The other two potential steps, to 18.36 or 17.54, make sense, but 17.54 makes the most sense as it gets you a lot closer.  So you jump to the lowest value at position 1,2.  The process is repeated until you reach the lowest value of 0.0 at position 6,6.

Figure 1.  Establishing Shortest, Non-Straight Routes.

Say, that's where we started measuring distance.  Let's get this right-- first you measure distance from a location (effective distance map), then you identify another location and move downhill like a rain drop on a roof.  Yep, that's it.  The path you trace identifies the route of the distance wavefront (successive rings) that got there first-- shortest.  But why stop there, when you could calculate optimal path density?  Imagine commanding your silicon slave to compute the optimal paths from all locations down the surface, while keeping track of the number of paths passing through each location.  Like gullies on a terrain surface, areas of minimal impedance collect a lot of paths.  Ready for another step?-- weighted optimal path density.  In this instance, you assign an importance value (weight) to each starting location, and, instead of merely counting the number of paths through each location, you sum the weights.

For the techy types, the optimal path algorithm for raster systems should be apparent.  It's just a couple of nested loops that allow you to test for the biggest downward step of "accumulated distance" among the eight neighboring cells.  You move to that position and repeat.  If two or more equally optimal steps should occur, simply move to them.  The algorithm stops when there aren't any more downhill steps.  The result is a series of cells which form the optimal path from the specified "starter" location to the bottom of the accumulation surface.  Optimal path density requires you to build another map that counts the number paths passing through each cell.  Weighted optimal path density sums the weights of the starter locations, rather than simply counting them.

The vector solution is similar in concept, but its algorithm is a bit more tricky to implement.  In the above discussion, you could substitute the words "line segment" for "cell" and not be too far off.  First, you locate a starting location on a network of lines.  The location might be a fire station on a particular street in your town.  Then you calculate an "accumulation network" in which each line segment end point receives a value indicating shortest distance to the fire station along the street network.  To conceptualize this process, the raster explanation used rippling waves from a tossed rock in a pond.  This time, imagine waves rippling along a canal system.  They are constrained to the linear network, with each point being farther away than the one preceding it.  The right side of the accompanying figure shows a three-dimensional plot of this effect.  It looks a lot like a roll-a-coaster track with the bottom at the fire station (the point closest to you).  Now locate a line segment with a "house-on-fire."  The algorithm hops from the house to "lily pad to lily pad" (line segment end points), always choosing the smallest value.  As before, this "steepest downhill" path traces the wavefront that got there first-- shortest route to the fire.  In a similar fashion, the concepts of optimal path density and weighted optimal path density from multiple starting locations remain intact.

What makes the vector solution testier is that the adjacency relationship among the lines is not as neatly organized as in the raster solution.  This relationship, or "topology," describing which cell abuts which cell is implicit in the matrix of numbers.  On the other hand, the topology in a vector system must be stored in a database.  A distinction between a vertex (point along a line) and a node (point of intersecting lines) must be maintained.  These points combine to form chains which, in a cascading fashion, relate to one another.  Ingenuity in database design and creative use of indices and pointers for quick access to the topology are what separates one system from another.  Unfettered respect should be heaped upon the programming wizards that make all this happen.

However, regardless of the programming complexity, the essence of the optimal path algorithm remains the same-- measure distance from a location (effective distance map), then locate another location and move downhill.  Impedance to movement can be absolute and relative barriers such as one-way streets, no left turn and speed limits.  These "friction factors" are assigned to the individual line segments, and used to construct an accumulation distance network in a manner similar to that discussed last month.  It is just that in a vector system, movement is constrained to an organized set of lines, instead of an organized set of cells.

Optimal path connectivity isn't the only type of connection between map locations.  Consider narrowness-- the shortest cord connecting opposing edges.  Like optimal paths, narrowness is a two part algorithm based on accumulated distance.  For example, to compute a narrowness map of a meadow your algorithm first selects a "starter" location within the meadow.  It then calculates the accumulated distance from the starter until the successive rings have assigned a value to each of the meadow edge cells.  Now choose one of the edge cells and determine the "opposing" edge cell which lies on a straight line through the starter cell.  Sum the two edge cell distance values to compute the length of the cord.  Iteratively evaluate all of the cords passing through the starter cell, keeping track of the smallest length.  Finally, assign the minimum length to the starter cell as its narrowness value.  Move to another meadow cell and repeat the process until all meadow locations have narrowness values assigned.

As you can well imagine, this is a computer-abusive operation.  Even with algorithm trickery and user limits, it will send the best of workstations to "deep space" for quite awhile.  Particularly when the user wants to compute the "effective narrowness" (non-straight cords respecting absolute and relative barriers) of all the timber stands within a 1000x1000 map matrix.  But GIS isn't just concerned with making things easy; be it for man or machine.  It is for making things more realistic which, hopefully, leads to better decisions.  Optimal path and narrowness connectivity are uneasy concepts leading in that direction.

Take a New Look at Visual Connectivity (GIS World, January 1993)

Remember the warning the Beast gave Belle, "Don't go into the west wing."  Such is the Byzantine world of GIS-- full of unfamiliar bells and whistles which tempt our curiosity.  Spatial derivative, effective distance, optimal paths and narrowness are a few of these discussed in recent issues.  Let's continue our groping in the realm of the unfamiliar with visual connectivity.  As before, the focus will be on the computational approach.

As an old Signal Corps officer, I am very familiar with the manual procedure for determining FM radio's line-of-sight connectivity.  You plot the position of the General's tent (down in the valley near the good fishing hole) and spend the rest of the day drawing potential lines to the field encampments.  You note when your drafted lines "dig into the dirt" as indicated by the higher contour values of ridges.  In an iterative fashion, you narrow down the placement of transmitters and repeaters until there is line-of-sight connectivity among all the troops.  About then you are advised that the fishing has played out and the General's tent is being moved to the next valley.

In a mathematical context, the drafted lines are evaluating the relationship of the change in elevation (rise) per unit of horizontal distance (run).  The "rise to run" ratio, or tangent, determines whether one location can be seen from another.  Consider the line-of-sight plot shown in left portion of Figure 1.  Points along a line are visible as long as their tangents exceed those of all intervening points (i.e., rise above).  The seen locations are depicted by the shaded area.  The tangent values at the last two points are smaller than that of the fourth point, therefore, they are marked as not seen (unshaded).  Now identify another "ray in space" and calculate where it digs into the dirt.  That's it-- a simple, straight forward adaptation of high school geometry's characterization of a familiar drafting technique.

But, as we have seen before, a mathematical solution can be different from a machine solution, or algorithm.  Just for fun, let's invoke the "rippling" wave concept used in measuring distance.  "Splash," the rock falls in the lower-left corner of the map (see Figure 1).  The elevation of the "viewer cell" is noted, along with the elevations of it's eight neighboring cells.  The neighboring cells are marked as seen and eight "tangents to be beat" are calculated and stored.  Attention is moved to the next ripple where the tangents are calculated and tested to determine if they exceed those on the inside ring.  Locations with smaller tangents are marked as not seen.  Those with larger tangents are marked as seen and the respective tangents to be beat are updated.

It is just what your machine likes-- neat organization.  The ripple number implicitly tracks of the horizontal distance.  The elevations are identified by the column and row designation of current ripple's set of cells.  The tangents to be beat are identified by cell positions of the previous ripple.  "Splash," followed by a series of rippling waves carry the tangents to be beat, while the visible locations are marked in their wake.  The effects of haze can be introduced by only rippling so far, or adding a visual fall-off weight, such as "inverse distance squared."  The lower map in the right portion of Figure 1 is a planimetric plot of the viewshed of the same point described above.  For reference, the line-of-sight is traced on the planimetric map.  The map on top, drapes the viewshed on the elevation surface.  Note that the line-of-sight shading of visible locations continues up the side of the mountain until the inflection point (ridge top) at the reference ring.

In general, the machine solution is not as exacting as a strict mathematical implementation.  But what it lacks in exactness often is made up in computational speed and additional capabilities.  Consider tossing a handful of rocks (viewer locations) into the pond.  "Splash, splash, ...."  As each ripple pattern is successively evaluated, the resultant map keeps track of the number of viewer locations connected to each map location.  If thirty splashes (viz. houses) see a location, that location is more "visually exposed" than another which has none or just a few.  Instead of a viewshed map, a visual exposure density surface is created.  It is like viewing through a fly's compound eyeball-- a set of lenses (viewer cells) considered as a single viewing entity.  But why stop here?  Imagine the visual exposure density surface of an entire road system.  High values indicate locations with a lot of windshields connected.  You might term these areas "visually vulnerable" to roads.  A sensitive logger might term these areas "trouble" and move the clearcut just over the ridge.

To make the algorithm a bit more realistic, we need to add some additional features.  First, let's add the capability to discriminate among different types of viewers.  For example, we all know a highway has more traffic than a back road.  On the viewers map, assign the value 10 to the highway and 1 to the back road as "weighting factors."  When your rippling wave identifies seen locations, it will add the weight of the viewer cell.  The result is a weighted visual exposure density surface, with areas connected to the highway receiving higher exposure values.  Isn't that more realistic?  You can even simulate an aesthetics rating by assigning positive weights to beautiful things and negative weights to ugly things.  A net weighted visual exposure value of 0 indicates a location that isn't connected to any important feature, or has counter-balancing beauties and uglies in its visual space... far out, man!

Another enhancement is the generation of a prominence map.  As the ripples advance, the difference between the current and the previous tangent identifies the "degree" of visual exposure.  If the difference is 0 or negative, the location is not seen.  As the positive values increase, increasing visual prominence is indicated.  A very large positive difference identifies a location that is "sticking out there like a sore thumb-- you can't miss it."  Couple this concept with the previous one and you have a weighted prominence map.  The algorithm simply multiplies the tangent difference (prominence) times the viewer weight (importance) and keeps a running sum of all positive values for each map location.  The result is a map that summarizes the effective visual exposure throughout a project area to a set of map features.  This is real information for decision-making.

But we aren't there yet.  The final group of enhancements include conditions affecting the line-of-sight.  Suppose your viewing position is atop a 90-foot fire tower.  You had better let the computer know so it can add 90 to the elevation value for your actual viewer height.  You will see at lot more.  What about the dense forest stands scattered throughout the area?  Better let the computer know the visual screening height of each stand so it can add them to the elevation surface.  You will see a lot less.  Finally, suppose there is a set of features that rise above the terrain, but are so thin they really don't block your vision.  These might be a chimney, an antenna and a powerline.  At the instance the algorithm is testing if such a location is seen, its elevation is raised by the feature height to test if it is seen.  However, the surface elevation is used in testing for tangent update to determine if any cells in the next ring are blocked.  Picky, picky, picky.  Sure, but while we are at it, we might as well get things right.

Figure 1.  Establishing Visual Connectivity.

Figure 2 puts this visual analysis thing in perspective.  It is a simple model determining the average visual exposure to both houses and roads for each district in a project area.  The "box and line" flowchart to the right summarizes the model's logic.  The sentences at the bottom list the command lines implementing the processing.  The visual exposure to roads and houses is determined (RADIATE), then calibrated to a common index of relative exposure (RENUMBER).  An overall index is computed (AVERAGE), then summarized for each district (COMPOSITE).  The resultant map shows the district in the upper-left has a very high visual exposure-- not a good place for an eyesore development.  But what have you learned?  How would you change the model to make it more realistic?  Would weighted prominence be a better measure?  What about screening effect of trees?  Or the proximity to roads?  Which houses are most affected? ...that leaves some discussion for next issue-- concepts and procedures in spatial modeling.

_______________________________________