Beyond Mapping
III
|
Map
Analysis book with companion CD-ROM for hands-on exercises and further reading |
Measuring Distance Is Neither Here nor There — discusses
the basic concepts of distance and proximity
Use Cells and Rings to Calculate Simple
Proximity — describes
how simple proximity is calculated
Extend Simple Proximity to Effective Movement — discusses
the concept of effective distance responding to relative and absolute barriers
Calculate and Compare to Find Effective
Proximity — describes
how effective proximity is calculated
Taking
Distance to the Edge — discusses
advance distance operations
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)
______________________________
Measuring Distance Is
Neither Here nor There
(GeoWorld, April 2005, pg. 18-19)
Measuring
distance is one of the most basic map analysis techniques. Historically, distance is defined as the shortest straight-line
between two points. While
this three-part definition is both easily conceptualized and implemented with a
ruler, it is frequently insufficient for decision-making. A straight-line route might indicate the
distance “as the crow flies,” but offer little information for the walking crow
or other flightless creature. It is
equally important to most travelers to have the measurement of distance
expressed in more relevant terms, such as time or cost.
The limitation of
a map analysis approach is not so much in the concept of distance measurement,
but in its implementation. Any
measurement system requires two components— a standard unit and a procedure
for measurement. Using a ruler, the
“unit” is the smallest hatching along its edge and the “procedure” is the line
implied by aligning the straightedge. In
effect, the ruler represents just one row of a grid implied to cover the entire
map. You just position the grid such
that it aligns with the two points you want measured and count the squares (top
portion of figure 1). To measure another
distance you merely realign the implied grid and count again.
Figure 1.
Both Manual Measurement and the Pythagorean Theorem use grid spaces as
the fundamental units for determining the distance between two points.
In a
Proximity establishes
the distance to all locations surrounding a point— the set of shortest straight-lines among groups of
points. Rather than sequentially
computing the distance between pairs of locations, concentric equidistance
zones are established around a location or set of locations (figure 2). This procedure is similar to the wave pattern
generated when a rock is thrown into a still pond. Each ring indicates one “unit farther away”—
increasing distance as the wave moves away.
Another way to conceptualize the process is nailing one end of a ruler
at a point and spinning it around. The
result is a series of “data zones” emanating from a location and aligning with
the ruler’s tic marks.
Figure 2.
Proximity identifies the set of shortest straight-lines among groups
of points (distance zones).
However,
nothing says proximity must be measured from a single point. A more complex proximity map would be
generated if, for example, all locations with houses (set of points) are
simultaneously considered target locations (right side of figure 3).
Figure 3.
Proximity surfaces can be generated for groups of points, lines or
polygons identifying the shortest distance from all location to the closest
occurrence.
In effect, the
procedure is like throwing a handful of rocks into pond. Each set of concentric rings grows until the
wave fronts meet; then they stop. The
result is a map indicating the shortest straight-line distance to the nearest
target location (house) for each non-target location. In the figure, the red tones indicate
locations that are close to a house, while the green tones identify areas that
are far from a house.
In a similar
fashion, a proximity map to roads is generated by establishing data zones
emanating from the road network—sort of like tossing a wire frame into a pond
to generate a concentric pattern of ripples (middle portion of figure 3). The same result is generated for a set of
areal features, such as sensitive habitat parcels (right side of figure 3).
It is important
to note that proximity is not the same as a buffer. A buffer is a discrete spatial object that
identifies areas that are within a specified distance of map feature; all
locations within a buffer are considered the same. Proximity is a continuous surface that
identifies the distance to a map feature(s) for every location in a project
area. It forms a gradient of distances
away composed of many map values; not a single spatial object with one
characteristic distance away.
The 3D plots of
the proximity surfaces in figure 3 show detailed gradient data and are termed accumulated surfaces. They contain increasing distance values from
the target point, line or area locations displayed as colors from red (close)
to green (far). The starting features
are the lowest locations (black= 0) with hillsides of increasing distance and
forming ridges that are equidistant from starting locations. Next month will focus on how proximity is
calculated—conceptually easy but way too much bookkeeping for even the most
ardent accountant.
Use Cells and Rings to
Calculate Simple Proximity
(GeoWorld, May 2005, pg. 18-19)
The last section
established that proximity is measured by a series of propagating rings
emanating from a starting location—splash algorithm. Since the reference grid is a set of square
grid cells, the rings are formed by concentric sets of cells. In figure 1, the first “ring” is formed by
the three cells adjoining the starting cell in the lower-right corner. The top and side cells represent orthogonal
movement while upper-left one is diagonal.
The assigned distance of the steps reflect the type of movement—orthogonal
equals 1.000 and diagonal equals 1.414.
As the rings
progress, 1.000 and 1.414 are added to the previous accumulated distances
resulting in a matrix of proximity values.
The value 7.01 in the extreme upper-left corner is derived by adding
1.414 for five successive rings (all diagonal steps). The other two corners are derived by adding
1.000 five times (all orthogonal steps).
In these cases, the effective proximity procedure results in the same
distance as calculated by the Pythagorean Theorem.
Figure 1.
Simple proximity is generated by summing a series of orthogonal and
diagonal steps emanating from a starting location.
Reaching other
locations involve combinations of orthogonal and diagonal steps. For example, the other location in the figure
uses three orthogonal and then two diagonal steps to establish an accumulated
distance value of 5.828. The Pythagorean
calculation for same location is 5.385.
The difference (5.828 – 5.385= .443/5.385= 8%) is due to the relatively
chunky reference grid and the restriction to grid cell movements.
Grid-based
proximity measurements tend to overstate true distances for
off-orthogonal/diagonal locations.
However, the error becomes minimal with distance and use of smaller
grids. And the utility of the added
information in a proximity surface often outweighs the lack of absolute
precision of simple distance measurement.
Figure 2 shows
the calculation details for the remaining rings. For example, the larger inset on the left
side of the figure shows ring 1 advancing into the second ring. All forward movements from the cells forming
the ring into their adjacent cells are considered. Note the multiple paths that can reach
individual cells. For example, movement
into the top-right corner cell can be an orthogonal step from the 1.000 cell
for an accumulated distance of 2.000. Or
it can be reached by a diagonal step from the 1.414 cell for an accumulated
distance of 2.828. The smaller value is
stored in compliance with the idea that distance implies “shortest.” If the spatial resolution of the analysis
grid is 300m then the ground distance is 2.000 * 300m/gridCell= 600m.
Figure 2.
Simple distance rings advance by summing 1.000 or 1.414 grid space
movements and retaining the minimal accumulated distance of the possible paths.
In a similar
fashion, successive ring movements are calculated, added to the previous ring’s
stored values and the smallest of the potential distance values being
stored. The distance waves rapidly
propagate throughout the project area with the shortest distance to the
starting location being assigned at every location.
Figure 3.
Proximity surfaces are compared and the smallest value is retained to
identify the distance to the closest starter location.
If more than
one starting location is identified, the proximity surface for the next starter
is calculated in a similar fashion. At
this stage every location in the project area has two proximity values—the
current proximity value and the most recent one (figure 3). The two surfaces are compared and the
smallest value is retained for each location—distance to closest starter location. The process is repeated until all of the
starter locations representing sets of points, lines or areas have been
evaluated.
While the
computation is overwhelming for humans, the repetitive nature of adding
constants and testing for smallest values is a piece of cake for computers
(millions of iterations in a few seconds).
More importantly, the procedure enables a whole new way of representing
relationships in spatial context involving “effective distance” that responds
to realistic differences in the characteristics and conditions of movement
throughout geographic space.
Extend Simple Proximity
to Effective Movement
(GeoWorld, June 2005, pg. 18-19)
Last section’s
discussion suggested that in many applications, the shortest route between two
locations might not always be a straight-line.
And even if it is straight, its geographic length may not always reflect
a traditional measure of distance.
Rather, distance in these applications is best defined in terms of
“movement” expressed as travel-time, cost or energy that is consumed at rates
that vary over time and space. Distance
modifying effects involve weights and/or barriers— concepts that imply the
relative ease of movement through geographic space might not always
constant.
Figure 1
illustrates one of the effects of distance being affected by a movement characteristic. The left-side of the figure shows the simple
proximity map generated when both starting locations are considered to have the
same characteristics or influence. Note
that the midpoint (dark green) aligns with the perpendicular bisector of the
line connecting the two points and confirms a plane geometry principle you learned
in junior high school.
The right-side
of the figure, on the other hand, depicts effective proximity where the two
starting locations have different characteristics. For example, one store might be considered
more popular and a “bigger draw” than another (Gravity Modeling). Or in old geometry terms, the person starting
at S1 hikes twice as fast as the individual starting at S2— the weighted
bisector identifies where they would meet.
Other examples of weights include attrition where movement changes with
time (e.g., hiker fatigue) and change in mode (drive a vehicle as far as
possible then hike into the off-road areas).
Figure 1.
Weighting factors based on the characteristics of movement can affect
relative distance, such as in Gravity Modeling where some starting locations
exert more influence.
In addition to
weights that reflect movement characteristics, effective proximity responds to
intervening conditions or barriers. There are two types of barriers that are
identified by their effects— absolute and relative. Absolute
barriers are those completely restricting movement and therefore imply an
infinite distance between the points they separate. A river might be regarded as an absolute
barrier to a non-swimmer. To a swimmer
or a boater, however, the same river might be regarded as a relative barrier identifying areas that
are passable, but only at a cost which can be equated to an increase in
geographical distance. For example, it
might take five times longer to row a hundred meters than to walk that same
distance.
In the
conceptual framework of tossing a rock into a pond, the waves can crash and
dissipate against a jetty extending into the pond (absolute barrier; no
movement through the grid spaces). Or
they can proceed, but at a reduced wavelength through an oil slick (relative
barrier; higher cost of movement through the grid spaces). The waves move both around the jetty and
through the oil slick with the ones reaching each location first identifying the set of shortest, but not necessarily
straight-lines among groups of points.
The shortest
routes respecting these barriers are often twisted paths around and through the
barriers. The
Figure 2.
Effective Proximity surfaces consider the characteristics and conditions
of movement throughout a project area.
The point features
in the left inset respond to treating flowing water as an absolute barrier to
movement. Note that the distance to the
nearest house is very large in the center-right portion of the project area
(green) although there is a large cluster of houses just to the north. Since the water feature can’t be crossed, the
closest houses are a long distance to the south.
Terrain
steepness is used in the middle inset to illustrate the effects of a relative
barrier. Increasing slope is coded into
a friction map of increasing impedance values that make movement through steep
grid cells effectively farther away than movement through gently sloped
locations. Both absolute and relative
barriers are applied in determining effective proximity sensitive areas in the right
inset.
The dramatic
differences between the concept of distance “as the crow flies” (simple
proximity) and “as the crow walks” (effective proximity) is a bit unfamiliar
and counter-intuitive. However, in most
practical applications, the comfortable assumption that all movement occurs in
straight lines totally disregards reality.
When traveling by trains, planes, automobiles, and feet there are plenty
of bends, twists, accelerations and decelerations due to characteristics
(weights) and conditions (barriers) of the movement.
Figure 3. Effective Distance waves are
distorted as they encounter absolute and relative barriers, advancing faster
under easy conditions and slower in difficult areas.
Figure 3 illustrates
how the splash algorithm propagates distance waves to generate an effective
proximity surface. The Friction Map
locates the absolute (blue/water) and relative (light blue= gentle/easy through
red= steep/hard) barriers. As the
distance wave encounters the barriers their effects on movement are
incorporated and distort the symmetric pattern of simple proximity waves. The result identifies the “shortest, but not
necessarily straight” distance connecting the starting location with all other
locations in a project area.
Note that the
absolute barrier locations (blue) are set to infinitely far away and appear as
pillars in the 3-D display of the final proximity surface. As with simple proximity, the effective
distance values form a bowl-like surface with the starting location at the
lowest point (zero away from itself) and then ever-increasing distances away
(upward slope). With effective
proximity, however, the bowl is not symmetrical and is warped with bumps and
ridges that reflect intervening conditions— the greater the impedance the
greater the upward slope of the bowl. In
addition, there can never be a depression as that would indicate a location
that is closer to the starting location than everywhere around it. Such a situation would violate the
ever-increasing concentric rings theory and is impossible except on Star Trek
where Spock and the Captain de-materialize then reappear somewhere else without
physically passing through the intervening locations.
Calculate and Compare to
Find Effective Proximity
(GeoWorld, July 2005, pg. 18-19)
The last couple
of sections have focused on how effective distance is measured in a grid-based
Figure 1.
Effective proximity is generated by summing a series of steps that
reflect the characteristics and conditions of moving through geographic space.
Figure 1 shows
the effective proximity values for a small portion of the results forming the
proximity surface discussed last month. Manual
Measurement, Pythagorean Theorem and Simple Proximity all report that the
geographic distance to the location in the upper-right corner is 5.071 *
300meters/gridCell= 1521 meters. But
this simple geometric measure assumes a straight-line connection that crosses
extremely high impedance values, as well as absolute barrier locations—an
infeasible route that results in exhaustion and possibly death for a walking
crow.
The shortest
path respecting absolute and relative barriers is shown as first sweeping to
the left and then passing around the absolute barrier on the right side. This counter-intuitive route is formed by
summing the series of shortest steps at each juncture. The first step away from the starting
location is toward the lowest friction and is computed as the impedance value
times the type of step for 3.00 *1.000= 3.00.
The next step is considerably more difficult at 5.00 * 1.414= 7.07 and
when added to the previous step’s value yields a total effective distance of
10.07. The process of determining the
shortest step distance and adding it to the previous distance is repeated over
and over to generate the final accumulated distance of the route.
It is important
to note that the resulting value of 49.70 can’t be directly compared to the 507.1
meters geometric value. Effective
proximity is like applying a rubber ruler that expands and contracts as
different movement conditions reflected in the Friction Map are encountered. However, the proximity values do establish a
relative scale of distance and it is valid to interpret that the 49.7 location
is nearly five times farther away than the location containing the 10.07
value.
If the Friction
Map is calibrated in terms of a standard measure of movement, such as time, the
results reflect that measure. For
example, if the base friction unit was 1-minute to cross a grid cell the
location would be 49.71 minutes away from the starting location. What has changed isn’t the fundamental
concept of distance but it has been extended to consider real-world
characteristics and conditions of movement that can be translated directly into
decision contexts, such as how long will it take to hike from “my cabin to any
location” in a project area. In
addition, the effective proximity surface contains the information for
delineating the shortest route to anywhere—simply retrace to wave front
movement that got there first by taking the steepest downhill path over the
accumulation surface.
Figure 2.
Effective distance rings advance by summing the friction factors times
the type of grid space movements and retaining the minimal accumulated distance
of the possible paths.
The calculation
of effective distance is similar to that of simple proximity, just a whole lot
more complicated. Figure 2 shows the set
of movement possibilities for advancing from the first ring to the second
ring. Simple proximity only considers
forward movement whereas effective proximity considers all possible steps (both
forward and backward) and the impedance associated with each potential
move.
For example,
movement into the top-right corner cell can be an orthogonal step times the
friction value (1.000 * 6.00) from the 18.00 cell for an accumulated distance
of 24.00. Or it can be reached by a
diagonal step times the friction value (1.414 * 6.00) from the 19.00 cell for
an accumulated distance of 30.48. The
smaller value is stored in compliance with the idea that distance implies
“shortest.” The calculations in the blue
panels show locations where a forward step from ring 1 is the shortest, whereas
the yellow panels show locations where backward steps from ring 2 are
shorter.
The explicit
procedure for calculating effective distance in the example involves:
Step 1)
multiplying the friction value for a step
Step 2) times
the type of step (1.000 or 1.414)
Step 3) plus
the current accumulated distance
Step 4)
testing for the smallest value, and
Step 5)
storing the minimum solution if less than any previously stored value.
Extending the
procedure to consider movement characteristics merely introduces an additional
step at the beginning—multiplying the relative weight of the starter.
The complete
procedure for determining effective proximity from two or more starting
locations is graphically portrayed in figure 3.
Proximity values are calculated from one location then another and
stored in two matrices. The values are
compared on a cell-by-cell basis and the shortest value is retained for each
instance. The “calculate then compare”
process is repeated for other starting locations with the working matrix
ultimately containing the shortest distance values, regardless which starter
location is closest. Piece-of-cake for a
computer.
Figure 3. Effective proximity surfaces
are computed respecting movement weights and impedances then compared and the
smallest value is retained to identify the distance to the closest starter
location.
Taking Distance to the
Edge
(GeoWorld, August 2005, pg. 18-19)
The past series
of four sections have focused on how simple distance is extended to effective
proximity and movement in a modern
While the
computations of simple and effective proximity might be unfamiliar and appear
complex, once programmed they are easily and quickly performed by modern
computers. In addition, there is a
rapidly growing wealth of digital data describing conditions that impact
movement in the real world. It seems
that all is in place for a radical rethinking and expression of
distance—computers, programs and data are poised.
However, what
seems to be the major hurdle for adoption of this new way of spatial thinking
lies in the experience base of potential users.
Our paper map legacy suggests that the “shortest straight line between
two points” is the only way to investigate spatial context relationships and
anything else is disgusting (or at least uncomfortable).
This restricted
perspective has lead most contemporary
Figure 1.
Extended list of advance distance operations.
The first
portion of figure 1 identifies the basic operations described in the previous
sections. Our traditional thinking of
distance as the “shortest, straight line between two points” is extended to Simple
Proximity by relaxing the assumption that all movement is just between
two points. Effective Proximity
relaxes the requirement that all movement occurs in straight lines. Weighted Proximity extends the
concept of static geographic distance by accounting for different movement
characteristics, such as speed.
The result is a
new definition of distance as the “shortest, not necessarily straight set of
connections among all points.” While
this new definition may seem awkward it is more realistic as very few things
move in a straight line. For example, it
has paved the way for online driving directions from your place to anywhere …an
impossible task for a ruler or Pythagoras.
In addition, the
new procedures have set the stage for even more advanced distance operations
(lower portion of figure 1). A Guiding
Surface can be used to constrain movement up, down or across a
surface. For example, the algorithm can
check an elevation surface and only proceed to downhill locations from a
feature such as roads to identify areas potentially affected by the wash of
surface chemicals applied.
The simplest Directional
Effect involves compass directions, such as only establishing proximity
in the direction of a prevailing wind. A
more complex directional effect is consideration of the movement with respect
to an elevation surface—a steep uphill movement might be considered a higher
friction value than movement across a slope or downhill. This consideration involves a dynamic barrier
that the algorithm must evaluate for each point along the wave front as it
propagates.
Accumulation
Effects
account for wear and tear as movement continues. For example, a hiker might easily proceed
through a fairly steep uphill slope at the start of a hike but balk and pitch a
tent at the same slope encountered ten hours into a hike. In this case, the algorithm merely “carries”
an equation that increases the static/dynamic friction values as the movement
wave front progresses. A natural
application is to have a user enter their gas tank size and average mileage
into MapQuest so it would automatically suggest refilling stops along your
vacation route.
A related
consideration, Momentum Effects, tracks the total effective distance but in
this instance it calculates the net effect of up/downhill conditions that are
encountered. It is similar to a marble
rolling over an undulating surface—it picks up speed on the downhill stretches
and slows down on the uphill ones. In
fact, this was one of my first spatial exercises in computer programming in the
1970s. The class had to write a program
that determined the final distance and position of a marble given a starting
location, momentum equation based on slope and a relief matrix …all in
unstructured FORTRAN.
The remaining
three advanced operations interact with the accumulation surface derived by the
wave front’s movement. Recall that this
surface is analogous to football stadium with each tier of seats being assigned
a distance value indicating increasing distance from the field. In practice, an accumulation surface is a
twisted bowl that is always increasing but at different rates that reflect the
differences in the spatial patterns of relative and absolute barriers.
Stepped
Movement
allows the proximity wave to grow until it reaches a specified location, and
then restart at that location until another specified location and so on. This generates a series of effective
proximity facets from the closest to the farthest location. The steepest downhill path over each facet,
as you might recall, identifies the optimal path for that segment. The set of segments for all of the facets
forms the optimal path network connecting the specified points.
The direction
of optimal travel through any location in a project area can be derived by
calculating the Back Azimuth of the location on the accumulation surface. Recall that the wave front potentially can
step to any of its eight neighboring cells and keeps track of the one with the
least “friction.” The aspect of the
steepest downhill step (N, NE, E, SE, S, SW, W or NW) at any location on the
accumulation surface therefore indicates the direction of the best path through
that location. In practice there are two
directions—one in and one out for each location.
An even more
bazaar extension is the interpretation of the 1st and 2nd
Derivative of an accumulation surface.
The 1st derivative (rise over run) identifies the change in
accumulated value (friction value) per unit of geographic change (cell
size). On a travel-time surface, the
result is the speed of optimal travel across the cell. The second derivative generates values
whether the movement at each location is accelerating or decelerating.
Chances are
these extensions to distance operations seem a bit confusing, uncomfortable,
esoteric and bordering on heresy. While
the old “straight line” procedure from our paper map legacy may be straight
forward, it fails to recognize the reality that most things rarely move in
straight lines.
Effective
distance recognizes the complexity of realistic movement by utilizing a
procedure of propagating proximity waves that interact with a map indicating
relative ease of movement. Assigning
values to relative and absolute barriers to travel enable the algorithm to
consider locations to favor or avoid as movement proceeds. The basic distance operations assume static
conditions, whereas the advanced ones account for dynamic conditions that vary
with the nature of the movement.
So what’s the
take home from this series describing effective distance? Two points seem to define the bottom
line. First, that the digital map is
revolutionizing how we perceive distance, as well as how calculate it. It is the first radical change since
Pythagoras came up with his theorem about 2,500 years ago. Secondly, the ability to quantify effective
distance isn’t limited by computational power or available data; rather our
difficulties in understanding accepting the concept. Hopefully the discussions have shed some
light on this rethinking of distance measurement.
______________________________
Author’s Note: Additional
discussion of distance, proximity, movement and related measurements in
http://www.innovativegis.com/basis/
¾ Topic 25, Calculating Effective Proximity
¾ Topic 20, Surface Flow Modeling
¾ Topic 19, Routing and Optimal Paths
¾ Topic 17, Applying Surface Analysis
¾ Topic 15, Deriving and Using Visual Exposure Maps
¾ Topic 14, Deriving and Using Travel-Time Maps
¾ Topic 13, Creating Variable-Width Buffers
¾ Topic 6, Analyzing In-Store Shopping Patterns
¾ Topic 5, Analyzing Accumulation Surfaces