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)