Beyond Mapping III
|
Map
Analysis book with companion CD-ROM for hands-on exercises and further reading |
Building
Accumulation Surfaces — reviews
how proximity analysis and effective distance is used to construct accumulation
surfaces
Analyzing
Accumulation Surfaces — describes
how two surfaces can be analyzed to determine the relative travel-time
advantages
Determining Optimal Path Corridors — describes
a technique for determining the set of nth best
paths between two points
Analyzing Stepped Accumulation Surfaces — describes a technique for forcing an optimal
path through a series of points
Author’s
Notes: The figures in this topic use MapCalcTM
software. An educational CD with online
text, exercises and databases for “hands-on” experience in these and other
grid-based analysis procedures is available for US$21.95 plus shipping and
handling (www.farmgis.com/products/software/mapcalc/
).
<Click here> right-click to download a printer-friendly
version of this topic (.pdf).
(Back to the Table of Contents)
(GeoWorld, October 1997, pg. 26)
“You can’t get there from here,” is often the flippant
response when you ask directions. In many
cases it is a perfectly valid answer, as movement in geographic space is rarely
as straight forward as a straightedge.
Often there are several possible contorted paths that twist and turn in
route to a destination. However, from
the perspective of a ruler there is only one—the “shortest, straight line
connecting two points.” Several Beyond
Mapping columns1 have addressed the concepts and procedures behind
Before we get too far, a quick review might be prudent. Recall that there are primarily two ways to
represent distance in a
The splash technique tracking simple
proximity is a bit less familiar, but conceptually easy. Imagine what happens to a still pond when you
toss in a rock—splash, then one ripple away, then another, and another, until
there’s a whole set of concentric rings about the starting point. If the conditions are the same throughout the
pond, the effect is similar to nailing a ruler at the starting point and
spinning it, while scribing the set of circles formed by dragging the ruler’s
tic marks. In a raster
Now imagine tossing a handful of rocks—splash, one ripple, two ripple, three
ripple, and more radiate out from each of the starting points. When two wave-fronts meet, they stop, with
the point of interference identifying the halfway location between starting
points. The same holds true if you toss
in a set of sticks or pieces of plywood, with the ripple patterns conforming to
the irregular shapes of the objects. The
end result of all the simulated splashing and crashing in a
Figure 25.1. Accumulation surfaces showing the effects of relative and absolute barriers in mapping proximity.
Inset (a) in the accompanying figure is a 3-D plot of a simple proximity surface
radiating from a single point. The
lowest point on the surface contains the value 0 denoting it is “0 grid spaces
away” from the start. Note that the
surface is shaped like a bowl with increasing values (1 away, 2 away,
etc.). The farthest location is in the
upper right corner at a distance of 60 grid spaces * 100 meters/grid space = 6000 meters. The slight depressions along the orthogonal
and diagonal are a result of the slight directional variations in distances
computed by the “splash” algorithm.
But continuous, straight line movement forming a perfect proximity bowl is
rarely the case in the real world.
Effective proximity respects movement around and through barriers—not
“as the crow flies,” but as the crow might walk. Suppose there’s a lake in the way. Inset (b) identifies the absolute barrier
itself as being infinitely far away (fear/reality of drowning). It assigns a value of 69 grid spaces to the
farthest accessible location, indicating that the distance is a 900 meters
farther as a result of going around the lake.
The set of all map values indicate the “shortest, but not necessarily
straight” distances between the starting point and all of the other locations.
However, in winter the lake freezes and can be crossed, though at a much slower
pace on the slippery ice. It represents
a relative barrier that impedes movement, but doesn’t totally restrict
movement. Inset (c) shows the accumulation
surface assuming you walk 5 times slower on the ice. The results show that it’s still 6900 meters
to the opposite corner by going around the lake. However, if you gingerly trek to the center
of the lake, it’s equivalent to traveling 8300 meters
on open land.
Previous Beyond Mapping columns described how the
computer finds the “steepest, downhill path” along an accumulation surface to
locate the “not necessarily straight” optimal path. It’s analogous to a rain drop’s route along
the surface, which effectively retraces the wave front that got there
first. In fact, the rain drop paths from
all locations identify the “shortest, but not necessarily straight set of lines
connecting the origin to everywhere.”
Information you with a ruler, or Pythagorus
with a calculator, could never derive.
But it’s chicken-feed compared to what insights you get by analyzing the
surfaces themselves—see you next time.
_____________________
1 See
Analyzing Accumulation Surfaces
(GeoWorld, November 1997, pg. 30-32)
The previous article
in this series described the nature of accumulation surfaces and how they are
built. Recall that the “splash”
algorithm measures distance from a starting location like waves that spread out
when a rock is tossed into a pond. The
result is a 3-dimensional surface with increasing distance reflected by the
increasing Z values stored in a matrix of grid cells. If absolute and relative barriers to movement
are introduced, these surfaces form unique shapes with ridges and peaks similar
to terrain surfaces.
However, unlike terrain surfaces, accumulation surfaces are always increasing
(no “false-bottoms”) from point, line and areal features designated as starting
locations. Areas with absolute barriers
are identified as infinitely far away and form sheer walls on an accumulation
surface. Relative barriers form hills
and ridges as they identify areas that are passable, but at an increased “cost”
(e.g., more time) per grid space. The valleys
emanating from the starting locations locate corridors of minimal resistance to
movement along the accumulation surface.
Figure 25.2. The
difference between two proximity surfaces identifies the relative geographic
advantage between two locations.
For example, the two
surfaces on the extreme left of the accompanying figure characterize movement
from opposing corners through the horseshoe-shaped relative barrier described
in the previous article. The proximity
from Start1 generally increases from left to right, while the increase from
Start2 is in the opposite direction.
Both surfaces show an abrupt increase when the relative barrier is
encountered, however the shape of the resulting “hill” is different due to the
different directions of the distance waves and the shape of the barrier.
Since the horseshoe ends of the barrier face Start1, the waves easily move into
the center before interacting with the increased impedance of the barrier. The formation of a ridge indicates that some
of the waves moved around the barrier, then penetrated the barrier from the
back side. Any location along the ridge
is equally distant from the start by moving to either side of hill. The locations on the back side of the ridge,
however, are optimally connected to Start1 by moving down the hill to the right
and around the barrier… a counter-intuitive move. Neither ruler nor Pythagorous’ theorem suggest that you must initially move
away from Start1 to begin the optimal route connecting the location to Start1. That’s because they simply assume that all
movement is in a straight line connecting two points—an extremely limiting
assumption in the real world of complex barriers.
The vertical line intersecting both surfaces identifies a map location that is
63 grid spaces from Start1 and only 5 from Statrt2. Since these “shortest, but not necessarily
straight” distances are stored at the same column, row position in the two
proximity matrices, they can be easily retrieved and their difference computed
(63 - 5 = 58). If this is done for all
locations, a difference surface (S1-S2 Surface inset in the middle of the
figure) is generated identifying the relative advantage between Start1 and
Start2 access for all locations throughout the project area.
The “0” line identifies locations that are equally distant between the two
starting locations. It’s similar to the
“perpendicular bisector” you might remember from high school geometry, except
it is bent and twisted reflecting the effect of the intervening barrier on actual
movement. The sign of the difference
indicates who has the advantage—negative values identify locations where Start1
has an advantage; positive values indicate a Start2 advantage. The magnitude of the value identifies the
strength of the advantage. The two
surfaces on the right isolate the relative advantages for both starting
locations. Similar advantage surfaces
can be derived for additional starting locations, keeping in mind that the
“starters” can be any combination of point, line or areal features.
In the example, a +58 denotes a location with a strong advantage for Start2
access… it would be stupid to trek all the way to Start1. If you were a thirsty
animal (or pub patron), why would you travel the extra distance? The liquid libations would have to be a lot
better, or the ambiance and other thirsty organisms much more to your
liking. If that were the case, then the
relative attractiveness of starter locations can be incorporated into the
derivation of the accumulation surfaces (termed “gravity” modeling).
Accumulation surface analysis provides valuable information for a wide array of
applications. Natural resource managers
use the technique to identify “home ranges” and “corridors of movement” based
on the arrangement of landscape features.
Instead assuming a simple distance of “within a two mile radius” of an
animal’s burrow, an effective distance home range based on absolute (e.g.,
river) and relative (e.g., cover type preferences) barriers can modeled.
Similarly, a retail market analyst can model the “home range” of a particular
breed of shopper by characterizing the road network (e.g., speed limit) and
ancillary attractions (e.g., areas of interest). Or in-store shopper habitat can be modeled
using the aisles like roads and department fixtures as attractions; even
“blue-light specials” could be modeled as dynamic features in a real time
system. Traffic flows, whether in-store,
across town or in the wild are similar beasts from a
__________________________________
Author’s
Note: for
“hands-on” experience in deriving and analyzing accumulation surfaces, see
exercises TMAP2, TUTOR5, TUTOR6 and TU-
Determining Optimal Path Corridors
(GeoWorld, December 1997, pg. 28)
The first article in
this series described the construction and fundamental nature of accumulation surfaces.
The second article discussed an analysis procedure for mapping relative
geographic advantage that involved subtracting two surfaces. This time we will
investigate the interpretation of slope and aspect of an accumulation surface
and what information is derived if we add the surfaces.
Figure 25.3. The sum of two proximity surfaces identifies the optimal path between two locations as the lowest values, while increasing values identify the “opportunity cost” of forcing a path through any location.
Recall that as
distance increases from a location(s) the values can be plotted as a
3-dimensional surface, like those shown in the left portion of the accompanying
figure. The lowest point on the surface
identifies the starting location(s) as zero units away from itself. All other locations contain increasing
distance values forming the characteristic “bowl-shape” of an accumulation
surface.
Effective distance (as opposed to “simple,” straight-line distance) can be
derived by introducing absolute and relative barriers to movement. The “hill” in the Starter1 and Starter2
proximity surfaces reflect the increased impedance of
a horseshoe-shaped barrier in the center of the map area. Each grid space on a friction map is coded
with the “relative cost” of traversing that location. Note that the increased impedance is
translated into the steeper slopes for the barrier area. Therefore a slope map of an accumulation
surface unmasks the relative ease of optimal travel through each grid space.
The notion of “optimal movement” embedded in an accumulation surface is
important. The “splash” algorithm used to build the surface considers movement
from the eight surrounding cells to each location. The accumulated distance and the relative
impedance for each of the eight potential “steps” is
evaluated. The least costly step, in
terms of total movement, is assigned. Therefore an aspect map of an
accumulation surface unmasks the direction of optimal movement through each
grid space.
That’s a lot of spatially-specific information—the rate and direction of
optimal movement throughout a map area.
It allows us to relax the assumption that “everything moves in a
straight line and with equal impedance.”
In fact, things rarely move as simply as they respond to the complex
patterns of absolute and relative barriers existing in the real world. Slope and aspect maps of an accumulation
surface allow us to track the conditions of that complex movement at each map
location.
As described in the first article, the optimal path from any location to the
origin is identified as the steepest down hill route over the surface. In the second article, we found that
subtracting two accumulation surfaces located the bisecting line between the
origins as 0 (equidistant). The sign of
the distance value on the difference map indicated which origin was closer, and
its magnitude indicated how much closer.
For example, a wildfire response model might generate a proximity map
for two fire stations considering both on and off-road movement. Subtracting the maps locates the effective
dividing line between the two stations.
In retail marketing, the halfway line is extended into a broad band
indicating a “combat zone” for customers.
Areas outside the band have distinct proximity advantages, while the
real battles are waged in the combat zone where there the differences are
marginal.
If subtracting accumulation surfaces creates useful information, what do you
think happens when you add them? The
surface in the center of the figure is a summation surface for the example
data. The highlighted location is 63
from Start1 and 5 from Start2, therefore it is a total
of 68 units away from both. In other
words, the best path connecting the two origins which passes through that
location has a total length of 68. In
fact, the values on the summation surface identify the length of the “best”
path forced through any given map location.
The optimal path between the two locations (identified by the line in both the
2-D and 3-D views) contains the set of locations having the lowest values (a
valley connecting the origins). The saw-toothed appearance of the optimal path
is an artifact of arithmetic rounding, the nature of the splash algorithm and
minimal friction outside the barrier in the center. Values above the valley
floor indicate the length of the best, but sub-optimal paths forced through any
location.
The difference between the lowest value on the summation surface and the value
at any other location identifies the “opportunity cost” of forcing a route
through that location. The 2-D display
shows fixed intervals of increasing opportunity cost—you would be crazy to
force a route through the darker tones (a mountain of opportunity cost). Next time we will look at constructing a
“stepped accumulation surface” which enables you to determine the optimal path
connecting a series of predetermined stops along the way. As a sneak preview, it involves minimizing
successive accumulation surfaces… whew!
Analyzing Stepped Accumulation Surfaces
(GeoWorld, January 1998, pg. 30)
Hopefully you have
survived the last three columns on accumulation surfaces. The discussion has covered the fundamental
nature of accumulation surfaces (increasing distance waves), procedures for
determining relative geographic advantage (subtract), ways to uncover direction
and speed of optimal movement (slope and aspect), and a technique for
determining the corridor of optimal movement (add). If that wasn’t enough, now we get to extend
the discussion to a “stepped accumulation surface” and “optimal path zones.”
Suppose you know several places you would like to visit, but don’t have a
particular route in mind. If you know
the order you would like to visit them, then a directed stepped accumulation
surface is for you. Simply generate an
effective proximity surface from the first location like those discussed in the
previous articles—splash, one ripple, two ripple, three ripple and more radiate
out from your starting point. The
familiar bowl of proximity identifies the effective distance to all other
locations. All you have to do is
“stream” down the bowl from your second point of interest to identify the
optimal path.
Now, construct a proximity surface from the second point to everywhere, and
stream your third stop down it for the second leg of your journey. The left side of Figure 25.4 shows a stepped
accumulation surface for the first two segments of a “directed hike” through
the demonstration area. The shaded area
shows the portion of the proximity surface from the start until the concentric
ripples encountered the second point.
The non-shaded area picks up the count by adding the proximity from
there to all other locations. The result
is a two-tiered surface similar to a spiral staircase. If you stream down the stepped accumulation
surface from the third stop, it first flows down the top tier to the second
stop, then continues down to the first point (right side of Figure 25.4).
Figure 25.4. Stepped Accumulation Surface. Proximity from the first point is calculated (shaded) until the second point is reached, then proximity from that point is calculated (non-shaded) forming the next tier; the individual optimal paths along each of the stepped proximity surfaces forms the overall optimal route.
Additional stops are
considered by repeating the successive construction of proximity bowls and
streaming down them for sequential optimal path segments. An undirected procedure allows the computer
to determine a spatially efficient ordering of the points. You simply identify a starting location, the
points you need to visit and the computer calculates the optimal route
connecting them. The solution spreads
out from the first point until it encounters the closest visitation point, then
streams down the truncated proximity surface for the first leg. The next tier spreads out until it encounters
its closest point and streams down for the next leg. The process continues until all of the
visitation points have been evaluated.
If you intend to return to the starting point, the home leg considers
the starting point and is evaluated last.
The undirected, stepped accumulation surface technique (whew …quite a mouthful)
is similar to the classic “traveling salesman” problem in network
analysis. However, it provides a
solution in continuous space, respecting the complex reality of absolute and
relative barriers. This is important if
the traveling salesman doesn’t have a car, or if the mover isn’t constrained to
a bunch of lines, like a herd of elk, or shoppers in a store.
In a recent project1, we encoded the floor plan for a retail
superstore (98,000 1-foot grids), translating the fixtures into absolute
barriers and congested areas into relative barriers. Shelving locations were identified on each
fixture and linked to product codes. The
checkout records for each market basket were used to “place” each item
purchased on the appropriate shelf.
These visitation points were evaluated for the “plausible” path used to
collect the items between the door to the cash register.
Granted, a shopper could do “a random walk” to collect the items, but a shopper
with a mission who knows the store, would be foolish to veer off the calculated
route. Also, the consideration of
several thousands of paths over a period of time converges on a map of relative
in-store shopper activity. The analysis
was summarized in hourly time-steps, displayed as normalized thematic maps, and
animated to show the ebb and flow of shopper activity throughout the day.
Figure 25.5. Route Proximity Surface. Proximity from the optimal route identifies the distance to the closest segment of the route for every location in a project area; the influence zone of each segment along the route identifies which segment is the closest.
Figure 25.5 shows a
follow-on analysis to the continuous-space routing problem. Directed, stepped accumulation surface
analysis was used to locate the optimal route from
The right side of Figure 25.5 shows the zones of influence for each leg of the
optimal route. The locations within each
zone are optimally connected to a particular segment. So, how might one use such information. In the shopper example, the distance from a
shopper’s path can be interpreted as a geographic
impedance that must be overcome to veer off stride. Influence zones locate areas along a common
portion of a shopper’s route. Overlaying
these data with in-store departments, sales density surfaces and item
categories produces a lot of information about shelving for retail marketing
types. How might you use accumulation
surfaces?
_________________________
1 see www.innovative.gis/basis
for a PowerPoint slide show on In-Store Shopper Movement.
(Back to the Table of Contents)