How to use the Toxiclibs Voronoi class?

toxmeister

Re: How to use the Toxiclibs Voronoi class?

2 years ago

This part of the library is still not very well integrated and/or documented, but below is a demo which will be bundled with the next release (forgot to add it to the last one). The process is quite easy: You create a Voronoi instance and add points to it. Then you can query it to retrieve polygons (" regions"), the Delaunay triangles or the original given points ("sites")...

The demo also shows how to use the PolygonClipper2D interface to constrain polygons to a given rectangle, something quite useful for voronoi shapes should you plan to fabricate them somehow...

/**
* This demo shows the basic usage pattern of the Voronoi class in combination with
* the SutherlandHodgeman polygon clipper to constrain the resulting shapes.
*
* Usage:
* mouse click: add point to voronoi
* p: toggle points
* t: toggle triangles
* x: clear all
* r: add random
* c: toggle clipping
* h: toggle help display
* space: save frame
*
* Voronoi class ported from original code by L. Paul Chew
*/
/*
* Copyright (c) 2010 Karsten Schmidt
*
* This demo & library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* http://creativecommons.org/licenses/LGPL/2.1/
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.util.*;
import toxi.util.datatypes.*;
import toxi.processing.*;
// ranges for x/y positions of points
FloatRange xpos, ypos;
// helper class for rendering
ToxiclibsSupport gfx;
// empty voronoi mesh container
Voronoi voronoi = new Voronoi();
// optional polygon clipper
PolygonClipper2D clip;
// switches
boolean doShowPoints = true;
boolean doShowDelaunay;
boolean doShowHelp=true;
boolean doClip;
boolean doSave;
void setup() {
size(600, 600);
smooth();
// focus x positions around horizontal center (w/ 33% standard deviation)
xpos=new BiasedFloatRange(0, width, width/2, 0.333f);
// focus y positions around bottom (w/ 50% standard deviation)
ypos=new BiasedFloatRange(0, height, height, 0.5f);
// setup clipper with centered rectangle
clip=new SutherlandHodgemanClipper(new Rect(width*0.125, height*0.125, width*0.75, height*0.75));
gfx = new ToxiclibsSupport(this);
textFont(createFont("SansSerif", 10));
}
void draw() {
background(255);
stroke(0);
noFill();
// draw all voronoi polygons, clip them if needed...
for (Polygon2D poly : voronoi.getRegions()) {
if (doClip) {
gfx.polygon2D(clip.clipPolygon(poly));
}
else {
gfx.polygon2D(poly);
}
}
// draw delaunay triangulation
if (doShowDelaunay) {
stroke(0, 0, 255, 50);
beginShape(TRIANGLES);
for (Triangle2D t : voronoi.getTriangles()) {
gfx.triangle(t, false);
}
endShape();
}
// draw original points added to voronoi
if (doShowPoints) {
fill(255, 0, 255);
noStroke();
for (Vec2D c : voronoi.getSites()) {
ellipse(c.x, c.y, 5, 5);
}
}
if (doSave) {
saveFrame("voronoi-" + DateUtils.timeStamp() + ".png");
doSave = false;
}
if (doShowHelp) {
fill(255, 0, 0);
text("p: toggle points", 20, 20);
text("t: toggle triangles", 20, 40);
text("x: clear all", 20, 60);
text("r: add random", 20, 80);
text("c: toggle clipping", 20, 100);
text("h: toggle help display", 20, 120);
text("space: save frame", 20, 140);
}
}
void keyPressed() {
switch(key) {
case ' ':
doSave = true;
break;
case 't':
doShowDelaunay = !doShowDelaunay;
break;
case 'x':
voronoi = new Voronoi();
break;
case 'p':
doShowPoints = !doShowPoints;
break;
case 'c':
doClip=!doClip;
break;
case 'h':
doShowHelp=!doShowHelp;
break;
case 'r':
for (int i = 0; i < 10; i++) {
voronoi.addPoint(new Vec2D(xpos.pickRandom(), ypos.pickRandom()));
}
break;
}
}
void mousePressed() {
voronoi.addPoint(new Vec2D(mouseX, mouseY));
}

http://postspectacular.com | http://toxiclibs.org

nardove

Re: How to use the Toxiclibs Voronoi class?

2 years ago

Awesome! thanks a lot

cedrickie..

Re: How to use the Toxiclibs Voronoi class?

2 years ago

ah perfect, didnt know there is a voronoi class. good to know

alphachap

Re: How to use the Toxiclibs Voronoi class?

2 years ago

But the Mesh Library Voronoi has serious problems.

It doesn't work properly as it is.

In particular, the getLinked( int index ) give incorrect result.

http://forum.processing.org/topic/strange-mesh-library-voronoi-issue

PhiLho

Re: Re: How to use the Toxiclibs Voronoi class?

2 years ago

If I am not mistaken, that's a different library.

cedrickie..

Re: How to use the Toxiclibs Voronoi class?

2 years ago

he seems to talk about lee byrons mesh library http://www.leebyron.com/else/mesh/
so thats why i welcomed a toxi version as alternative

PhiLho

Re: Re: How to use the Toxiclibs Voronoi class?

2 years ago

Yes, but the chap reports an error not belonging to this thread...

nardove

Re: How to use the Toxiclibs Voronoi class?

2 years ago

@toxi will it be possible to provide an example of moving points and using only DelaunayTriangulation? like they do here http://wiki.processing.org/w/Triangulation

Thanks

- rS

toxmeister

Re: Re: How to use the Toxiclibs Voronoi class?

2 years ago

(almost) certainly :) As I said these classes are not yet fully up to scratch and there's actually still a visibility issue with one of the Delaunay classes, so for now you'll have to stick with Voronoi as a "frontend" to the triangulation. Doing this also has the benefit of working with Vec2Ds instead of the more complex (and still less userfriendly) DelaunayVertex. Moving points is not part of the plan either. The best is to keep all points in a separate list and then recalculate the triangulation from scratch each time a point has been moved... The example below is based on the one above, but only kept the interesting bits...

import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.util.*;
import toxi.util.datatypes.*;
import toxi.processing.*;
// radius of the root triangle which encompasses (MUST) all other points
float DSIZE = 10000;
// a Voronoi diagram relies on a Delaunay triangulation behind the scenes
// we simply use this as a front end
Voronoi voronoi;
ToxiclibsSupport gfx;
// render switch
boolean doIgnoreRoot=true;
void setup() {
size(600, 600);
smooth();
voronoi = new Voronoi(DSIZE);
gfx = new ToxiclibsSupport(this);
}
void draw() {
background(255);
stroke(0);
noFill();
stroke(0, 0, 255, 50);
beginShape(TRIANGLES);
// get the delaunay triangles
for (Triangle2D t : voronoi.getTriangles()) {
// ignore any triangles which share a vertex with the initial root triangle
if (!doIgnoreRoot || (abs(t.a.x)!=DSIZE && abs(t.a.y)!=DSIZE)) {
gfx.triangle(t, false);
}
}
endShape();
fill(255, 0, 255);
noStroke();
for (Vec2D c : voronoi.getSites()) {
ellipse(c.x, c.y, 5, 5);
}
}
void mousePressed() {
voronoi.addPoint(new Vec2D(mouseX, mouseY));
}
void keyPressed() {
doIgnoreRoot=!doIgnoreRoot;
}

http://postspectacular.com | http://toxiclibs.org

nardove

Re: How to use the Toxiclibs Voronoi class?

2 years ago

This is one of the reasons I love toxiclibs, the support, Nice! I have enough to play with so I will leave this topic alone and wait for the next release!

Just checking, is this the best approach to get the moving points?

void draw() {
// calculate new points positions
voronoi = null;
voronoi = new Voronoi(DSIZE);
voronoi.addPoints( points );
...
}

This approach does works for me, but I wonder if this will impact the performance, can we have a clear or removePoints method? but if moving points is not in the plan I understand

Cheers

- rS

aufsess

Re: How to use the Toxiclibs Voronoi class?

2 years ago

Any suggestions on how you would implement this when you start with points that 3D? Is there an elegant way to keep the z within this library?

Thanks.

aufsess

toxmeister

Re: Re: How to use the Toxiclibs Voronoi class?

2 years ago

Unfortunately, 3D is not supported by these classes: Voronoi & DelaunayTriangulation (hence their locations in the mesh2d package). Take a look at wblut's hemesh library if you're after 3D Voronois...

http://postspectacular.com | http://toxiclibs.org

almost_sc..

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Hello -

Frist, thanks Toxi for your awesome library. Every time I use it, not only can I do amazing things, but I learn so much in the process.

I've started playing with your Voronoi class, and I have a question.

What is the best way to extract the vertices that are formed as you build the Voronoi? Currently I'm comparing all the vertices that make up the polygons to find which one have commons.

Is there a more direct method that you could recommend?

Thanks!

toxmeister

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Thanks for the kind words! :)

You could use a HashSet to easily get a unique set of Voronoi region vertices, something like this:

Set<Vec2D> uniqueVerts=new HashSet<Vec2D>();
for(Polygon2D region : voronoi.getRegions()) {
uniqueVerts.addAll(region.vertices);
}
for(Vec2D u : uniqueVerts) {
// do something with uniques
}

I've been thinking about that use case myself a while ago, but this will require some further thinking. The issue of that in the above solution is that even though some vertices are extremely close (may 0.0001 units away from each other) they still are considered unique. Therefore I've been starting to do some work on a new container class for vectors which is decimating/snapping coordinates to a given grid resolution, but meanwhile been thinking about a more generic solution. If you need something similar in effect, you can for now also achieve it like this:

import toxi.math.*;
Set<Vec2D> uniqueVerts=new HashSet<Vec2D>();
float prec=5;
for(Polygon2D region : voronoi.getRegions()) {
for(Vec2D v : region.vertices) {
v.x=MathUtils.roundTo(v.x, prec);
v.y=MathUtils.roundTo(v.y, prec);
uniqueVerts.add(v);
}
}

Hth!

http://postspectacular.com | http://toxiclibs.org

almost_sc..

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Hi Toxi,

See - Like I said, I learn something new. I never knew about the set interface. I can already see how that will come in handy.

So your reply makes perfect sense to me (after reading up on sets

), however, my MathUtils class does not seem to have a roundTo method. I've download the most recent version of ToxiLibs, and it's not even listed in the included JavaDoc. Nor do I see it here on the google code page.

Also, if you don't mind, perhaps you can give me a bit more guidance. Ultimately, I need a representation of the Voronoi that is more like a Graph, with an explicit representation of the nodes (vertex) and edges, rather than the polygon regions. Really, I need to be able to recreate the positions of each vertex and the relative vectors that make up the edges associated with each point.

My thinking is, one I know where all the vertices are, I could search though all the polygons, find the three sharing a vertex, and find the additional point each shares with one of the others.

Again, is there a more direct way to do this?

Thanks, again, for the help, and your work!

toxmeister

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Gosh, I really need to bundle a new release (the last one was yesterday a year ago!)... sometimes it's hard to remember what was available back then and what wasn't...

You can copy & paste the roundTo() function(s) from here:

http://hg.postspectacular.com/toxiclibs/src/tip/src.core/toxi/math/MathUtils.java#cl-589

Please also be aware that the Google Code repo is NOT maintained anymore, the master branch lives at hg.postspectacular.com/toxiclibs/ since 2010...

Now, to turn this into a proper graph, I've taken this as an opportunity to create a new demo for the next release, pasted below. This is a very simple undirected graph implementation, but maybe is good enough for your purposes or at least helps you to get going:

/**
* Demonstration of a simple undirected graph implementation
* for navigating voronoi regions (or connected points in general).
*
* Move mouse to select vertices and see their related edges:
* 1st degree - magenta
* 2nd degree - green
*
* (c) 2012 Karsten Schmidt // LGPL licensed
*
* Requires toxiclibs-0020 or later..
*/
import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.processing.*;
Voronoi voronoi = new Voronoi();
UndirectedGraph graph=new UndirectedGraph();
ToxiclibsSupport gfx;
Vec2D selectedVertex=null;
float snapDist = 5*5;
void setup() {
size(400,400);
smooth();
PolygonClipper2D clip=new SutherlandHodgemanClipper(new Rect(10,10,width-20,height-20));
for(int i=0; i<25; i++) {
voronoi.addPoint(new Vec2D(random(width),random(height)));
}
for (Polygon2D poly : voronoi.getRegions()) {
poly=clip.clipPolygon(poly);
// add all edges of the polygon to the graph (duplicates are ignored automatically)
for(int i=0,num=poly.vertices.size(); i<num; i++) {
graph.addEdge(poly.vertices.get(i),poly.vertices.get((i+1)%num));
}
}
gfx=new ToxiclibsSupport(this);
noLoop();
}
void draw() {
background(255);
stroke(0);
strokeWeight(1);
for(Edge e : graph.getEdges()) {
gfx.line(e.a,e.b);
}
if (selectedVertex!=null) {
strokeWeight(3);
// show related edges for selected vertex
for(Edge e1 : graph.getEdgesForVertex(selectedVertex)) {
stroke(255,0,255);
gfx.line(e1.a,e1.b);
stroke(0,255,0);
// now get 2nd degree relationships
for(Edge e2 : graph.getEdgesForVertex(e1.getOtherEndFor(selectedVertex))) {
if (e2!=e1) {
gfx.line(e2.a,e2.b);
}
}
}
noStroke();
fill(0,255,255);
gfx.circle(selectedVertex,8);
}
}
void mouseMoved() {
selectedVertex=null;
Vec2D mousePos=new Vec2D(mouseX,mouseY);
for(Vec2D v : graph.getVertices()) {
if (mousePos.distanceToSquared(v) < snapDist) {
selectedVertex=v;
break;
}
}
redraw();
}
/**
* This class implements a undirected vertex graph and provides basic connectivity information.
* Vertices can only be added by defining edges, ensuring there're no isolated nodes
* (but allowing for subgraphs/clusters).
*/
public class UndirectedGraph {
// use vertex position as unique keys and a list of edges as its value
private final Map<Vec2D, List<Edge>> vertexEdgeIndex = new HashMap<Vec2D, List<Edge>>();
// set of all edges in the graph
private final Set<Edge> edges = new HashSet<Edge>();
// attempts to add new edge for the given vertices
// if successful also add vertices to index and associate edge with each
public void addEdge(Vec2D a, Vec2D b) {
if (!a.equals(b)) {
Edge e = new Edge(a, b);
if (edges.add(e)) {
addEdgeForVertex(a, e);
addEdgeForVertex(b, e);
}
}
}
private void addEdgeForVertex(Vec2D a, Edge e) {
List<Edge> vertEdges = vertexEdgeIndex.get(a);
if (vertEdges == null) {
vertEdges = new ArrayList<Edge>();
vertexEdgeIndex.put(a, vertEdges);
}
vertEdges.add(e);
}
public Set<Edge> getEdges() {
return edges;
}
// get list of edges for the given vertex (or null if vertex is unknown)
public List<Edge> getEdgesForVertex(ReadonlyVec2D v) {
return vertexEdgeIndex.get(v);
}
public Set<Vec2D> getVertices() {
return vertexEdgeIndex.keySet();
}
}
/**
* A single immutable, undirected connection between two vertices.
* Provides equals() & hashCode() implementations to ignore direction.
*/
public class Edge {
public final ReadonlyVec2D a, b;
public Edge(ReadonlyVec2D a, ReadonlyVec2D b) {
this.a = a;
this.b = b;
}
public boolean equals(Object o) {
if (o != null && o instanceof Edge) {
Edge e = (Edge) o;
return
(a.equals(e.a) && b.equals(e.b)) ||
(a.equals(e.b) && b.equals(e.a));
}
return false;
}
public Vec2D getDirectionFrom(ReadonlyVec2D p) {
Vec2D dir = b.sub(a);
if (p.equals(b)) {
dir.invert();
}
return dir;
}
public ReadonlyVec2D getOtherEndFor(ReadonlyVec2D p) {
return p.equals(a) ? b : a;
}
public int hashCode() {
return a.hashCode() + b.hashCode();
}
public String toString() {
return a.toString() + " <-> " + b.toString();
}
}

http://postspectacular.com | http://toxiclibs.org

almost_sc..

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Toxi!

Thank you so much, you are my hero for the day! This is exactly what I needed!

Thanks, you are awesome!

__vac__

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Hi,

i'm using this post as i think it is the best place to ask my question.

After experimenting the Voronoi class today and reading Paul Bourke's little article about the subject, i didn't go in depth of the algorithm though. But i think i do understand the purpose of such a tool.

What i don't understand is how from a 2D sets of points/sites interpolated with the voronoi algorithm, how can i generate a Terrain. How do i add heights to every sites and have the interpolation on the heights as well (do i necessarily need to use a 3D version of the algorithm?) .

Thank you very much and hopefully i will be able to attend your workshop in Belgrade and meet you.

Toxic rocks!

Laurent Novac

Don't hesitate to tell me if i have it totally wrong.

almost_sc..

Re: How to use the Toxiclibs Voronoi class?

1 year ago

Laurent --

The Voronoi class in Toxilibs ends up producing a list of polygons. If wanted to generate a terrain from those I might try first finding their centroid, creating a heigh vector at the centroid and build a mesh from each vertex of the polygon to that height vector. Depending on your scale this could be a rather sharp terrain, but you can always generate a series of heigh vecs for each polygon to create a little hill around each polygon.

You would only need a 3D implementation of the Voronoi if you wanted to subdivide a volume. I think the hemiMesh lib can do that.

Hope that helps you on the right path.