Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

ie. a combination of Voronoi polygons with isochrones, so that the Voronoi polygons are based on driving distance instead of Euclidean distance. Is there a name or a described method for this?

share|improve this question
I don't know any exact name for this, but an exact analogy to Euclidean distance isn't always possible for driving routes. Consider one-ways roads: they cause some street locations to be such that distances don't adhere to the triangle inequality. – Anthony -GISCOE- Feb 8 '11 at 18:38

I don't think there is a name for this exact technique, but hopefully some of what follows will provide some options:

In general, there are many interpolation techniques for moving between a point representation and a continuous surface, such the TIN interpolation method underdark has illustrated. The continuous surface could then be classified by value to produce the isochrones.

On a network such as roads, if the distances along the edges are known, you can compute the distances to any location using something like the A* algorithm -- again this data could be partitioned by distance into isochrones.

share|improve this answer
Interpolation off-road is meaningless unless you explicitly permit off-road travel. In that case, the correct answer is not an interpolation per se, but is computed with a cost-distance procedure (of which the A* algorithm is an example) for off road travel, not for travel along the road "edges." Neither IDW nor kriging are appropriate here. – whuber Feb 19 '11 at 4:07
Interpolation off-road can just be there for presentation purposes. Imagine a city map which indicates to which hospital you should go based on driving time. – johanvdw Feb 19 '11 at 7:54
(anyway in that case IDW or kriging are bad techniques. Better use voronoi polygons to just connect the same travel times) – johanvdw Feb 19 '11 at 11:03
I've updated the methods to mention using TINs for interpolation (keep everything in vector). As this approach is intended as a visualization technique to give an overall picture of movement time, not a point-to-point true cost, I think IDW or similar is fine: it isn't accurate in a scientific sense, but that is often not the intention of maps of this nature (e.g., – scw Feb 25 '11 at 7:48
I use the phrase interpolation to be consistent with the software, but I agree that this is really a cartographic generalization approach: another area where the multifaceted uses of GIS ranging from the artistic to the scientific can cause conceptual mismatches. – scw Feb 25 '11 at 7:50

I could see two ways of going about this problem. One is pretty straightforward. The other requires a great deal of supporting data.

The straightforward algorithm would rely on convex hulls rather than voronoi polygons. Construct the convex hull of the vector endpoints and vertices for the street segments that fall inside your drive time cutoffs. Then, use this convex hull to select the connected networks inside your convex hull which are outside your drive time cutoff. These are the pockets inside your general area that are not reachable in the drive time (e.g. one way cutoffs, complex interior subdivisions, etc). Construct a convex hull for each of these isolated pocket networks and use these hulls as interior rings to your original convex hull.

Note that this particular algorithm gets a lot more complex if you are using true curves, since a true curve could fall outside your vertex constructed convex hull.

For the supporting data algorithm, you use a land partitioning. Parcels are the most obvious land partitioning, but not necessarily effective for every scenario. Based on your solution network, each parcel is either determined to be accessed from or inaccessible to the solution network. If the parcel is accessible, you place it inside the catchment area. If not, outside. On an area with developed planimetrics this can be pretty easy; just include driveways and private roads as components of the road network. If the partition touches the solution network, it is accessible. One of the difficulties here ensuring that all potentially accessible partitions touch the network. For example, if you have an interior common ground parcel in a subdivision, you need to merge that in some way with a parcel or parcels that touch the network. But you might have regions, like interior trails in a large park, that are not accessible at all that are simply left not touching the network. Like I said, a lot of supporting data, but a very effective algorithm once you have the data.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.