Voronoi Cell Details.
Because Voronoi Diagram spans the whole plane, the outer cells are semi-open. In such cells one edge is missing and two edges are semi-infinite – they are actually rays. To visualise a VD semi-infinite ‘ray’ edges need to be clipped to a reasonable (but large!) length. In fact implementation does not store this ray edge – such needs to be constructed when discrete geometry is created. For such ray only one vertex is known, so to form a finite edge the other vertex needs to be computed. Boost Polygon Tutorial on Voronoi Diagram describes how this is done and the layout generator uses some of the code from voronoi_visualizer.cpp. In this code the second vertex for a ‘ray’ edge is chosen as the midpoint between the current and the adjacent cell centres – edge is shared between these two.
Cell polygon can be constructed by taking vertices of the edges. Ray edge one ‘virtual’ vertex does not have an adjacent edge, so instead of taking say the first vertex (or second) all vertices could be taken. This certainly results in duplicates for inner edges and duplicates are to be removed subsequently. This is the first method used. The second method simply takes the first vertex, virtual or not, everywhere except for a ray edge where the second vertex is also virtual – in such case both vertices are used as shown on the picture.Every second vertex is in grey square. Because there is no edge between two ray edges – where the cross is, first vertex of one of the ray edges is taken – the one within a red square.
Voronoi cells are shrunk to form park quarters. The remaining space taken by paths and junctions. VD data structures use Counter-Clockwise (CCW) orientation while where as most operations are performed on boost::geometry polygon data types where vertices are stored clockwise (CW). A mapping between the two is created.
Before Cells are shrunk, a VD vertex is shared by neighbouring cells. The shrunk cells each have shifted version of the same vertex [TODO picture], which are kept track of by a vertex id. Implementation stores shifted vertices under the entry indexed by vertex id. Since VD vertex has three neighbour cells [NOTE is it possible a 4-junction in VD? maybe in an artificial case?] hence junctions are triangles , we do not need to even worry about the order, just clockwise orientation. If the vertex is merged vertex mapping looks up the vertex that is shared with other junctions. In such case path segment is missing and junctions will share an edge.
A path consists of two offset parts of the mirrored edges. Edge id is also know during iteration and hashed against the position within a cell/quarter polygon.
Two twin edges that are shrunk form a path segment. When vertices are tracked it is possible to smooth quarters and still preserve topology of path segments. In this case segment still based on the same but shifted VD segments, but more vertices which approximate a curve may be inserted in between two VD vertices of the given edge.
Naive Shrinking A0 (Algorithm 0)
- Go through every edge and offset it by a certain a given amount t along the (inner) normal.
- Intersect each pair of edges – intersections form the new polygon.
Our implementation also extends each edge – to handle concave polygon (with a reasonable angle of incidence).
The problem with naive approach is that topology may change, where the an edge may collapse, or for concave angles vertex may split into two, also summerised by Cacciola. These are called edge event and split events respectively. We want for polygons collapse a if each edge were set on fire, hence the Grassfire Transform. The reduction method is called Mittered-offset.
In the case of VD cells all polygons are convex (because of the intersection of half-spaces) so only edge events need to be handled. After we shrink a polygon with distance t from the boundary a number of edges might have collapsed, meaning a number of vertices might have merged into one (see second picture below). It is necessary to track which edges have collapsed – means no path segments for them, and which vertices are merged – vertex sharing for junctions.
A1 is based on naive shrinking.
- Shrink Polygon naively (A0).
Since this may create spurious geometry outside of the actual Grassfire polygon there might be some intersections with non-neighbouring edges.
- Find non-neighbour intersections per edge.
Find any additional intersections that trigger and edge event. To avoid neighbour intersection we shrink an edge by a small amount (Epsilon value) from both sides. We manually discard self-intersections. boost::geometry r-tree is used which operates which only allow to intersect a segment with an edge, we manually weed out edges within the AABB by intersecting the with each potential segment individually.
- Merge neighbour and non-neighbour intersections,
storing their edge id pairs.
- Filter out spurious geometry.
Intersections or vertices that inside the ‘buffer’, a polygon with hole are discarded. Buffer polygon the result of the union of extruded edges.
- Create vertex and edge mappings.
A client should be ignorant to which edges were removed (vertices merged), or whether the direction is clockwise.
- Use mappings to create correct junctions and path segments.
Smoothing based on Logical Edges have been added. LE topology is preserved as can be seen on the second picture under Junctions subsection. At the moment only for inner cells (and respective path segments that are affected), since outer cells are quite large before they are clipped to iregion. After smoothing a shape shrinks so much – relative to the much smaller inner cells, that they leave the iregion.