FF Regions 4 – Indexing Propagation Reconsidered

Problems with A1
Range of merged vertices includes boundary (Zero vertex)

Problem arises at the indexing boundary, that is if a merged vertex which source set includes a first vertex (index 0).

Copying LE Indexing

In a smoothed shape it should it should be known which are the original vertices – or the logical vertices, in contrast to the newly created vertices who’s purpose is to approximate the curve in geometry. This mapping is facilitated with LEs. We want this to have a consistent behaviour in subsequent operations and visual similarity (preserved topology) – no matter if smoothing was performed or not.

Vertex mapping options:

  1. Complete – isomorphic mapping, where all of the indices are propagated to the derived shapes
  2. Partial, where some of the indices are propagated. In this case there are missing source shape vertices, and indexing has to be made whole somehow.

In addition Propagation can be

  1. Exact – each indexed vertex in the derived shape exactly matches (has the same coordinates) that of the parent shape. In complete and exact propagation a rule may only insert or modify non-index vertices.
  2. Inexact – either closely laying vertices are used as successors, or some sort of mapping is applied. If we consider the whole smoothing operation – the vertices would have moved – but we can still track and apply appropriate indices to them.

Smoothing has Complete Inexact index propagation, because all of the vertices are kept (except for special cases of concave geometry?), but (depending on the smoothing method) they change their positions.

Clipping index propagation is Partial Exact, because some indexed vertices are discarded, while the remaining ones retain at their position.

Counting Propagation (P1)

First implementation of indexing propagation does not work for a number of cases as the following:


The vertices 3 and 4 need to be found in the source polygon (unclipped) which looks like:


and closup:


Which means there are only 4 vertices in the source and we are trying to fill 3 vertices in the place of two, that is in addition of vertex 1 and 2 we need to need to fit addition vertex – which is impossible or we would have a sequence like 0 1 2 3 3, because the first and the last LE indices have to match that of the unclipped shape as show above. Below is an image of how the indices are stored – array indices correspond to actual geometry indices of the clipped shape and the values are LE indices of the source (unclipped) shape:


The algorithm should replace missing LE indices (represented by -1, NOTE this is a bug in the algorithm; a subsequent fix has been applied and -1 replaced by 0) for new vertices created by the clip operation.

It was decided to abandon this algorithm, however for completeness the description as follows:

  1. Hash source LE corners in rtree. In the case of Voronoi Diagram source is the unclipped polygon and LE corners are vertices stored clockwise (Boost Geometry format).
  2. Interate over target (clipped) polygon vertices and see if a match is found with the source. This results in the array as on the picture above.
  3. Find unknown LEs for the new vertices created from clipping (or other operation). We find first vertex that is defined, e.g. vertex 3 in the picture, and feel all the other vertices up to that with one less e.g. 0, 1, 2. In this example however there would be two zeros at indices 0 and 4 (picture below), which make this approach unsuitable.


Geometric Propagation and Smoothing (P2)

Boundary shapes are clipped to the iregion. The polygon part that is outside of iregion that are clipped away are called outer part and the result of the clipping that remain are inner part.

When smoothing is applied, if the boundary shapes are smoothed after clipping we the whole park layout consists of ‘blobs’ as in the first picture above, whereas the layout on the second picture is more desirable.

If they are smoothed before clipping – the boundary shapes are either missing or, for a large cell – they become very small. The reason is simple – since the outer part is much larger than the inner part, smoothing affects the inner part considerably more in the local scale (that is within the iregion), than the outer part. For this reason it is important to reduce the outer part before smoothing. , but at the same time leave some area outside the iregion to avoid blobs. Rather than preserving geometric detail on the part that is clipped away it turns out it is sufficient to evenly arrange remaining vertices at some distance from the iregion boundary.

Let us take expand the iregion (inverse of grassfire shrink) to create a clipping region. Each shape is clipped as follows.

  1. Find intersections of the cell with the clipping region. There should be two (2) of them or we throw an error (discard or do not smooth the polygon.
  2. Each intersection would belong to a certain edge. One vertex of such edge would be inside the clipping region and the other – outside. The two immediate outside vertices are moved in the place of intersections.
  3. Span a line with two vertices at the intersections. The vertices between these two vertices are evenly distributed along the line segment.

Extended Geometric Propagation (P3)

Two problems with P2:


  1. Line may cut into a large chunk of iregion, even if clipping region is large, part of the smoothed polygon will crawl into the iregion creating a hole.
  2. Paths overlap – vertices are ‘smoothed’ inside too much.

P3 solves these two issues, picture below shows a smoothed layout before clipping.


  1. Discard expanded clipping region, use iregion as clipping region (less work too).
  2. Instead of spawning lines at intersections, extend ‘rays’ from intersection points away from iregion with a reasonable length (currently perimeter / 12). Endpoints of ‘rays’ span the line segment described in above in P2.