Optimal tiling of polygon using ArcGIS Desktop?

Question

I am trying to tile a polygon with a minimal number of fixed sized squares.

Currently I am creating a fishnet over my polygon then spatially joining the squares that intersect the polygon. This is not optimal.

Also note the squares can be shifted vertically/horizontally but not rotated.

My end goal: The polygon represents a clipped image and I want a tiling of the clipped image. Where each tile is 300px by 300px. Some overlap is fine if that makes the problem easier.

Current

Manually optimized

Are there any tools or algorithms that would help with this? I am proficient with Python and ArcMap.

The polygon was created from line features so I also have access to those segments. Maybe that would will help for generating the squares.

The entire polygon must be covered.

Answer 1

I think the class of problem that you are looking at is called Polygon covering:

A covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered and on the types of units allowed in the covering.

While the "near fishnet" that you are trying to create would be useful, as an example, for GIS professionals trying to create indexes for map series which minimize the number of pages while maximizing the feature area per page, I think that you may find more potential answerers by tailoring this for a different audience and posting it at either of the maths sites where I have seen at least two similar sounding questions:

• https://math.stackexchange.com/questions/64223/cover-a-polygon-using-a-minimal-set-of-rectangles
• https://mathoverflow.net/questions/105164/covering-a-polygon-with-rectangles