Fill Polygon A with Maximum number of Polygon B

Question

I want to find how many of Polygon B can fit into Polygon A. I have a database of water bodies in the US as polygons of various unique shapes, 'Polygon A'. I have another layer with 'Polygon B'. Does ArcGIS have a tool to calculate how many times I could fill Polygon B into each waterbody polygon without Polygon B overlapping with itself?

Right now, I have a process that utilizes the Intersect Analysis tool however, I am hoping there is a tool that would Fill all water body polygons with the maximum number of Polygon B. Polygon B is a simple circle and can be converted into a different layer type (polyline etc) if needed.

DanPatterson · Answer

The process I described is meant to do one water body at a time.  "circle packing" is complex

A close approximation would be to use hexagonal tiling of the whole area, then intersect or spatial join these to the water body layer

Alvarado10 · Answer

Thanks Dan!

What tool would you recommend to keep the circles? There's a few options that work but with the large amount of data, processing time is quite slow. I would like to have a table generated that shows the original data from the water body layer with a new column showing how many circles are contained within each waterbody feature.

DanPatterson · Answer

You are looking for "circle packing"

python - Covering irregular region with circles - Stack Overflow

and there are no builtin tools.

Your best approximation would be to

* generate a hexagonal grid in your polygon extents
* take the centroid of each centroid
* buffer the centroid
* keep the circles (aka, buffers) that are completely within the polygon bounds

It won't be exact since you might have to algorithmically jiggle the start coordinates of the hexagon-ization to fit in a few more.

Not an easy task... but can be "close enough" for many purposes