Non-walkable region partitioning

The regions are the faces that result from partitioning the park with paths. Actually paths are extruded, but regions are considered separately. The regions are non-walkable, but can represent park partitions like flowerbeds or patches of grass, or a place where the tree is planted.

This is enchancement of the centered partitioning described in the previous post.

The new procedures were created

  1. Contraction
    All vertices are moved towards a centroid by a relative distance to it (distance to centroid/centre is 1, move range clamped to [0 . .0.9].
  2. Edge Partitioning
    Every edge is split with level n, for n = 0 no splitting occurs, for n = 1 we add one vertex in the middle, for n = 2 we evenly place two new vertices on the edge, splitting it into three edges.
  3. Smoothing
    Every vertex is reposition into the sum of two adjacent vertex and itself (v_curr + v_prev + v_next)*1/3; alternatively weight_middle, by default 1/3 can be used to adjust the neighbour weight (e.g. 0.5 means neighbours get 0.25 of weight each).

The image below shows on the example of a simple flowerbed partitioning with the application of Contraction, Edge Partitioning and then multiple Smoothing for the first inner loop, and additional Contraction for the most inner polygon.


Park shape generation

I have experimented with squared parks with 4 entrances at each side.

The first example shows just two paths crossing in the middle. A small round square is place at the intersection, which could be a square, rombus etc.


A second type of the park is where the regions are cut ellipses centred at the park corners. there is more place to fit something in the centre (a fountain, statue, flower beds etc.).




Bezier curves can alternatively be used to smooth the corners. Any degree can be used, determined by the number of points in the corner region.



Bezier curves also produce interesting results when the points control points are permuted randomly. Perhaps it may give a slight impression that a (human) designer has modelled it.

Bezier with random offsets



I have decided to work on generation of parks. This should be pluggable into the existing city creation framework.

The input to the system should be

  1. A polygon on the plane
    We consider a park on the flat surface for simplicity.
  2. Street network (optionally)
    The park can contain a street network that has been constructed externally, perhaps automatically by the same module that generates the city street network.

The output is a set of geometry that is based embedded into the plane that represents the park. Geometry can be abstract so that the rendering system is free to choose how to interpret the representation, for example to render the tree foliage as a series of polygons for fast preview or creating an instance of a tree with individual leaves.

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.