Creating non-overlapping, road-centred circles for an entire road network

[AndreaClouston]

We are a group of ecologists interested in designing and evaluating road-based wildlife survey designs. Using a complex road network over a large geographic extent (e.g. thousands of square km), we require a method that will create, based on a specified radius distance, an output file of all possible, adjacent, non-overlapping, road-centred circles for the entire road network - given a single, arbitrarily chosen starting point. The method must be robust to complex road patterns (including intersections and switchbacks). Conceptually, the problem seems fairly straightforward: from a given centroid, search exactly 2*radius until a road is encountered, then establish another centroid (and circle of radius x distance) and continue searching while complying with the 2*radius rule. If conflicts result from complying with the search rule - e.g., a new centroid could be in location A or B - simply taking the first new centroid would be an acceptable solution.

Advice on how to implement this with ArcGIS, R, SAS/GIS, or other software would be very helpful. Our preference is for a script or similar solution that could be set up to run in batch-mode after the starting point and radius definition were designated.

[KimOllivier]

It's like the old Irish joke about getting directions when lost - "If I was trying to get to your destination I wouldn't start from here"! It would help to see a diagram of your final requirements.

Geoprocessing tools work best on the whole dataset at once, not in the interative solution that you are imagining.

My first thought is that a set of stepped circles along a road is a Buffer. So why not a buffer of distance equal to the radius. Then the circles will fit inside the buffer. So how do you get the centres?

Centres along the roads can be easily created using a linear referencing system and using an event table with distances equal to twice the radius. I can see this might clash at intersections, so some sort of sphere-packing might be required there. Maybe linear referencing can be used there to only pass through the intersection once to resolve that, with side roads stopping at a suitable distance that does not intersect the main road buffer.

All of these processes would run once for the whole dataset, maybe there would be several steps (say less than 10) to handle exceptions to weed out strange cases, but not millions of iterations.

[MarkEllis]

I think kimo has the right idea - points along the roads, 2*r apart, which can then be buffered.  It might require simplification of the road network to create, but the resulting circles could be used overlaying the original complex road network.  Using a linear event theme, this would be a fairly straightforward process.

Have you thought about using a hexagon grid?  This could be generated from an arbitrary starting point.

[ChrisSnyder]

When the road is perfectly straight (i.e. no vertices/curves), the next circle center will be exactly 2*r "down the road" from the preceeding center. However, if the line curves at all, this method falls appart, and the derived circles would overlap (overlap % being a function of how curvy the line was).

What you really need is a method to traverse the constituient vertices of a line segment, find the two sets of vertices where between them a new center point would be located that is 2*r from the last center (as the crow flies, not as the crow drives), and then interpolate a new center location.

Although in this case a raster solutuion wouldn't be as precise as a vector one, I'll bet Bill Huber would jump at offering a very nice raster-based method if you posted this in the Spatial Analyst forum...