Quantitative Methods and Applications in GIS - Chapter 2

2 Measuring Distances and Time This chapter discusses one of basic tasks encountered most often in spatial analysis: measuring distances and time. After all, spatial analysis is about how physical and human activities vary across space — in other words, how these activities change with distances from reference locations or objects of interest. In many applications, once the distance or time measure is obtained, studies may be completed outside a GIS environment. The advancement and wide availability of GIS have made the task much easier than it used to be. The task of distance or time estimation can be found throughout this book. For example, spatial smoothing and spatial interpolation in Chapter 3 utilize distance measures to determine which objects enter the computation and how much the objects influence the computation. In trade area analysis in Chapter 4, distances (or time) between stores and consumers dictate which stores are the closest and how often residents visit a store. In Chapter 5 on accessibility measures, distance or time measures are the building block of either the floating catchment area method or the gravity-based method. Chapter 6 examines how population density or land use intensity declines with distance from a city or regional center. The task can also be found in other chapters. This chapter is structured as follows. Section 2.1 provides an overview of various distance measures. Section 2.2 discusses how to compute the shortest-route distance (time) through a network and how to implement it in ArcGIS. A case study of measuring the Euclidean and network distances in northeast China is presented in Section 2.3. Results from this case study will be used in case study 4B (Section 4.4). The chapter is concluded with a brief summary in Section 2.4. 2.1 MEASURES OF DISTANCE Distance measures include Euclidean (straight-line, or air) distance, Manhattan dis-tance, or network distance. Euclidean distance is simply the distance between two points through a straight line. Unless otherwise specified, distance is measured in Euclidean distance. Prior to the wide usage of GIS, researchers needed to use mathematical formulas to compute the distance, and the accuracy is limited depending on the information available and tolerance of computational complexity. If a study area is small in terms of its geographic territory (e.g., a city or a county), Euclidean distance between two nodes (x1, y1) and (x2, y2) in Cartesian coordinates is approximated as d12 = [(x1 − x2 )2 + (y1 − y2 )2 ]1/2 (2.1) 19 © 2006 by Taylor & Francis Group, LLC 20 Quantitative Methods and Applications in GIS If the study area covers a large territory (e.g., a state or a nation), one needs to compute the geodetic distance. The geodetic distance between two points is the distance through a great circle assuming the Earth as a globe. Given the geographic coordinates of two points as (a, b) and (c, d) in decimal degrees, the geodetic distance between them is d12 = r* acos[sinb*sind + cosb*cosd *cos(c − a)] (2.2) where r is the radius of the earth (approximately 6367.4 km). As the name suggests, Manhattan distance describes a rather restrictive move-ment in rectangular blocks, like in the borough of Manhattan. Manhattan distance is the length of the change in the x direction plus the change in the y direction. For instance, the Manhattan distance between two nodes (x1, y1) and (x2, y2) in Cartesian coordinates is simply computed as d12 =| x1 − x2 | + | y1 − y2 | (2.3) Like Equation 2.1, Manhattan distance, defined by Equation 2.3, is only meaningful within a small study area (e.g., a city). Network distance is the shortest-path (or least-cost) distance through a road network and will be discussed in detail in Section 2.2. Manhattan distance can be used as an approximation for network distance if the street network is in a grid pattern. In ArcGIS, simply click on the graphic tool (measure) in ArcMap to obtain the Euclidean distance between two points (or a cumulative distance along several points). Distance is created as a by-product in many spatial analysis operations in ArcGIS. For example, a distance join (a spatial join method) in ArcGIS, as explained in Section 1.3, records the nearest distances between objects of two spatial datasets. In a distance join, distance between lines or polygons is between their closest points. Under ArcToolbox > Analysis Tools > Proximity, the Near tool computes the distance from each point in one layer to its closest polyline or point in another layer. Some applications need to use distances between any two points either within one layer or between different layers, and thus a distance matrix. The Point Distance tool in ArcToolbox is designed for this purpose and is accessed in ArcToolbox > Analysis Tools > Proximity > Point Distance. In the output file, if the value for DISTANCE is 0, it could be that the actual distance is either indeed 0 (e.g., from a point to itself) or beyond the Search radius. The current ArcGIS version does not have a built-in tool for computing the less commonly used Manhattan distance. Computing Manhattan distances requires the Cartesian coordinates of points that can be generated in ArcToolbox. For a shapefile, use Data Management Tools > Features > Add XY Coordinates. For a coverage, use Coverage Tools > Data Management > Tables > Add XY Coordinates. Com-puting network distance in ArcGIS is more complex and will be discussed in the next two sections. © 2006 by Taylor & Francis Group, LLC Measuring Distances and Time 21 2.2 COMPUTING NETWORK DISTANCE AND TIME A network consists of a set of nodes (or vertices) and a set of arcs (or edges or links) that connect the nodes. If the arcs are directed (e.g., one-way streets), the network is a directed network. A network without regard to direction may be considered a special case of directed network with each arc having two permissible directions. Finding the shortest chains from a specified origin to a specified desti-nation is the shortest-route problem, which records the shortest distance or the least time (cost) if the impedance value (e.g., travel speed) is provided on each arc. Different methods for solving the problem have been proposed in the literature, including the label-setting algorithm discussed in this section and the valued-graph (or L matrix) method in Appendix 2. 2.2.1 LABEL-SETTING ALGORITHM FOR THE SHORTEST-ROUTE PROBLEM The popular label-setting algorithm was first described by Dijkstra (1959). The method assigns labels to nodes, and each label is actually the shortest distance from a specified origin. To simplify the notation, the origin is assumed to be node 1. The method takes four steps: 1. Assign the permanent label y1 = 0 to the origin (node 1) and a temporary label yj = M (a very large number) to every other node. Set i = 1. 2. From node i, recompute the temporary labels yj = min (yj, yi + dij), where node j is temporarily labeled and dij < M (dij is the distance from i to j). 3. Find the minimum of the temporary labels, say, yi. Node i is now perma-nently labeled with value yi. 4. Stop if all nodes are permanently labeled; go to step 2 otherwise. The following example is used to illustrate the method. Figure 2.1a shows the network layout with nodes and links. The number next to a link is the impedance value for the link. Following step 1, permanently label node 1 and set y1 = 0; temporarily label y2 = y3 = y4 = y5 = M. Set i = 1. A permanent label is marked with an asterisk (*). See Figure 2.1b. In step 2, from node 1 we can reach nodes 2 and 3, which are temporarily labeled. y2 = min (y2, y1 + d12) = min (M, 0 + 25) = 25, and similarly, y3 = min (y3, y1 + d13) = min (M, 0 + 55) = 55. In step 3, the smallest temporary label is min (25, 55, M, M) = 25 = y2. Permanently label node 2 and set i = 2. See Figure 2.1c. Back to step 2, as nodes 3, 4, and 5 are still temporarily labeled. From node 2, we can reach temporarily labeled nodes 3, 4, and 5. y3 = min (y3, y2 + d23) = min (55, 25 + 40) = 55, y4 = min (y4, y2 + d24) = min (M, 25 + 45) = 70, y5 = min (y5, y2 + d25) = min (M, 25 + 50) = 75. Following step 3 again, the smallest temporary label is min (55, 70, 75) = 55 = y3. Permanently label node 3 and set i = 3. See Figure 2.1d. © 2006 by Taylor & Francis Group, LLC 22 Quantitative Methods and Applications in GIS 2 45 4 y2 = M 2 45 y4 = M 4 25 50 1 40 25 35 y∗ = 0 1 40 50 35 55 3 30 5 55 (a) 3 30 5 y3 = M y5 = M (b) y∗ = 25 2 45 y4 = M y∗ = 25 4 2 45 y4 = 70 4 25 25 y∗ = 0 1 40 50 35 y∗ = 0 1 40 50 35 55 y3 = 55 30 y5 = M (c) 55 y∗ = 55 30 (d) 5 y5 = 75 y∗ = 25 2 y∗ = 70 y∗ = 25 y∗ = 70 45 4 2 45 4 25 25 y∗ = 0 1 40 50 35 y∗ = 0 1 40 50 35 55 y3 = 55 30 y5 = 75 (e) 55 y∗ = 55 30 (f) 5 y∗ = 75 FIGURE 2.1 An example for the label-setting algorithm. Back to step 2, as nodes 4 and 5 are still temporarily labeled. From node 3 we can reach only node 5 (still temporarily labeled). y5 = min (y5, y3 + d35) = min (75, 55 + 30) = 75. Following step 3, the smallest temporary label is min (70, 75) = 70 = y4. Permanently label node 4 and set i = 4. See Figure 2.1e. Back to step 2, as node 5 is still temporarily labeled. From node 4 we can reach node 5. y5 = min (y5, y4 + d45) = min (75, 70 + 35) = 75. Node 5 is the only temporarily labeled node, so we permanently label node 5. By now all nodes are permanently labeled, and the problem is solved. See Figure 2.1f. The permanent labels yi give the shortest distance from node 1 to node i. Once a node is permanently labeled, we examine arcs “scanning” from it only once. The shortest paths are stored by noting the scanning node each time a label is changed (Wu and Coppins, 1981, p. 319). The solution to the above example can be sum-marized in Table 2.1. © 2006 by Taylor & Francis Group, LLC Measuring Distances and Time 23 TABLE 2.1 Solution to the Shortest-Route Problem Origin–destination nodes 1, 2 1, 3 1, 4 1, 5 Arcs on the Route (1, 2) (1, 3) (1, 2), (2, 4) (1, 2), (2, 5) Shortest distance 25 55 70 75 2.2.2 MEASURING NETWORK DISTANCE OR TIME IN ARCGIS Networks handled in ArcGIS include transportation networks and utility networks. For our purpose, the discussion is limited to transportation networks. Most GIS textbooks (e.g., Chang, 2004, chap. 16; Price, 2004, chap. 14) discuss how the distance between two points (or distances between a location and many others) is obtained in ArcGIS. In many spatial analysis applications, a distance matrix between a set of origins and a set of destinations is needed. For this task, one needs to use the ArcInfo Workstation, in particular, the NODEDISTANCE command in the ArcPlot module. The NODEDISTANCE command computes the shortest distances through a road network by default and also outputs the Euclidean or Manhattan distances as options. By properly defining the item IMPEDANCE as time or cost, it also computes the shortest travel time or the least cost, respectively. The following explains how a matrix of network distances is computed in ArcGIS. The first step is to set up the network. A transportation network has many network elements, such as link impedances, turn impedances, one-way streets, and overpasses and underpasses, that need to be defined (Chang, 2004, p. 351). Putting together a road network requires extensive data collection and processing, which can be very expensive or infeasible for many applications. For example, a road layer extracted from the TIGER/Line files does not contain nodes on the roads, turning parameters, or speed information. When such information is not available, one may assume that nodes built from a road layer by some automation tools (e.g., topology builders in ArcGIS) are acceptable and closely resemble the real-world network. For link impedances, one may assign speed limits based on road levels and account for congestion effects if possible. In Luo and Wang (2003), speeds are assigned to different roads according to the census feature class codes (CFCCs) used by the U.S. Census Bureau in its TIGER/Line files and whether in urban, suburban, or rural areas. Wang (2003) uses regression models to predict travel speeds by land use intensity (business and residential densities) and other factors. In the second step, the NETCOVER command is used to set up the route system for network computation. The third step is to define the origin nodes, destination nodes, and impedance item. Commands such as CENTERS, STOPS, and NODES are used to define origin and destination points; IMPEDANCE specifies which item in the network attribute table defines the impedance. © 2006 by Taylor & Francis Group, LLC ... - tailieumienphi.vn