Let us consider a simplified version of our basic 2×2 grid park. In this case we are just concerned with a placement of a single tree region in every of the 4 non-walkable regions (or grid subregions).


To place a tree region we have to locate the position in the local space of each of the regions.

Position can be calculated in two steps

  1. Edge and corner indexing against two (x and y) axes.
  2. Calculate position by parametrising the edges/corners in the local space.
  3. Place the item, optionally partitioning the region

Index building will be considered in the latter post. But we will consider options for parametrising and placing an object.

Corner Parametrisation

Corner diagonal offset

We take a diagonal line segment to the opposite corner and parametrise it in the range [0..1].

parametrise relative to vertex

  • Problems – which is the opposite vertex if the region is not-square?
(Optional) Corner Angle based offset

Instead of a diagonal line, we select an arbitrary line emanating from the current corner. We add an extra parameter- angle. Angle can be relative or absolute.

Edge Parametrisation

To find position using an edge, we need to first find the position on the edge and then offset into the region.

Position within the selected edge is given by parameter p in the range [0..1) (or maybe [0..1]?). However we can we can just use one parameter in p_n [0..n), where the integer part, floor(p_n), selects the edge and fractional(p_n) == p select the position within the edge.

Next we select the position within the region which is a quad. If the centre is more then just intersection of the paths, the adjacent non-walkable regions are not quads which may lead so some ambiguity. Another problem is when the quad is non-rectangular.

parametrise relative to edge variations

Non-parallel offset

We find a similar point on the opposite edge, draw a line between the the points on the opposite and the current edges, and then offset along this line. The whole area is utilised, no invalid (out of region) points may be sampled and no points are left out.

Edge parallel offset

Offset is applied to the normals. So items with the same offset are parallel to the edge. However for obtuse corners the area remains (see picture) and for sharp corners we offset into invalid positions. The latter is may especially be difficult to handle.

This method is permissible when the region is a non-quad (non-standard centre).

 Issues that remain
  • How to handle invalid parallel offsets for sharp corners
  • Most real life park regions are on rectangular.
    • Solution: cut out rectangle region (or regions) within non-rectangular regions