Stage2 – Grid rule

System changes

Looking at my current code I have decided to remove unnecessary abstraction – parasitic code. Only two structure are required:

  • Mutable – geometry that is transformed and state is stored here
  • Immutable – rules, park design, model etc.

Mutable structure I will call ParkState and immutable ParkModel (actually ParkModelSquare in case I shall have other parks).

Grid Rule v1

I decided to start with the grid rule. It should be possible to apply it recursively.

Park -> grid(2, 1) { SubPark1 }
SubPark1 -> grid(3,2) { ParkRegion1 }

Integer parameters of the rule changed their meaning. For instance 2×2 means 2 paths and 3 regions along each axis, NOT 2×2 regions as specified earlier.

It is trivial to implement 1×1 (that of 4 regions) subdivision:

  1. create two perpendicular path polygons that touch opposite edges of the iregion
  2. unite them into a single polygon – a cross
  3. subtract from the iregion to create subregions

However for 2×2 grid a hole is created after the operation 2. Hence we need to split the paths at the junctions.

The first implementation includes a function that iteratively splits into regions and then unites the two perpendicular sets of path regions. Each of the paths in each set are parallel to each other (NOTE details of the splitting are omitted but because they become irrelevant with introduction of the next section).

However in the next iteration two changes have occured:

  1. boost libraries were updated from 1.5.6 to 1.5.8, and the geometry library have been updated to include standard operations like union_ and difference  to support multipolygons.
  2. the need for separate centres removed the whole problem with polygons with holes. The intersections of the paths become centres

Grid Rule v2

In the light of the developments described above Grid now supports three types of regions:

  • Centre regions
  • Path regions
  • Non-walkable or park regions

These types also correspond to the nodes, edges and faces of the connectedness graph.

First of all the two sets of perpendicular path regions are stored into two multipolygons.

Centre regions are created by intersecting these multipolygons.

Path regions are created by subtracting the centre regions from the union of the path regions (which are a multipolygon with holes)

Park regions are created by subtracting the same union of path regions from the iregion.

Grid Centres

Simple intersections of path regions can be replaced by more elaborate path centres. Centre is specified inside the third block statement with a shape rule and optionally a label.

Rhombus Centre

We describe creation of a Rhombus centre. Rhombus shape operator/rule takes the form of “Rhombus(size1, size2)” where the sizes are the extensions of the shape along the x an y axes.

In fact the extension occurs along the parametrised by length path central segments. Think of the path regions created by extruding the path segments.

  1. i and j segments are intersected to find the centre point.
  2. From centre we extend upwards by size2 (y) along the vertical segment. This is the first corner of the Rhombus. The second corner is obtained by extending eastward (left direction) by size1 along the vertical segment. Similarly we extend downward and westward.
  3. We create lines which also collinear with the rhombus sides by connecting corner i and (i+1) mod 4, for each of the four corners.
  4. We intersect the lines with the path regions. For instance line1 is intersected with east side of vertical path region i and upper (north) side with the horizontal path region j. Similar operations for the others.
  5. The obtained intersecting points are connected into a polygon to create a centre.
    rhombus centre and surrounding paths

A System for Reordering of Indices

Boost subtract operation does not take into account ordering of indices. For instance subtracting a single path region from a quad input region (e.g. applying grid(1, 0)) will result in one of the subregions being of different index order.

We need to sync the indexes of the vertices of the input region to the resulting subregions. Edge indices directly depend  the vertex indices and will be correct provided vertex indices are fixed. Reindexing as follows

  • We consider only quad indexing only currently. All edges need to be indexed 0 to 3. We choose the order as the image below, that is we start with the positive y direction and go clockwise. Indexes are assigned during construction.

    1. get edge direction e_i = v_(i+1) – v_i
    2. compute angle value using atan2 function. x and y values are inverted as we want to obtain the following index.
    3. divide angle by Pi/2. At negative y we have +/-2 because angle can be interpreted as +/-Pi.
      (4-angle) fixes the index for values [-Pi, -Pi/4]. Integer value (or a cast to int) is an index that we need!
  • Each produced shape we need to orient the same was as an input shape; for instance indices of the input were [0 1 2 3], and one of the produced shapes has indices [2 3 0 1] we create a map [(2->0) (3->1) (0->2) (1-> 3)]. Application of the map to the produced shape restores the orientation or, perhaps fixes it to that of the input shape.

Recursive Grid v2.1 – Corner Preservation

When Grid rule is applied recursively, Grid v2 paths will be corrupted. The following rules

Park -> grid(1, 1) { aI } { ParkPathI } { Rhombus(25, 45) ParkCentre }
aI -> grid(1, 1) { aII } { ParkPathI } { Square(4, 4) ParkCentreII }

Produces these results (v2)


As can be seen from the south-west (lower left) region the third edge is selected from the centre instead of the ‘logical’ quadrant.

We fix this by adding this so called logical quadrant that is used for path construction, here in the second level of recursion. Logical quadrant consists of the region, which would have  been constructed without the centres. In this case we would not have the rhombus centre and there would be four squares after application of the first Grid.

Paths are now fixed in the second iteration as seen on the picture (v2.1)