This block is a Work In Progress, a continuation of a previous block, and tries to implements a Voronoï map (i.e., one-level treemap) based on the algorithm presented in Computing Voronoi Treemaps - Faster, Simpler, and Resolution-independent, and augmented with heuristics found on a Java implementation done by Arlind Nocaj, one of the co-authors of the scientific paper. Because this algorithm requires the computation of weighted Voronoï, this block uses the d3-weighted-voronoi plugin.
Without going into details (cf. the scientific paper), the overall algorithm doesn’t differs from the one used in the previous block. Hence, at each iteration :
- the weighted voronoi diagram is computed based on each weighted sites
- then, each site is re-position at the center of its influence area
- then, another weighted voronoi diagram is computed based on each weighted relocated sites
- then, each site is re-weighted in order to fit its expected influence area
The algorithm stops when each site is no longer moved or re-weighted (more exactly, when each site is moved or is re-weighted below a certain treshold), or if a certain number of iterations is reached.
Differences from the algorithm used in the previous block are :
- rework the limitation of weights when re-positioning and when re-weighting sites; both handled in function handleOverweigthed, which prevent any site to be overweighted (and hence prevent any site to produce an empty cell)
- heuristics to mitigate near-zero weight (if active, min allowed weight = (max weight / 1000)); near-zero weights are difficult to handle because re-positioning systematically overweighted near-zero sites, making stabilization difficult to reach
- heuristics to mitigate flickering (if active, if area error < 5% of total area, the more the flickering count, the less sites are re-positioned and re-weigted)
Notes :
- only one level, no nested hierarchy
- compared to the previous block, the algorithm used in this block performs better : in term of representativity of initial weights (reaching error below 1% is common, compared to 15%-20% in the previous block), and in term of number of iterations needed to reach the stable state
- experience shows that stabilization is not reached when a lightweighted site is trapped between 2 heavyweighted sites and the edges of the encosing polygon; this is because (i) heavyweighted sites have reached their targeted area and don’t need to be re-positioned or re-weighted by their own, (ii) lightweighted site has much larger area (than the one targeted) but can no longer lowers its weight (it has reached the minimim weight), and (iii) the others sites haven’t enought energy to grow and reach their targeted area (which would push heavyweighedt sites on the lightweighted one)
User interactions :
- you can choose to draw the Weighted Voronoï Diagram (default) or the weights (visualized as circles).
- you can hide/show sites
- you can choose among different rendering (greyscale, radial rainbow, or conical rainbow (default, having hard-&-fun time to implement it because canvas don’t provides conical gradient)).
Acknowledgments to :