Mesh - voronoi with manhattan distance?

sylvanite

Mesh - voronoi with manhattan distance?

in Contributed Library Questions • 6 months ago

First-time poster, sorry if this is in the wrong place.
I've been experimenting a little bit with Lee Byron's Mesh library and Voronoi diagrams.
I'm curious about the best way to do what's been calculated on the Wikipedia page for voronoi - calculating the Voronoi spaces with Manhattan Distances - and if I can use the library and modify the data after I get it, or if I should try and just implement the formula they have presented without using the library... Any help is greatly appreciated, and thank you in advance!
-Nate

Replies(1)

amnon.owed

Re: Mesh - voronoi with manhattan distance?

6 months ago

The Mesh library gives the regular voronoi and delauney shapes. Coincidentally I stumbled upon Manhattan voronoi when aiming for regular voronoi. Note that my goal was implementation in a fragment shader, so my research sketch was floodfill pixel-based. To see the algorithmic process you can move the floodfill (line 35) to the draw() loop instead of within the while loop.

Code Example

PImage img;
int numPixels = 25;
color transparent = color(0, 0);
ArrayList <PVector> points = new ArrayList <PVector> ();
void setup() {
size(500, 500);
noStroke();
resetImage();
}
void draw() {
background(200);
image(img, 0, 0);
for (PVector p : points) {
rect(p.x, p.y, 3, 3);
}
}
void mousePressed() {
resetImage();
}
void resetImage() {
img = createImage(width, height, ARGB);
points.clear();
for (int i=0; i<numPixels; i++) {
int x = (int) random(img.width);
int y = (int) random(img.height);
int index = x + y *img.width;
img.pixels[index] = color(random(255), random(255), random(255));
points.add(new PVector(x, y));
}
while (numTransparentPixels (img)>0) {
img = floodfill(img);
}
}
PImage floodfill(PImage input) {
PImage output = createImage(input.width, input.height, ARGB);
for (int y=0; y<input.height; y++) {
for (int x=0; x<input.width; x++) {
int index = x + y * input.width;
color c = input.pixels[index];
if (c==transparent) {
output.pixels[index] = getColor(input, x, y);
} else {
output.pixels[index] = c;
}
}
}
return output;
}
color getColor(PImage input, int x, int y) {
int indexLeft = max(0, (x-1)) + y * input.width;
int indexRight = min((x+1), width-1) + y * input.width;
int indexUp = x + max(0, (y-1)) * input.width;
int indexDown = x + min((y+1), height-1) * input.width;
color colorLeft = input.pixels[indexLeft];
color colorRight = input.pixels[indexRight];
color colorUp = input.pixels[indexUp];
color colorDown = input.pixels[indexDown];
if (colorLeft!=transparent) { return colorLeft; }
else if (colorRight!=transparent) { return colorRight; }
else if (colorUp!=transparent) { return colorUp; }
else if (colorDown!=transparent) { return colorDown; }
else { return transparent; }
}
int numTransparentPixels(PImage input) {
int np = 0;
for (color p : input.pixels) {
if (p==transparent) np++;
}
return np;
}

Top Reply