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.


enter image description here

Manually optimized

enter image description here

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.

  • Would selecting only the squares where your polygon intersects its centroid be appropriate? This could significantly reduce your square counts. – Trevor J. Smith Oct 2 '18 at 17:27
  • I need to cover all of the polygon and I think that may leave uncovered areas on the outer sides of the polygon. I will update my question to include this. – Squanchy Oct 2 '18 at 17:38

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:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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