To compute FF layout fist we create park ‘quarters’ which are non-walkable. Because paths are computed from quarters, simply subtracting them from the polygon will result in a polygon with holes (see middle image below). To break loops we have to partition paths. There are few ways to acomplish this, for instance just one edge splitting the polygon loop would be sufficient, or the method described earlier that works better with the boost geometry library. However to be consistent it was decided to adopt similar structure to that of Grid rule where all paths are split into separate path centres from path sections.
The centres were generated from a list of shifted vertices around each voronoi cell vertex. Shifted vertices were collected from each cell and stored in a map under a key of unshifted or voronoi vertex (for instance stored in std::map<point, std::vector<point>>). Cells are could be accessed in no particular order, for instance simply iterating over the cell container, and eventually each vertex would have received all shifted vertices within the neighbouring cells. Because search for the cell vertex is logarithmic the operation is expected to be of nlog(n) complexity.
In theory it would be only sufficient to compute centres and (picture 4) and subtract them from the paths with holes (or what is left after subtracting quarters, picture 3) from the iregion (picture 1) to create separate path sections. Alternatively we could subtract a union of centres and quarters:
iregion – (centres + cells)
However neither methods yield correct results with boost geometry, for instance as we can see of the second method in the last picture (the three paths sections in the lower left corner were generated).
The previous process has failed because perhaps the algorithm was forced to work on non-manifold data (punctures). Instead trying point-edge operations (non-manifold) we separately create path sections which result in edge-edge operations with both centre and cell/quarter polygons.
Boost polygon provides half-edge data structures which was taken advantage of. Procedure as follows:
- Shrink each quarter of the cell
- Each shifted edge (of the shrunk quarter) is paired with the twin edge to create a path section.
- For each original vertex – shifted vertices are also stored as well which are used to create a path centre.
It is important to note that come cells were open, e.g. with infinite edges. However we have already used an existing solution described in boost polygon documentation.
Shifted edges were created using normal-direction offset and subsequent intersection. To make certain intersection occurs edge was extended at both ends. It was also made sure only adjacent edges (those that share a vertex) were intersected – without such test intersections of the infinite edges which are adjacent in the data structures but not adjacent geometrically have been occurring at the other end. Shifted edges were computed per cell. To create a path section each a shifted edge had to be paired up with the twin variant and only once. To obtain the shifted twin we get list of shifted edges for appropriate neighbour and then the index of the twin within that list. The index is obtained from edge_id – > local_edge_id hash which was implemented as an array.
Shifted vertices were collected from the first vertex of each edge. Unlike the previous methods an array is used instead of the map to group around the ‘unshifted’ vertex.
The whole operation should be of n complexity (linear) because a linear access for all adjacent elements within half-edge based data structures. Boost polygon does allow to store a colour with each element – it was used to store container indices of each element.