Voronoi - Plotting Vertices

CalxDesign

Hi all,

I've been experimenting the Voronoi Diagrams, and the Manhattan Distance function and ended up with some interesting results. My current (simple) code is below. I have an array of vectors, an array of colours. Each pixel on the screen is set to the colour at the index of the closest vector.

I'm now at the point where I would like to plot some geometry - I would like to use vertices to create the pattern from polygons, but I'm stuck, and at a loss as to how to achieve it. A lot of the reading on Voronoi is a on the heavy side, and what I'm after is really a simple explanation of the process.

Would anyone be kind enough to point me in roughly the right direction for this?

Thanks for your time,

Dave

size(800, 800);
colorMode(HSB, 100);

int numSites = 20;
boolean manhattan = true;

PVector[] sites = new PVector[numSites];
color[] colors = new color[numSites];

for (int i = 0; i < numSites; i++) 
{
    colors[i] = color(random(100), 60, 100);
    sites[i] = new PVector(random(width), random(width));
}

for (int x = 0; x < width; x++) 
{
    for (int y = 0; y < height; y++) 
    {
        float minDistance = Float.MAX_VALUE;
        int closestIndex = 0;

        for (int i = 0; i < numSites; i++) 
        {
            float distance = manhattan ? abs(sites[i].x - x) + abs(sites[i].y - y) : dist(x, y, sites[i].x, sites[i].y);

            if (distance < minDistance) {
                closestIndex = i;
                minDistance = distance;
            }
        }
        set(x, y, colors[closestIndex]);
    }
}

for (int i = 0; i < numSites; i++) {
    ellipse(sites[i].x, sites[i].y, 5, 5);
}

amnon

There are different options. Getting voronoi vertices directly instead of an image. Using blob detection (libraries) on the image. Using custom code to find the vertices from the image you got. Don't know which route appeals most to you...

CalxDesign

I think what appeals to me most is the "right" way to do it from the perspective of creating geometry - I'm in absolutely no way tied to this code. Just a simple explanation along the lines of:

1. Start Shape
2. Loop through a
3. Check for a certain condition
4. Do something else.
5. Place vertex
6. Close Shape

This would be reallly useful, what I'm struggling with is that often the descriptions of the process and the underlying algorithm look like this:

Thanks, appreciate the help!

Dave

colouredmirrorball

Don't be scared of the math. It's not entirely unlike code after all. Granted, it's not easy to read when you're not used to it, but so is Processing code. The only way is practice.

This is my interpretation. Rk equals the set of all vectors x, where the distance between x and Pk is smaller than the distance between x and all other P's. Rk is the set of all points belonging to one region around point Pk.

CalxDesign

That's helpful thanks. I've just found this post too, so I'm well on my way.

amnon

Are you tied to Manhattan voronoi?

If not, there are also a few libraries (Mesh, Toxiclibs) that can generate voronoi polygons.

CalxDesign

No, absolutely not. I've looked at Toxi's class and Mesh. What I'm after here is an understanding of the subject, not an implementation.

Thanks

Dave

amnon

All right, here are a few resources that may be useful:

• http://765.blogspot.nl/2009/09/how-to-draw-voronoi-diagram.html
• http://blog.ivank.net/fortunes-algorithm-and-implementation.html
• http://blog.alexbeutel.com/332/interactive-voronoi-diagrams-with-webgl/
• http://www.cs.princeton.edu/~edwardz/voronoi/voronoi.html
• http://www.raymondhill.net/voronoi/rhill-voronoi.html

CalxDesign

Some great resources there - thanks Amnon.