Major part of park construction is partitioning of the input polygon into subregions that shall represent the functional components of the park. For example the basic park would contain a flowerbed in the middle surrounded by a green area (two polygons).

The polygons considered here are composed of line segments, and *arcs* or *polynomial curves* are not allowed. An internal will might contain curves, but these will be parametrised into polygons or *polylines* for simplicity and for compatibility for now (*CityEngine* cannot handle polynomial regions for instance).

The problem with placement on one another as seen in the picture above is that the inner polygon is completely contained within the outer one. So if we decide to populate the outer polygon with trees, they will also be placed over the inner one which represents a flower bed.

Task: It is required to cut the outer polygon to make a whole for the inner polygon.

One solution is to simply cut starting from the outer boundary of the first polygon to the boundary of the inner polygon.

Second solution is to split the *Polygon1* into to polygons and then subtract the *Polygon2* from it. CityEngine park example is partitioned this way, by my assumption – manually.

- Preconditions are that we have two simple polygons and that
*Polygon2*is contained entirely within the*Polygon1*. - Compute the centre of the
*Polygon2*–*P2c*. - Select the largest side of the
*Polygon1 – S1.* - Partition
*Polygon1*with the line passing through*P2c*and the middle of*S1*into*Polygon1a*and*Polygon1b*. - Subtract
*Polygon2*from (*Polygon1a +*).*Polygon1b*

There can of course be problems when, for example either of the shapes are concave (not convex) – and even then it is not selection of *S1* as a start of the cut line is not guaranteed to be optimal.