Introduction
Voronoi diagram (VD) could be a very colorful geometric figure, and we gonna generate and plot random version of it
both in JavaScript and in R.
According to Wikipedia [1]:
"In mathematics,
a Voronoi diagram is a partitioning of a plane into regions based
on distance to points in a specific subset of the plane. That set of points
(called seeds, sites, or generators) is specified beforehand, and for each seed
there is a corresponding region consisting of all points closer to that seed than
to any other."
You would be surprised how many "real world" and theoretical applications are there [2-4].
In [2] it was stressed that there are "literally hundreds of different algorithms for constructing various types of Voronoi diagrams".
So, let's talk about algorithms in general and applied to generating/plotting of VD in particular.
There are a lot of suggestions, e.g., to use D3.js library in JavaScript [5] or use this or that package in R.
You can find a lot of algorithms realizes in C, C++, C# and VB, and actual samples of code even here, on CP [6-10].
Almost all of them overfilled with math, have a "monster" size of code [6,7], etc. The one in [9] is definitely not simple, and I'm not
sure if the one in [8] is fast. But I know for sure: generating/plotting in JavaScript is faster than in R on my computer, i.e.:
TIP: Speed of generating/plotting depends on the language/tool and on the power of
your computer even for the same algorithm.
In R language, you could be confused totally, because
one of the R's great powers is its unlimited number of packages, virtually thousands of them.
For any applications, big or small, you can find a package. In case of VD there are many packages,
e.g.: deldir, alphahull, dismo, ggplot, ggplot2, tripack, CGAL, etc. Not to mention all linked packages
you need to install too. Do you need random colors? Again, find a few packages more...
In fact, I've found only black-and-white VDs built in JavaScript and R.
I was lucky to find what I need instead of advised tools: The Algorithm.
Here is a long story in short. I was reading description of "the simplest" algorithm in [2], and I've stopped right at the beginning.
I thought: "Interesting, but too time consuming..." After this I stumble at [6,7] and thought: "WOW, it will take too much time even to understand it..." Later I've "scanned" scripts in [5] and have found a small, compact code
in Python. My thoughts: "It looks like it is fake, too simple... It can't work!? Test it!" So, in 5 min I've created the first very simple prototype,
and it worked!
Find a page almost like the initial prototype page in a downloaded source file.
Take a look at this prototype page script code below. This version is even a little bit expanded if compare it with
an initial prototype page.
function Metric(x,y) {return (x*x + y*y)}
function pVoronoiD() {
var cvs=document.getElementById("cvsId");
var ctx=cvs.getContext("2d");
var n=7, w=640, x=y=d=dm=j=0, w1=w-2;
X=[20,30,60,80,100,120,140];
Y=[200,100,300,400,200,400,340];
C=["red","orange","yellow","green","blue","navy","violet"];
ctx.fillStyle="white"; ctx.fillRect(0,0,w,w);
for(y=0; y<w1; y++) {
for(x=0; x<w1; x++) {
dm=w1*w1 + w1*w1; j=-1;
for(var i=0; i<n; i++) {
d=Metric(X[i]-x,Y[i]-y)
if(d<dm) {dm=d; j=i;}
}
ctx.fillStyle=C[j]; ctx.fillRect(x,y,1,1);
}
}
ctx.fillStyle="black";
for(var i=0; i<n; i++) {
ctx.fillRect(X[i],Y[i],3,3);
}
}
All "magic" of VD generation is happening inside triple "for" loop (see above).
In short, it works like following:
- For each point (x,y) within canvas the minimal distance to all "site points" (defined in X and Y arrays)
is calculated.
- A color related to "site point" with a minimal distance is applied to the current canvas point.
- Later, overlapping of colors helps to determine shapes of all sites.
VD generated by this simple script is shown below.
Voronoi diagram shown in the prototype page.
Remember:
TIP: Compact, simple and reliable algorithm is the most important programing advisor for plotting and not only.
Additionally, a few custom helper functions can simplified code, and they can be used for any other applications,
and even can be "translated" to other language, e.g., R language in our case.
Now, VD generation/plotting is available in JavaScript and R producing beautiful colorful diagrams with any reasonable amount of sites.
It means that, in fact, two "VD generators" are available for CP users.
Algorithms realized in JavaScript and R
JavaScript in HTML page
Let's take a closer look at the JavaScript:
function randgp(max) {return Math.floor(Math.random()*max)}
function randhclr() {
return "#"+
("00"+randgp(256).toString(16)).slice(-2)+
("00"+randgp(256).toString(16)).slice(-2)+
("00"+randgp(256).toString(16)).slice(-2)
}
function Metric(x,y,mt) {
if(mt==1) {return Math.sqrt(x*x + y*y)}
if(mt==2) {return Math.abs(x) + Math.abs(y)}
if(mt==3) {return(Math.pow(Math.pow(Math.abs(x),3) + Math.pow(Math.abs(y),3),0.33333))}
}
function pVoronoiD() {
var cvs=document.getElementById("cvsId");
var ctx=cvs.getContext("2d");
var w=cvs.width, h=cvs.height;
var x=y=d=dm=j=0, w1=w-2, h1=h-2;
var n=document.getElementById("sites").value;
var mt=document.getElementById("mt").value;
var X=new Array(n), Y=new Array(n), C=new Array(n);
ctx.fillStyle="white"; ctx.fillRect(0,0,w,h);
for(var i=0; i<n; i++) {
X[i]=randgp(w1); Y[i]=randgp(h1); C[i]=randhclr();
}
for(y=0; y<h1; y++) {
for(x=0; x<w1; x++) {
dm=Metric(h1,w1,mt); j=-1;
for(var i=0; i<n; i++) {
d=Metric(X[i]-x,Y[i]-y,mt)
if(d<dm) {dm=d; j=i;}
}
ctx.fillStyle=C[j]; ctx.fillRect(x,y,1,1);
}
}
ctx.fillStyle="black";
for(var i=0; i<n; i++) {
ctx.fillRect(X[i],Y[i],3,3);
}
}
As you can see, 3 helper functions are very small and self-explanatory. Note: the first two
are from VOE.js described in [6] and used "as is".
Prime generating and plotting function pVoronoiD() has 3 simple steps:
- Building 3 arrays for requested n random sites (defined by points located on canvas)
and linked to them random colors.
- Plotting sites: applying selected mt metric and linked colors.
- Plotting site points (in black) over already plotted sites.
In fact, all prime fragments of the code are the same both here and in the prototype script, e.g., 3 arrays,
triple "for" loop, plotting "site points".
See 4 plotted in JavaScript Voronoi diagrams for yourself in the figure below. Metrics applied are as
following: Euclidean, Manhattan, Minkovski and again Euclidean.
As usually, right-clicking any VD image you can save it as png-file, for example. Original dimensions are 640 x 640 pixels,
i.e. 4.6 times bigger than presented here..
Figure 1 - The first 3 VDs have 20 sites each and last one has 100 sites
R script
Functions in R script look like "twins" of similar JavaScript functions, because
they were "translated" from JavaScript. See for yourself:
## VORDgenerator.R
## Voronoi Diagram Generator
# Helper Functions
## HF#1 Random hex color returned as "#RRGGBB".
randHclr <- function() {
m=255;r=g=b=0;
r <- sample(0:m, 1, replace=TRUE);
g <- sample(0:m, 1, replace=TRUE);
b <- sample(0:m, 1, replace=TRUE);
return(rgb(r,g,b,maxColorValue=m));
}
## HF#2 Return the value of a metric: Euclidean, Manhattan or Minkovski
Metric <- function(x, y, mt) {
if(mt==1) {return(sqrt(x*x + y*y))}
if(mt==2) {return(abs(x) + abs(y))}
if(mt==3) {return((abs(x)^3 + abs(y)^3)^0.33333)}
}
## Generating and plotting Voronoi diagram.
## ns - number of sites, fn - file name, ttl - plot title.
## mt - type of metric: 1 - Euclidean, 2 - Manhattan, 3 - Minkovski.
pVoronoiD <- function(ns, fn="", ttl="",mt=1) {
cat(" *** START VD:", date(), "\n");
if(mt<1||mt>3) {mt=1}; mts=""; if(mt>1) {mts=paste0(", mt - ",mt)};
m=640; i=j=k=m1=m-2; x=y=d=dm=0;
if(fn=="") {pf=paste0("VDR", mt, ns, ".png")} else {pf=paste0(fn, ".png")};
if(ttl=="") {ttl=paste0("Voronoi diagram, sites - ", ns, mts)};
cat(" *** Plot file -", pf, "title:", ttl, "\n");
plot(NA, xlim=c(0,m), ylim=c(0,m), xlab="", ylab="", main=ttl);
# Building 3 arrays for requested n random sites (located on canvas)
# and linked to them random colors.
X=numeric(ns); Y=numeric(ns); C=numeric(ns);
for(i in 1:ns) {
X[i]=sample(0:m1, 1, replace=TRUE);
Y[i]=sample(0:m1, 1, replace=TRUE);
C[i]=randHclr();
}
# Plotting sites and applying selected mt metric and linked colors.
for(i in 0:m1) {
for(j in 0:m1) {
dm=Metric(m1,m1,mt); k=-1;
for(n in 1:ns) {
d=Metric(X[n]-j,Y[n]-i, mt);
if(d<dm) {dm=d; k=n;}
}
clr=C[k]; segments(j, i, j, i, col=clr);
}
}
# Plotting site points (in black).
points(X, Y, pch = 19, col = "black", bg = "white")
dev.copy(png, filename=pf, width=m, height=m);
dev.off(); graphics.off();
cat(" *** END VD:",date(),"\n");
}
## Executing:
#pVoronoiD(10) ## Euclidean metric
#pVoronoiD(10,"","",2) ## Manhattan metric
#pVoronoiD(10,"","",3) ## Minkovski metric
#pVoronoiD(150) ## Euclidean metric
As you can see, all functions in R having the same functionality, the same steps as in JavaScript, because they were adopted
to R native operators and functions. That's it!
See 4 plotted in R Voronoi diagrams for yourself in the figure below.
Figure 2 - The first 3 VDs have 10 sites each and last one has 150 sites
Conclusion
Two Voronoi diagram generators were presented: HTML/JavaScript page and R script, and this is a whole source code for this project.
It should be stressed, that cited in the beginning VD definition from [1] is only the one of many possible, especially if VD is built
to show something like temperature, or water, or even something more abstract.
Also metric could be not related to any distance, but acting as a "love meter" or "mood meter", for example.
Anyway, in many researches randomly selected sites and colors should be not random, but predefined.
Even sequence of "points" could be changed to fit the plotting algorithm. To determine how you should re-arrange sites for proper plotting watch
animation of a plotting process.
If your computer is not a super fast one, you can watch "animation" in "R Graphics" sub-window of the "RGui" window.
It means that scripts should be modified.
Fortunately, these scripts are small and clear, so, it won't be difficult to modify them.
Note: "real world" or theoretical applications are out of scope of this article.
Presented algorithm is reliable for sure, just because it works already in 7 languages [5].
another question would be reasonable: "Does it fit your application task?"
To find the answer: implement it in your language and test it! There is no other way.
Finally, using "VD Generators" as a template, any person can start any kind of research suitable for
demonstrating results as a colorful Voronoi diagram.
References
- Voronoi diagram, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Voronoi_diagram.
- Drysdale D. Voronoi Diagrams: Applications from Archaology to Zoology. (1993), Regional Geometry Institute, Smith College. URL: http://www.ics.uci.edu/~eppstein/gina/scot.drysdale.html.
- Snow, J. On the Mode of Communication of Cholera. (1855), London: John Churchill. URL: http://www.ph.ucla.edu/epi/snow/snowbook.html.
- Voronoi, G. Nouvelles applications des paramètres continus à la théorie des formes quadratiques.. (1907), J. reine angew. Math. 133, 97-178.
- Voronoi diagram, Rosetta Code Wiki, URL: http://rosettacode.org/wiki/Voronoi_diagram.
- Haugland. K. Create a Voronoi diagram 1 of 2. (2012), Code Project, URL: https://www.codeproject.com/Articles/411242/Create-a-Voronoi-diagram-of.
- Haugland. K. Create a Voronoi diagram 2 of 3. (2012), Code Project, URL: https://www.codeproject.com/Articles/413452/Create-a-Voronoi-diagram-of.
- Joukhadar, B. Fast Voronoi Diagram in C#. (2014), Code Project, URL: https://www.codeproject.com/Tips/797123/Fast-Voronoi-Diagram-in-Csharp.
- Stadnik, V. Simple approach to Voronoi diagrams. (2015), Code Project, URL: https://www.codeproject.com/Articles/882739/Simple-approach-to-Voronoi-diagrams.
- BenDi. Fortune's Voronoi algorithm implemented in C#. (2015), Code Project, URL: https://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C.
- Voevudko, A.E. Generating Kronecker Product Based Fractals. (2017), Code Project, URL: https://www.codeproject.com/Articles/1189288/Generating-Kronecker-Product-Based-Fractals.
