Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am trying to work out an algorithm for creating the maximum radius circle within an irregular polygon (a census tract) based on a given center of the circle.

The motivation for this is to obscure the location of an individual who has answered a survey. Their actual location is known, however it needs to be obscured in the analysis, in order to release the data to the public, for further analysis.

We want to have a donut shaped polygon for each survey respondent that has some inside radius (easy), bounded by an outside radius that is constrained by the census tract that the individual is in. Their final location will be randomly placed within the donut polygon.

I have seen many answers to similar questions here, but not this specific one, which in this case starts with a SPECIFIC location.

Once we have the donut established, we can randomize the location of the individual response within the polygon. That's relatively easy...

Thanks for your ideas, mine so far have seemed pretty brute force, and computationally "expensive" or inefficient...

share|improve this question
Isn't it just the shortest distance from the specific location to the boundary of the polygon that you want? –  Nicklas Avén Mar 17 '13 at 22:35
Which software or programming language are you using? –  Pablo Mar 18 '13 at 15:13
Why not just intersect the desired annulus with the tract? Better yet, there's no reason to use circular shapes--you could just as well use a square annulus, which would lead to faster execution. –  whuber Mar 18 '13 at 15:22
There seems to be little or no consensus. An overview of some methods appears here, beginning p. 34. A sophisticated method was proposed on our site. A recent international workgroup explored many related issues. A recent review by Mathews & Harel may be useful. –  whuber Mar 18 '13 at 19:45
@whuber, thanks so much! I assume you are the same Bill Huber that has been posting help and source code since I first started using GIS in 1998. I loved all of your Avenue scripts, learned a lot from them (and I assume the program referenced below is ArcView, it's amazing how fast it runs these days!!!). Just wanted to let you know how much you are appreciated in the community of GIS practitioners! Thanks for all of your years of great advice! –  Percy Mar 20 '13 at 16:02
show 6 more comments

3 Answers

A simple method to move locations within such annuli exploits a gridded representation of the distance to the tract boundary. Beginning with a polygonal representation of the Census tracts (which is the usual),

  1. Convert that to the polygon boundaries (a polyline layer).

  2. Compute the Euclidean distance grid to the boundaries.

  3. Extract the Euclidean distances at the given locations.

  4. Move each location within the range given by the distance--which, by definition, is the maximum to the boundary.

Each typically requires just a single command with a GIS, making the entire sequence easily automated and easily carried out manually. These are efficient commands, because they do not require constructing a buffer for each point (which typically creates several dozen to almost a thousand points in order to describe a ring, or annulus). No searching or random trials are needed, either: the points are directly displaced by amounts guaranteed to leave them within their original Census tracts.

For example, I moved 172,902 locations within 47 tracts in random directions by displacements uniformly distributed between one-half the distance and the full distance to the boundary. Here is a part of one tract before the move:

Figure 1

(yellow squares mark the locations) and after the move:

Figure 2

(now gray squares mark the new locations). The total operation took just a minute or two (using an old outdated GIS :-).

By comparing these figures closely, you can see that

  • Points that are now close to the boundary (such as near the two lakes shown as white "holes" in these figures) necessarily stay close to the boundary.

  • Points far from the boundary tend to move far.

Consequently, a point close to the boundary likely (but not certainly) originated very close by, whereas any point far from the boundary likely originated from somewhere else far from the boundary. These two tendencies are far from completely random: they could (fairly easily) be exploited by someone who wishes to penetrate the privacy that these movements were intended to afford.

Better methods would make the connections between final and initial location more tenuous and more random. At a minimum, points should be moved within reasonably large neighborhoods rather than within neighborhoods of varying (and possibly arbitrarily small) size. Such movements are not readily carried out with grids, because typically they require some trial and error: you generate a bunch of random points within a neighborhood of each original point and select the first one that lies within the same Census tract. That's a loop involving (1) a random movement and (2) a point-in-polygon inquiry. Both operations are fast, but this requires a bit of programming to implement the loop.

(In a comment to the question, I provide links to some studies of methods used to disguise locational data for privacy purposes.)

share|improve this answer
add comment

Hopefully this Python solution will help you out. The general workflow is as follows:

  1. Convert polygons to polylines so that you can calculate a Near distance
  2. Buffer the points based on the near distance

enter image description here

# Import arcpy module
import arcpy, os
from arcpy import env

env.overwriteOutput = 1

env.workspace = r'C:\sample.gdb\temp'
Dir = env.workspace

# Local variables:
points = "points"
polygon = "polygon"
points_2 = "points"
buffers = "buffers"
polyline = "polyline"

# Polygon To Line
arcpy.PolygonToLine_management(polygon, polyline, "IDENTIFY_NEIGHBORS")

# Near
arcpy.Near_analysis(points, polyline)

# Buffer
arcpy.Buffer_analysis(points_2, buffers, "NEAR_DIST")
share|improve this answer
Thanks! that looks like it might just work! :-) we'll give it a try! –  Percy Mar 18 '13 at 17:20
add comment

I just wanted to test out your donuts in PostGIS

I tried it on PostGISonline.

To do the same test you go to: http://postgisonline.org/map.php

There is some polygons called "property" print:

SELECT * FROM property;

and press "Map1"

Then you can test the donut-code by copying the below to the textarea and press "map2" (then the property-map will remain):

SELECT ST_Difference(ST_Buffer(the_geom,dist),ST_Buffer(the_geom,dist/3)) the_geom,dist FROM
    SELECT ST_Distance(poly.boundary,points.the_geom) dist, points.the_geom FROM
        SELECT ST_Boundary(the_geom) boundary,the_geom FROM property
    ) poly
        SELECT ST_SetSrid('POINT(137816 267009)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(139816 268542)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(135016 268102)'::geometry,3021) the_geom
    ) points
    ON ST_Contains(poly.the_geom,points.the_geom)
) a

That should give you a result something like: enter image description here

share|improve this answer
PostGIS just totally rocks! Thanks, that's awesome, nice work! –  Percy Mar 24 '13 at 22:46
add comment

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.