Park polygonal composition

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).

simple-park-layout1 - polygon with a hole

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.

simple-park-layout2 no holes

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.

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

simple-park-layout3 - max-side-middle-cut


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.