checking intersection of many (small) polygons against one (large) polygon by filling with rectangles?

I have a 2D computational geometry / GIS problem that I think should be common and I'm hoping to find some existing code/library to use.

The problem is to check which subset of a big set (thousands) of small polygons intersect with a single large polygon. (By "small" and "large" I'm referring to the amount of space the polygons cover, not the number of points that define them, although in general suppose that the number of points defining a polygon is roughly proportional to its geometric size. And to give a sense of proportion, think of "large" as the polygon for a state in the United States, and "small" as the polygon for a town.)

Suppose the naive solution using a standard CheckIfPolygonsIntersect( P, p ) function, called for each small polygon p against the one large polygon P, is too slow. It seems that there are ways to pre-process the large polygon to make the intersection checks for the majority of the small polygons trivial. In particular, it seems like you could create a small set of rectangles that partially/almost fill the large polygon. And similarly you could create a small set of rectangles that partially/almost fill the area of the bounding box of the large polygon that is not actually within the large polygon. Then the vast majority of your small polygons could be trivially included or excluded: if they are fully outside the bounding rect of the large polygo开发者_开发问答n, they are excluded. If they are fully inside the boundary of one of the inside-bounding-rect-but-outside-polygon rects, they are excluded. If any of their points are within any of the internal rects, they are included. And only if none of the above apply do you have to call the CheckIfPolygonsIntersect( P, p ) function.

Is that a well-known algorithm? Do you know of existing code to compute a reasonable set of interior/exterior rectangles for arbitrary (convex or concave) polygons? The rectangles don't have to be perfect in all cases; they just have to fill much of the polygon, and much of the inside-bounding-rect-but-outside-polygon area.

Here's a simple plan for how I might compute these rectangles:

• take the bounding box of the large polygon and construct a, say, 10x10 grid of points over it
• for each point, determine if it's inside or outside the polygon
• "grow" each point into a rectangle by iteratively expanding it in each of the four directions until one of the rect edges crosses one of the polygon edges, in which case you've gone too far (this would actually be done in a "binary search" kind of iteration so with just a few iterations you could find the correct amount to expand in each direction; and of course there is some question of whether to maximize the edges one at a time or in concert with one another)
• any not-yet-expanded grid point that get covered by another point's expansion just disappears
• when all points have been expanded (or have disappeared), you have your set of interior and exterior rectangles

Of course, certain crazy concave shapes for the large polygon could lead to some poor/small rectangles. But assuming the polygons are mostly reasonable (e.g., say they were the shapes of the states of the United States), it seems like you'd get a good set of rectangles and could greatly optimize those thousands of intersection checks you'd subsequently do.

Is there a name (and code) for that algorithm?

Edit: I am already using a quad-tree to determine the small polygons that are likely to intersect with the bounding rect of the large polygon. So the problem is about checking which of those polygons actually do intersect with the large polygon.

Thanks for any help.

In your plan you described something very similar to the signed distance map method. Google 'distance map algorithm' for details. I hope it will be what you're looking for.