Generating Random Voronoi Diagrams

Voevudko A. E., Ph.D.

Rate me:

4.41/5 (11 votes)

3 Jun 2017CPOL7 min read

19.4K

Generating and plotting random Voronoi Diagrams and offering web-page supporting it and R scripts.

Download full project source - 3 Kb

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.

JavaScript

function Metric(x,y) {return (x*x + y*y)}
// Generating and plotting Voronoi diagram (simple version).
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;
  // Arrays for 7 predefined sites (located on canvas) and colors
  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);
  // Plotting sites and applying linked color.
  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;}
      }//fend i
      ctx.fillStyle=C[j]; ctx.fillRect(x,y,1,1);
    }//fend x
  }//fend y
  // Plotting site points (in black). Note: these 7 lines were added later! LOL
  // Also, there was no title, h3 and comment tags. No JS comments too. Only 21 lines.
  // I've re-formatted it later to look like now (and match prime page code).
  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:

JavaScript

// Helper Functions
// HF#1 Like in PARI/GP: return random number 0..max-1
function randgp(max) {return Math.floor(Math.random()*max)}
// HF#2 Random hex color returned as "#RRGGBB"
function randhclr() {
  return "#"+
  ("00"+randgp(256).toString(16)).slice(-2)+
  ("00"+randgp(256).toString(16)).slice(-2)+
  ("00"+randgp(256).toString(16)).slice(-2)
}
// HF#3 Return the value of a metric: Euclidean, Manhattan or Minkovski
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))}
}
// Generating and plotting Voronoi diagram.
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;
  // Building 3 arrays for requested n random sites (located on canvas)
  // and linked to them random colors.
  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();
  }
  // Plotting sites and applying selected mt metric and linked colors.
  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;}
      }//fend i
      ctx.fillStyle=C[j]; ctx.fillRect(x,y,1,1);
    }//fend x
  }//fend y
  // Plotting site points (in black).
  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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Voevudko A. E., Ph.D.

Architect

United States

I've started programming in a machine code and an assembly language for IBM 370 mainframe, and later programmed in many other languages, including, of course, C/C++/C# and ASP/ASP.net/VB.net.

I've created many system automation tools and websites for companies and universities.
In addition, I've always been a scientist interested in Computer Science, NT, AI, etc.

Now I'm using mainly scripting languages for NT small problems and computer graphics.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.