# QGIS tool to identify polygons that can fit a certain sized square within the polygon

I am trying to identify parcels with enough space for an additional building, and one of the parameters for this is: there needs to be a space of at least `9' x 10'` available to fit the additional building.

I used the QGIS tool 'Difference' to remove existing buildings from the parcels shapefile. I am now trying to see if there is a tool to identify polygons with enough continuous space for the additional building. I don't want to simply find the area, since there will probably be parcels with enough area, but it's not a square.

image of the remaining parcels:

• Hey Shelley, welcome to GIS.SE! Could you provide us with a sample screenshot of your remaining polygons? Especially interesting is, whether each parcel is it's own polygon, or not.
– Erik
Oct 19, 2018 at 14:03
• Hi Erik, thanks! I added a screenshot of the polygons. Each parcel is it's own polygon. I added a 6 foot buffer around each of the buildings before deleting it, so some of the deleted buildings took a bit of the other parcel with them. Oct 19, 2018 at 14:10
• So there are rings, which blows my first idea.
– Erik
Oct 19, 2018 at 14:14
• Do you have any front/side/rear setbacks to respect? Oct 19, 2018 at 14:14
• Hi there, front/side yards are acceptable. The new structure must be 6 feet from the any existing structure. I included a 6 foot buffer around the existing buildings before removing them. Thanks! Oct 19, 2018 at 14:18

This question refers in fact to an optimization problem: the Polygon Containment Problem, and a particularily difficult case too, because the containing polygons can be irregular, non-convex and have holes. Unfortunately, to my knowledge, I do not think than an accurate algorithm for such a problem has ever been implemented in QGis. However, I will propose an easy alternative that can at least help solving some of the cases.

First, from your initial layer (parcels after building difference), create a Buffer with a negative distance corresponding to half the diagonal of your new building space requirement. For this specific case with a 9 x 10 rectangle, the half-diagonal is `sqrt(9^2 + 10^2)/2` = 6.73 feet, so the Buffer distance is set to -6.73.

The output will be a layer containing all the zones (in green) where the centroid of the new building could be, no matter what the orientation of the building is. Some parcels will collapse into an empty geometry, you can identify and delete them by testing which features have an area of 0 or null in their geometries. At the end, any parcel apprearing in this layer and table are certain to have enough residual space to host a new building, therefore they can be flagged as available. You can select your original parcels by location and save them as a _Parcels_Available_ layer. Chances are several parcels will be identified at this point.

Finally, we can find the parcels that clearly cannot containg a building. We know, from the smallest side of the building, that a minimum of 9 feet of space is required to fit the building. By creating a -4.5 foot Buffer on the initial layer, it is possible to identify those cases. Some parcels will collapse to nothing. In the layer table, delete records with an area = 0 or null. Then, select any parcel than do not contain any of your two buffer layers, with a Select by location of your initial parcels with each of the two buffer layers, with the second selection in add to currect selection mode, then switch selection. Those are parcels that cannot contain a building for sure, and can be flagged and saved as not available (red). The entries left will be those in-between cases, where a much more complex algorithm would be required, to see if a building can squeeze in these parts (orange).

Interestingly, some labeling functions are subject to similar optimization problems. With a bit of tweaking with labels in QGis, I was able to generate the following result, by placing free labels with the rule inside polygons:

Although not perfect, it could be an easy way to make a more educated guess about how a rectangular building could fit. This could be an avenue worth exploring as well.

For demonstration purposes, I used larger values for the buffers and buildings to get more varied visual examples with my dataset.

• I had no idea about the optimization issue, very interesting. This was an excellent workaround! Thank you for the detailed response, it worked great! Oct 23, 2018 at 0:43