Weighted Voronoi? Different distance algorithms?

[mbostock]

Related d3/d3#2401. For example: Manhattan, Chebychev, and Minovsky.

[BBischof]

I'd also like to echo the request for support for Weighted(additive and multiplicative) Vornoi.

[Fil]

Seems that the reference algorithm can handle weights
https://en.wikipedia.org/wiki/Fortune%27s_algorithm#Weighted_sites_and_disks

[jarmstrong2]

Would also like weighted support if possible! Thanks!

[Fil]

If we could include geoDistance() in the pack then it would help solve Fil/d3-geo-voronoi#1 too!

[nitaku]

@mbostock Any pointers on which parts of the code are involved? I'm also interested in having custom distance functions.

[mbostock]

@nitaku No pointers, sorry. If I knew how to do this I would have done it already.

[jarmstrong2]

Mike, what is the original algorithm for d3's voronoi based on? If it is in fact Fortune's algo, there is a weighted variant available.

[mbostock]

Yes, as @Fil mentioned. This library is an adaptation of gorhill/Javascript-Voronoi, which is an implementation of Fortune’s algorithm.

[aubergene]

I'd love to see these additions. A while ago @jasondavies made an example weighted voronoi power diagram, he's since replaced it with an image. I think it was written with an older version of d3 which I didn't use Fortune's algorithm

[nitaku]

Maybe @gorhill could help us to understand which parts of the implemented algorithm are involved. I had a look at his github, but I was unable to identify the code about distance metrics.

[Kcnarf]

I've found an interesting bl.ock implementing a Weighted Voronoï algorithm in order to produce a Voronoï Treemap : https://bl.ocks.org/mkedwards/759e719eefe36cf9c8ab.

I guess the algorithm uses a 'power distance' as the tessellation uses straight lines. Also, I've not yet been able to identify the underlying algorithm, nor if it is a port from another language.

Nevertheless, it could be a good starting point.

[jarmstrong2]

Looks promising, will look into it. Thanks!

[mbostock]

FYI, that bl.ock has no license. It looks like it is based on this: https://cse512-14w.github.io/fp-plvines-djpeter/

Here are two GPL’d libraries for Java:

https://github.com/ArlindNocaj/Voronoi-Treemap-Library
https://github.com/ArlindNocaj/power-voronoi-diagram

And the related paper:

https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/NoBr12a.pdf

[mhebrard]

I am not sure about the relation between the previous citations, but found another article (with algorithmic)
Balzer et al

[Kcnarf]

Also, I found an interesting article called An efficient algorithm for construction of the power diagram from the Voronoi diagram in the plane presenting an alternative approach. Instead of computing a new power diagram from sites, it reuses an existing basic Voronoï diagram and modifies the cells' borders regarding the weights of each site.

[zbryikt]

hey, a year ago I implemented the weighted voronoi treemap, with MIT License:
https://github.com/zbryikt/voronoijs

it's adopted in PlotDB with d3js for quick customization, which is also my project:
https://plotdb.com/chart/1017/

voronoijs is in vanillajs, but not sure if it's possible to be integrated.

the algorithm is based on following papers:

• "An efficient algorithm for construction of the power diagram from the Voronoi diagram in the plane" ( Marina Gavrilova and Jon Rokne, the one @Kcnarf mentioned. )
• "Voronoi Treemaps" ( Michael Balzer and Oliver Deussen )
• "Applications of Random Sampling in Computational Geometry, II" ( Kenneth L. Clarkson and Peter W. Shor )

[SSCodeChamp]

Hey ,how can I draw voronoi by size/area of each cell instead of sites ?

[Fil]

@zbryikt very impressive! Do you need help integrating it as a d3 plugin? It would certainly be very enjoyable, and useful.

Ideally d3-voronoi-weighted or d3-power-diagram would share the same API as d3-voronoi, with defaults of equal weights so that maybe it could be used as a drop-in replacement, and compared for performance, features etc.

If I'm understanding this correctly, your script offers both the computation of the power diagram (which would be the equivalent of d3-voronoi's Diagram) and of a treemap layout based on it (which looks like "voronoi relaxation"). One of them (I'm not sure which?) is based on an extent defined by an ellipsoid (n-polygon), where d3-voronoi has a rectangle extent. So even with equal weights it would add an interesting feature. (Is it possible to use other types of polygons for the extent?)

[Kcnarf]

@Fil
I'm working on the subject too when I found time to do so, cf. block which works with D3v4. Perhaps it's a good starting point because it already works with d3v4.

I reuse a code from here (https://bl.ocks.org/mkedwards/759e719eefe36cf9c8ab), which computes a treemap and seems to use the same algorithm than the one used by @zbryikt (@zbryikt, can you confirm?).

The code now focuses on computing the power diagram. I remove treemap generation 'cause I think it is another subject. It contains 3 files :

• PowerDiagram.js, which is main API computing the weighted voronoi
• ConvexHull.js, which computes 3D-convexHull
• d3-polygon-clip.js (feature in d3v3 no longer in d3v4)

@Fil, regarding your question with the extent, I guess it could be any convex, hole-free polygon. furthermore, this feature may be added to the current d3-voronoi: once computed, each cell have to be clipped by the desired polygon (by using the d3-polygon-clip).

[Kcnarf]

I've continued to put some effort in creating a dedicated d3 plugin for weighted Voronoi, and the result is here : d3-weighted-voronoi.

[zbryikt]

@Fil I think it will be great if we make a d3-plugin for voronoijs, but I don't have time to do this currently. Yet I think it won't take too much time to do this...

Voronoijs contains power digram calculation and treemap building by recursively buliding power diagram. the boundary could be arbitrary convex polygon.

@Kcnarf I'm not sure but it looks like we use different algorithms; this is the algorithm I used.

[Kcnarf]

@zbryikt
power diagram is computed in the same way (projection of a 3D convex hull)
I don't know if the relaxation part is the same.

[SSCodeChamp]

@Kcnarf
https://bl.ocks.org/mkedwards/759e719eefe36cf9c8ab - this guy does not compute diagram correctly. If you use this , you will find that not all shapes sizes match with his weight.

[Kcnarf]

@Svmali84
this is bad news ... but I've guessed things were not going very well in this block. Hence ...

When I ported this block to d3v4, I've actually found some bugs. Some were fixed, and others not (cf. Weighted Voronoi Treemap in D3v4).

And when I've reuse part of this code for the d3-weighted-voronoi plugin (which focuses only on weighted voronoi diagram computation, and leaves out treemap/relaxation computation), I put some effort on automated (but simple) tests. I can not prove the code works fine, but I do my best to do so.

Finally, if you have some repeatable failing tests or can point out some bugs in the code, I will put some effort to investigate it.

[SSCodeChamp]

@Kcnarf - Thanks for the reply. I did one small test with the code by writing weight of each cell into it. Through this you can clearly see the issue.

This is what I observed , if you have say 3 cells with weightes as 3,4,5 . Sometimes you see cell 3 bigger than cell 4 etc..

[SSCodeChamp]

@Kcnarf - I tried with different data. Sometimes if we have large data we gets twin is NULL exception. Any idea what is it ?

[Kcnarf]

@Svmali84 - go to https://bl.ocks.org/Kcnarf/15d54f4ccae6a3710cd3029546664eec : it is a port of @mkedward's block to d3V4, with some reworks and fixes (difs are listed in the readme); notably, it drastically reduces the arising of the Cannot set property 'twin' of null error

Furthermore, perhaps that you can use the d3-voronoi-treemap plugin, which provide a packaged solution, and may be simpler to use.

[SSCodeChamp]

Thanks @Kcnarf . This one is working fine with most of the data sets.

So can I make use of it on my website free ? I see it is under GPL-3 license. So putting copyright is sufficient ?

[SSCodeChamp]

Hi,

Can someone let me know if I can use this on the website ? I have very less idea of GPL license

[micahstubbs]

@Svmali84 I imagine that you can use it so long as you do not distribute it. this stackoverflow answer may help 😄 https://stackoverflow.com/a/2281266/1732222

[micahstubbs]

we could also ask @Kcnarf if he would be willing to release d3-voronoi under a more liberal license, like for example the BSD-3-Clause license that d3 itself is released under or the popular MIT license

[Kcnarf]

@Svmali84 - I propose to continue this license-related discussion into the dedicated d3-voronoi-treemap's issue#2