Indexing and Selecting using Logical Edges

Logical Edges Implementation

As mentioned already, logical edges (or LEs) contain multiple physical (or geometrical) edges. A selection unit is now a logical edge instead of a physical vertex as it was previous to this moment. Indices and directions are still used but relate to LEs instead of vertices. LEs are implemented as integer values of a start vertex and the length of the path to the next corner vertex.

When length is zero selection is no longer contains edges could represent a single vertex.

Autoindexing Input Region

A polygon with |v| > 4 but that roughly looks like a quad is treated as a ‘quad’ by partitioning all edges using (currently only) angle thresholding into 4 LEs


Vertices of the detected LEs or corners are also used as a corner shape for the Grid rule, because for path partitioning Grid rules requires a quad as input.

Grid Changes

  • adapted LEs to be used as input
  • Subregions (may be non-quads) and Corner Shapes (quads) are spacially indexed the same way
  • Matrix indexing
  • Corner Shapes may contain vertices that do not add new geometric information. Such vertices are removed. Thresholds were increased to deal with increasingly large Epsilon values.
    • Almost identical vertices, that is with an Epsilon distance between them are removed.
    • Vertices that span an angle of close to 180 degrees with the adjacent edges are classified as middle of the edge vertices and are removed.
Matrix Indexing
  1. Compute points of quarter centres (NOTE border quarters are slightly larger because path is subtracted only from one side; TODO fix that).
  2. For each unsorted quarter intersect find intersection with the quarter centre and save at the matrix array index. Do the same for corner shapes.
  3. Now it is possible to walk through matrix and access both quarters and corner shapes (corner quarters).
    1. Create labelled shape for each quarter
    2. Remove duplicate and middle-of-edge vertices for each corner shape and set it to appropriate quarter.
    3. Set indexing.

Peel Changes

  • Input remains the same
    • Iregion
    • Selection: list of non-overlapping intervals [a, b]
    • Extrusion size
  • Process separated
    1. Linestrings created from selection list and input shape
    2. Each linestring extruded into a single connected polygon
    3. Boolean polygon cutting and labelled shape creation
      1. Substrate shape created by differencing iregion with extruded shapes
      2. Fixing of polygons
    4. Indices are set
Linestring Creation

Given iregion and a selection extractBoundary computes a linestring around the boundary of the iregion.

  1. Split one selection range into selection for reach LE and pair with index of that LE. Whole LEs of course will have range [0, 1]. For instance selection [0.6, 2.3] will result in the list:
    [0:[0.6, 1], 1:[0, 1], 2:[0, 0.3]]
  2. (optional) Ranges are reversed if selection direction is negative. Also each LE selection ranges are reversed [a, b] -> [1 – b, 1 – a]. Note that LE indexing is not changed, only the order of evaluation to closely match physical representation. For example the range above converted to:
    [2:[0.7, 1], 1:[0, 1], 0:[0, 0.4]].
    [TODO picture]
  3. Ectually extract LE subedges.
    1. Get LE, as linestring on the local range [0, 1]
    2. Extract ‘substring’ or [0, 1] converted to [a, b] which could be[0.7, 1]. The algorithm also rather large in code is quite trivial nevertheless, important only to mention is that the edges are parametrised by length.
  4. Joing LE subedges into one linestring, removing duplicates at joining points.

Initially only inner extrusion has been used. However as a result of floating point errors using Boolean operations – part of the boundary was not clipped appropriately. In the second iteration outer extrusion has been enabled and which amount controlled by an additional argument.


Extrusion algorithm as follows

  1. Split polyline into individual edges or segments
  2. Create pairs of inner and outer segments; Outer segment may either lie on the polyline or outside when outer extrusion parameter is positive.
  3.  Extrude polygons or blocks are created. At this point however we cannot join them unless angle between adjacent segments is180 degrees or lower.
    extrusion blocks
  4. Joining polygons are created connect adjacent blocks. To accommodate both inner and outer extrusion joining polygons are applied to the whatever side of the polyline that has a greater angle. For zero outer extrusion empty polygons are added.
  5. Inner product algorithm joins sets of blocks and joining polygons where both * and + operation overloaded as a joining operation. Because number of joining polygons is one less, an extra one is added to match the number of blocks.

Grid Quarter Selection

It is necessary to select a quarter (or subregion) resulting from the Grid rule. Instead of a single label, a list of expressions paired with labels are now allowed – when expression matches a given quarter – label is selected. At the end there should be a label without expression to guarantee a label for for a quarter that has not been matched by the other expressions.

For instance instead of:

Park ->(…){ ParkQuarter }

It is possible to have:

Park ->(…){ ParkQuarter | 0, 1, Quarter2 | odd, 1, Quarter3 }

In other words we replace label with label_list:

label_list = label_expr ( ‘|’ label_expr )*
label_expr = label | x_idx_expr ‘,’ y_idx_expr ‘,’ label
x_idx_expr, y_idx_expr =  [‘!’] idx_expr
idx_expr = NUM | ‘odd’ | ‘border’

Where index expression is either a number or a constant label which corresponds to multiple indexing of being either odd, on the boundary. We could also have a negation of an expression. However negation applies to individual axes, for instance “!x, !y, Label” negates both x and y.

Autoindexing of the Input Region

Input Shape Autoindexing

Since physical edge indexing is being abandoned, we introduce logical edges – groupings of the input region edges into geometrically (or otherwise) meaningful sets. Selection indexes shall correspond to that of these sets. Applied rules should preserve/propagate these edge sets.

Following shape classes could result in the following actions:

  1. Rectangular quad – trivial case.
  2. Quad, not axis-aligned, we can try:
    • simple: determine index for the first edge, increment successive edges
    • harder: compute Oriented Bounding Box; translate longest edge of that to x-axis; edge to the left (W-edge) has index 0.
  3. |e| > 4, but roughly looks like a quad:
    • Cardinal Directions selection will create 4 groups of edges
    • …?
  4. |e| > 4, looks like a multi-polygon
    • length/angle threshold.

Autoindexing of Input Shape

Grid-based Parks

Grid rule requires for input region to be a quad and ideally rectangular or close to rectangular or it will look strange. In other words we need to provide the following guarantee to Grid rule:

  1. |Vi| == 4, Vi are vertices of the input region – a quad
  2. All angles >= threshold1 (e.g. 70 degrees) – close to rectangular
  3. Min Area >= threshold2 – minimum area required to build a park, otherwise fail (no derivation or a alternative rule)
  4. Input region convex – otherwise results make no sense.

The following fixes apply to the appropriate points

  • Oriented Rectangle (Box): 1, 2, 4
    • Bounding Box
    • Inscribed Box
    • Linear Combination
    • Optimised Box that occupies area sufficient for a park (harder problem)
  • Axis-aligned box: certain design constraints
  • Autoindexing: 1
    • Cardinal directions when looks like a quad; Grid still requires a ‘corner shape’ which can be a quad with vertices corresponding to the meething points
  • Autoindexing + Oriented Box,
    • which vertices are at proximity (using a certain function) to the meeting points


Possible solutions for Selection v3

The selection problem is plagued by edge explosion and increasingly complex and dubious grammar results. New selection strategies are to be considered. Furthermore a layer of abstraction is to be placed between the physical and logical geometry elements:

  • Corners or logical vertices – corresponding to selected vertices on the actual geometry that have a special importance
  • Logical edges – should be enclosed between two corners and may contain a number of physical edges within – a polyline, or a curve. It should be used as a unit of selection (an integer range).

Selection Modes v3

Abandoning the physical based selection the new methods keep numeric indexing, but pointing to logical edges instead of the physical ones, as we see later.

Selection Propagation

Each rule should be capable of propagation of default input selection  to derived shapes the best way possible, for instance as seen below for the Peel rule.

Peel edge set indexing propagation

For partitioning rules such selection will be based on closeness to the boundary:

  • Whether or not it is located on the boundary
  • Edge set touches the boundary

Optional: specify level within the hierarchy to as closely as possible to match to the current geometry of the shape. For instance one before last Peel rule or first Grid rule (could use negative indices to count from the ‘front’ of history).

Grid Autoreindexing
Reindexing for Grid rule

Grid rule auto-reindexing is straightforward except for question of what to do with 45 degree edge – it can belong to the lower or higher index or split between both, as seen below – in this case it is crucial that edge assignment is symmetrically consistent.


For Voronoi regions there is a little more ambiguity so one selection method has to be chosen.

FF-Regions Autoreindexing
Reindexing for FFregion parititioning

Custom Shape Selection

In addition of edge set index based selection, rule can perform a custom selection on any part of the input shape boundary.

Edge Angle Selection

Select edges which orientation is within a given angle range, e.g. [85, 95] degrees are roughly perpendicular edges.edge-angle-selection

Angle Range Selection

Select edges that lay within or partially within the radial region surrounded by two rays cast from the centre.angle-range-selection

Direction Grow Selection

A number of directions are given. May result in inconsistent selection for non-convex shapes!

  • Cast rays from the shape centre along these directions until an edge is hit.
  • Grow selection for each edge. Attach successive neighbours to the existing selection.
  • Stop when threshold of subsequent edge is too high
  • Question: What to do with unattached regions?
    • Keep growing until all edges are attached
    • That containing more divergent (from threshold) value continues
    • Optimisation problem…
Cardinal Directions Selection

Based on W, N, E, S directions. Every polygon with |e| >= 4 should be capable of accepting a cardinal selection.

  • Edge Angle selection should with appropriate angles (for instance [-45, 45] for East) will work only for convex shapes.
  • Angle Range selection will also work on concave shapes but will not work so well when lengths of the sides (or edge sets) differ a lot (high variance of edge set lengths).
  • Direction Grow along the axes.
  • Dominant-direction symmetrical selection.
    • In the picture above (Reindexing for Grid rule) the dominance (say set by the user or selected to one value by default) is symmetrically consistent for the mirrored regions.

Rule History Selection

Such selection has already been discussed for Peel rule. However is it possible to create generic selection that all rules could adhere to?

Selection v2

Previously to this point actual vertices were used for selection. A new selection system was needed that would widen (or create) an abstraction gap between geometry and identifiable element used in grammar. Because edge to vertex relationship remains the same we discuss vertex indexing only.


Index array is used to access polygon vertices instead of dereferencing actual geometry. For instance vertex 0 is not the first vertex in a container of the polygon representation, but the first element in the index array, value of of which points to the container element. This way any geometrical operation does not violate logical or spacial order of the elements.

Current Indexing Problem

Auto selection (for instance that of Peel rule) is still not stable because the rule stores a set of vertices, but the selecting rule manipulates on ranges, which are edge based. Vertex to edge conversion looses selection of single vertices. In addition edge to vertex selection mutilates selection where two intervals are separated by one edge – both vertices of that edge are contained in adjacent selections, so reverse conversion unites the two selections into one.


Grid operation now enforces symmetry based on vertex indexing. Because the direction for x or y-mirrored regions change the direction (for instance to counter clockwise from default clockwise) and the geometrical representation uses requires of the same implementation for all elements – indexed orientation may differ from the actual one. Hence we can save indexing with two items, start vertex and direction. Start vertex is computed based on the outgoing edge orientation of one of 4 types. This works well for nearly grid aligned (of course also for perfectly aligned) shapes, but near diagonal shapes, for instance rhombus centres this technique does not work.

Path Parametrisation

In a previous approach to specify positions of the objects along the polyline for Insert/Place rules one would write for instance [0.3, 0.5, 0.7] – three objects in the centre separated by 0.2 (20%) of the selected path length. However it is quite tedious to specify each individual positions and not very algorithmic. New parameter subrule allows a shortcut: 0.3:n3:0.3 – meaning there is distance of 30% from each sides and three objects in the middle; an alternative form 0.3:l0.2:0.3 also works. In fact we can omit the last number as well 0.3:n3.

Implementation for Ray and Free Form Regions v1

Ray Cast Regions

As described already, the poisson scattered circles (2d disks) serve as locations for path centres, but certainly their radius is smaller than that of poisson disks – than to make room for the paths. Poisson circle radius as a rule parameter.

Paths are connected as follows. First each corner connects the nearest centre with a path. Second a single paths between all the centres is found – construction of a spanning tree. The algorithm walks through centres and tries to connect to each centre to one of the kNNs with the condition that such is not already connected. If all kNNs are connected, we simply do an exhaustive search for an unconnected one. Newly connected centre is selected as the next one. Only n-1 centres are processed this way, of course (|E| == |V| – 1).

The resulting tree may contain a crossing when embedded into the plane or a layout, so each path section is merged with the existing set of paths right after creation – otherwise when fusing (merging) the unconnected paths with the centres afterwards a boost geometry error will occur.


For next Iteration
  • Number of circles as a parameter (user would prefer that to the poisson radius)
  • More elaborate connections. Even if it is a spanning tree – perhaps try to create a graph that is embedded into a plane?
  • Region indexing

Free Form (Smooth) Regions

Poisson circles are scattered (the same way as above) and the centres are grown into Voronoi regions (or diagram), which are then shrunk (the same process as used for a straight skeleton creation), and smoothed by using subdivision. Subdivision weighting is another rule parameter.


For next Iteration
  • Better smoothing techniques – a polynomial curve perhaps?
  • Number of circles (same as above)

Poisson Disk Sampling – Bridson 2007

Poisson disk scattering or sampling has points more or less evenly distributed within the minimum distance r from each other. This distribution is similar to the receptor cells in the eyes of humans and other animals [Cook 1986]. Previously to this method I have implemented random placement based on jittering as described by Cook.

Bridson introduces a grid for growing distribution and also spacial indexing, which contains indices to samples or -1 for emtpy cells. Each cell should accommodate at most one point, that means that diagonal – largest distance – should be less (or equal) to the minimal radius, or r / sqrt(2) (r / sqrt(n) for n dimensions as described in the paper). Algorithm starts with a single point and grows around it. References to the current ‘grow’ points are stored in a separate array and points which may no longer accommodate new neighbours (e.g. internal) are removed from this array. When the grow array is empty algorithm terminates. Sampling is performed in annulus of radii r and 2r.

I have created a class using GML vector types (instead of boost geometry this time ;)) and using uniform distribution of boost libraries. I normalise the random value closer to the outer radius of annulus, or r*(2-rnd^2), where rnd is a uniform random value in range [0..1]. Neighbours are searched up to second edge away (e.g. (2, -1), (-1, -2)).

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

Recursive Peel and Edge Indices


The problem with selection arises when we have a non-quad shape in a rule production.

Indexing of regions, for instance in the context of the grid rule works well as long as we have [0-3] indexes for W(est), N, E, S directions.

Instead of one type of index based on orientation, or distance from the boundary, we need other types of indexing methods, for instance those that are semantically-aware.

It would be nice to have the following selection modes

  • Edge interval that was result of the peel operation
    • when placing something between the peeled regions
  • Outer iregion edges
    • when placing something on the boundary
  • Direction based (W N E S) edge selection. If we have multiple edges facing West, parametrisation, by length, will be of the combined edge length – those facing west
    • we want to place trees on the south-facing borders
  • Direction continuity selection. Selection for West-dc edges will also include edges NOT facing west, IF they are resulted from operation from west facing edge OR (!) when they are enclosed by west facing edge.
    • we want to place trees on the west side of the park but not all edges may face west

Index operators v2.1

Peel based selection


Shapes that result from the peel operation allow edge selection based on what was peeled. For instance a is the selection passed to the peel operation; b and c were extruded.

  • PEELED_BASE, short version – PB, the ‘a‘ segment in the image
Implementation Details

During peel operation a and b are recorded by storing copies of the points. Another operations on the derived shapes can make selection based on these edges, for instance  for PEELED_INNER selector if an edge endpoints are in b, then it is selected.

Boundary Indexing

Two options for such:

  • Edges incident to iregion (corners). The problem is that there may be more vertices between two corners – we need to consider an ‘edge’ between two corners NOT vertices.
  • All edges resulted of splitting or modifying iregion edge. Edge implementation does not need to be changed however more operations – intersections – are required; extra problems might arise from the intersections.

Enumerated Indexing for Grid

We are returning to enumerated indexing.

Lets consider the 1×1 path (2×2 regions) case again.

grid indexing

Indexing shall start at the iregion corners. The direction will be determined where the second index is.

Since iregion indexing starts at SW – the lower left corner, it shall be mirrored to the remaining elements (in 2×2 regions it is simple!).

Polygons are ALWAYS oriented one way, in our case clockwise. The indexing system allows us to avoid re-ordering vertices after each operation!



Non-symmetric partitioning – first indexing ideas

Symmetric design apply to grid-constructed park, but not to beam and grow-based (Voronoi) region partitioning.

We still require some a form of addressing when placing the elements within these regions. We need to find a way to index the edges and corners.

Common functionality

The non-symmetric methods accept a list of points as a parameter, which are the centres of the circles completely within the boundary (or just to say that the centres are of a certain distance from the boundary).

Beam Partitioning (RayCast)

Edge Indexing

  • Edge 0 will be the first edge from the centre (that does not lay on the centre)
    • Which one of the two will be determined by the orientation (default is clockwise).
  • Corner 0 will be the vertex that coincides with the centre region and the  Edge 0.
  • if Centre is non-zero, there will be an Edge that represents the centre boundary


Because symmetry can still be preserved but WITHIN a single region of consideration.

  • Edge indexing starts with 1, and -1 in the other direction (counter-clockwise).
  • Edge 0 exists in case Centre is non-zero (except for the widths of the paths)
  • Similar indexing strategy for vertices.
Adaptable shapes

Further partitioning needs to consider the boundary of the region. Two options are possible:

  • Match the the sides that are not parallel to the boundary/edge that is uses as a reference.
  • Keep the shape, e.g. preserve the angles and scale the are to match the available space.
    • NEW IDEA have a new rule that would fit in the rectangular shape into the available space
Multiple Centres

It should (may?) be possible to have multiple centres in the rule. The problem arises of how to connect the centres with paths, building a walk-graph.

Centres Connection

The rule should be independent of the number of centres and number of corners. Instead we must have some guidance how to build the graph.

Some ideas:

  • Cast the ray to the nearest corner only. OR
    • cast the ray only if the corner is not connected (or inverse cast corner -> centre)
    • cast ray to all corners, without intersecting other paths (HOW??)
  • Have a sub-rule on how to join the centres some options
    1. Leave as it is – completely disconnected
    2. Join in a loop or closed path
    3. A loop without a single edge – a tree; chosen at random
    4. Join pairs of centres
    5. Join opposites – intersections? What if there is an odd number of vertices? How to select two equally weighted opposites?
    6. Completely random?

Grow Region Partitioning

Symmetrical placement is even less applicable to this method because it is much harder to predict the number of edges that the region is going to have.

Counting the index perhaps would not make much sense (why?) Instead the designs should be developed taking into the account the inner and outer edges and vertices.

 Quad Mapping

Although the subregion may have more then four corners, it is often necessary to map a region to a quad.


  • Non-convex beam paritioning – remove paths that are casted to the outside area
  • More formal specifications for terms
    • opposite centres in the sides
    • delauney triangulation – connects into a graph
    • planar graph – must be plannar