Spacial Indexing

Because centres produced in Grid v2 using intersection algorithm are not placed in meaningful order beyond 2 by 2 regions, we need to find a way to index them.

Rtree implementation of boost geometry was used. Rtree is basically b-tree with spacial indexing (n-dimentional rectangles), so insertions are automatically balanced. Alternatively it would be possible to individually intersect path strips, but for more complex algorithms or other patterns spacial indexing is much more beneficial (for instance in terms of search complexity).

Grid Indexing

To find region index we divide iregion into as many Indexing Regions (XRs), which would also take the space of the paths [NOTE will these XRs not overlaps with the negibouring regions?]. XR_i,j will obtain Non-walkable Region, NWR_i,j.

Each NWR will have x and y index from which symmetry can be obtained. From then we can choose how to compute a symmetry. We have SYMM_BOTTOM_LEFT and SYMM_BOTTOM_RIGHT which are self-explanatory with the same orientation for all blocks.
SYMM_RADIAL_2X2 we have orientations in 2×2 block set with the orientation = 3 * x + y*(int)(-1)^i, where i is x index, x = i%2, y = j%2.

For 3×2 (4 by 3 regions) and radial 2×2 symmetry result is as follows:grid-indexing-symmetry-3x2