Voronoi relaxation (Lloyd’s algorithm) in Processing

How to implement a basic Voronoi relaxation (Lloyd’s algorithm) in Processing in few simple steps

 

I stumbled upon this algorithm while researching for another project, I am not sure yet for what I will use it, anyway it’s nice and neat, so here it is.

The goal of the Voronoi relaxation algorithm is to obtain an even distribution of previously provided points. To achieve this, the steps of the algorithm, as described from the Wikipedia page, are:

Lloyd’s algorithm starts by an initial placement of some number k of point sites in the input domain. […]It then repeatedly executes the following relaxation step:

• The Voronoi diagram of the k sites is computed.
• Each cell of the Voronoi diagram is integrated, and the centroid is computed.
• Each site is then moved to the centroid of its Voronoi cell.

Quite straightforward, let’s see the implementation. To get the Voronoi diagram we will use the famous Processing library Toxiclibs, so make sure to have it on your machine and to import it on your Processing sketch. We will also need the Java List interface.

import java.util.List;

import toxi.geom.*;
import toxi.geom.mesh2d.Voronoi;

Let’s create, as a global variable, the List of points that we are going to relax.

List<Vec2D> points;

Now we initialize them in setup().

void setup() {
  size(800, 600);

  noFill();

  points = new ArrayList<Vec2D>();

  int n_points = 50;

  for (int i=0; i<n_points; i++) {
    points.add( new Vec2D(random(width), random(height)));
  }
}

Now we will relax the points. First we create a Voronoi object, as per documentation, and we add all the points of our List to it. From the Voronoi object we can use the getRegions() method to get the cells of our Voronoi diagram. For all the regions we can now get the centroids with getCentroid() which will be the new positions of our points. We repeat the process at each iteration of draw().

There is still a problem to address: since the exterior regions of the Voronoi diagram are huge they will lead to unexpected behaviors and crashes when we use their centroids as new points’ locations. What we need to do is to clip them, so that they don’t go out of the boundaries of the screen. Luckily Toxiclibs has an easy class for this, the SutherlandHodgemanClipper clipper.

Here’s the code for the Voronoi relaxation:

Voronoi voronoi = new Voronoi();

voronoi.addPoints(points);

Rect bound_rect = new Rect(0, 0, width, height);

SutherlandHodgemanClipper clipper = new SutherlandHodgemanClipper(bound_rect);

List<Polygon2D> regions = voronoi.getRegions();

for (int i=0; i<regions.size(); i++) {
  regions.set(i, clipper.clipPolygon(regions.get(i)));
  Vec2D centroid = regions.get(i).getCentroid();
  points.set(i, centroid);
}

Finally, few simple drawing functions for drawing points and polygons and we are done 😉

void drawPoints(List<Vec2D> pts) {
  for (Vec2D p : pts)
    ellipse(p.x, p.y, 2, 2);
}

void drawPolygons(List<Polygon2D> ps) {
  for (Polygon2D p : ps)
    drawPolygon(p);
}

void drawPolygon(Polygon2D p) {
  beginShape();
  for (Vec2D v : p.vertices)
    vertex(v.x, v.y);
  endShape(CLOSE);
}

Here’s the whole code, also on GitHub, enjoy.

import java.util.List;

import toxi.geom.*;
import toxi.geom.mesh2d.Voronoi;

List<Vec2D> points;

void setup() {
  size(800, 600);

  noFill();

  points = new ArrayList<Vec2D>();

  int n_points = 50;

  for (int i=0; i<n_points; i++) {
    points.add( new Vec2D(random(width), random(height)));
  }
}

void draw() {
  background(255);

  Voronoi voronoi = new Voronoi();

  voronoi.addPoints(points);

  Rect bound_rect = new Rect(0, 0, width, height);

  SutherlandHodgemanClipper clipper = new SutherlandHodgemanClipper(bound_rect);

  List<Polygon2D> regions = voronoi.getRegions();

  for (int i=0; i<regions.size(); i++) {
    regions.set(i, clipper.clipPolygon(regions.get(i)));
    Vec2D centroid = regions.get(i).getCentroid();
    points.set(i, centroid);
  }

  drawPoints(points);

  drawPolygons(regions);
}

void drawPoints(List<Vec2D> pts) {
  for (Vec2D p : pts)
    ellipse(p.x, p.y, 2, 2);
}

void drawPolygons(List<Polygon2D> ps) {
  for (Polygon2D p : ps)
    drawPolygon(p);
}

void drawPolygon(Polygon2D p) {
  beginShape();
  for (Vec2D v : p.vertices)
    vertex(v.x, v.y);
  endShape(CLOSE);
}

void mousePressed() {
  points.add(new Vec2D(mouseX, mouseY));
}

void mouseDragged() {
  points.add(new Vec2D(mouseX, mouseY));
}

 

---