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.