Voronoi Toxiclibs library question

asmith33

I am trying to interact with Toxiclibs vornonoi objects and I am missing something. Namely I am trying to interact with the centroids of each region in a Voronoi class, and also the sites of the Voronoi class.

For example:

println("Original Sites");
    for (Vec2D site : voronoi.getSites()) {
      println(site);
    }

println("Original Centroids");
    for (Polygon2D poly : voronoi.getRegions()) {
      println(poly.getCentroid());
    }

My output is:

Original Sites
{x:78.0, y:78.0}               
{x:525.0, y:77.0}             
{x:525.0, y:528.0}           
{x:76.0, y:527.0}             
{x:303.0, y:305.0}           < -- center

Original Centroids
{x:-3205.746, y:-3205.5093}             
{x:3815.8723, y:-3015.4072}
{x:302.67184, y:304.48938}           < -- center
{x:-6293.649, y:2903.7415}
{x:7501.3203, y:3228.6487}

Mind you my fundamentals are pretty poor and I'm not real solid on what is going on in my for loops, but the way I see it, I am continually creating new Polygon2D or Vec2D objects, that exist only until the bottom of the for loop. Then, I continue looping until I've iterated through the entire voronoi object. The issue is the "center" centroid and the "center" site don't happen at the same iteration. This is really messing up my ability to interact with the system. Notice the center site came out of the for loop last, while the center centroid came out of the for loop 3rd? In order of points placed on screen the sites output is correct.

Anyway, my goal is to use an ArrayList to create new voronoi objects after I've modified the sites, but I can't do this correctly if the order is different between sites and centroids. If anyone has an tips on how I could go about solving this I would appreciate the help.

Also, Toxiclibs states the the output of his voronoi method "getRegion()" is java.util.List, I don't even know what a list is in processing. ArrayList sure, but I don't think he means an ArrayList. His output for method "getSites()" is java.util.List. So, maybe my issue is a misunderstanding of a List.

GoToLoop

• ArrayList is just 1 type of List. There are others!
• And a List is itself a Collection. That's Java's hierarchy!
• If you want a List of Polygon2D from getRegions(), use:
  List<Polygon2D> polies = new ArrayList();
for (Polygon2D poly : voronoi.getRegions()) polies.add(poly);
• Since I dunno this library, I can't help ya out further!

amnon

First, the library is called Toxiclibs. Fixed. :-)

Second, do you really need it to be in the same order?

Third, if you really need the same order, then sort it. Per site, go over the list of polygons until you find the one that the site is in (point in polygon), then add it to a (new) list. Once you have gone over all sites, you should have a list of polygons in the same order as the sites. Then you get the centroids.

asmith33

Thank you GoTo, that makes a lot of sense. I'll start working with that to become more familiar.

amnon, here we go again! :D

I'll try implementing your "third." Any idea why the library wouldn't just output sites and regions in the same order? Seems like that would be fairly intuitive. I guess I just assumed I was doing something wrong when calling them.

amnon

I assume this is because of the algorithm that generates the regions. Not sure if this is the same algorithm that is used, but this visualization gives an insight in the way voronoi regions are generated. Press "Animate sweep line".

asmith33

GoToLoop, I was trying our your List expression but I get the error message of 'Cannot find a class or type named "List."' Also, the List identifier isn't being assigned a color like other data types do (orange). Seems like processing isn't recognizing List as a data type.

GoToLoop

All Collection classes/interfaces, like List, ArrayList, HashMap, etc., belong to Java's API, not Processing: @-)
https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

In order to use List interface, we 1st need to import it: import java.util.List;:
https://docs.oracle.com/javase/8/docs/api/java/util/List.html

Also, the List identifier isn't being assigned a color like other data types do (orange).

B/c it's not an "official" Processing's API. Although I don't see why they couldn't standardize it since it doesn't interfere w/ "JS Mode" after all. *-:)

asmith33

Update, I used this:

case 'l':
    sites = new ArrayList();
    polies = new ArrayList();
    for (Vec2D site : voronoi.getSites()) sites.add(site);
    for (int i=0; i<sites.size(); i++) {
      Vec2D site = sites.get(i);
      for (Polygon2D poly : voronoi.getRegions()) {
        if (poly.containsPoint(site)) polies.add(poly);
      }
    }
    for (int i=0; i<sites.size(); i++) {
      Polygon2D poly = polies.get(i);
      Vec2D site = sites.get(i);
      println("i=" + i);
      println("Centroid: " + poly.getCentroid() + " Site: " + site);
    }
    break;

And got this output:

i=0
Centroid: {x:-3191.5664, y:-3218.2837} Site: {x:78.0, y:78.0}
i=1
Centroid: {x:3840.1035, y:-2992.3496} Site: {x:527.0, y:79.0}
i=2
Centroid: {x:7499.253, y:3235.2285} Site: {x:526.0, y:529.0}
i=3
Centroid: {x:-6298.1514, y:2902.6182} Site: {x:76.0, y:526.0}
i=4
Centroid: {x:302.24872, y:304.5047} Site: {x:302.0, y:305.0}

So now the order matches up. Thanks for the tip amnon.

asmith33

Great, thank you GoTo. Between the two of you this has helped quite a bit. I suppose I do have one last question regarding lists. When would I want to use an ArrayList vs a List? Since list wasn't working I basically did what you said just using ArrayList and it seemed to work. I'm not sure I understand the distinction. My guess is if I had matched the output type of the getRegions() function (List), I could have done something like..

polies = voronoi.getRegions();

Skipping the for() statement.

asmith33

Update: This site shows what I am trying to do with these regions quite well (Lloyd Relaxation). http://www.jasondavies.com/lloyd/

However, by ignoring regions who's centroids are outside the sketch I was able to reproduce something fairly similar. Code below. I made a case that by pressing L (lower case), you produce one iteration of lloyd relaxation.

If anyone knows how to handle the edge cases, please let me know.

/*
 * 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();
ArrayList<Vec2D> sites;
ArrayList<Polygon2D> polies;

// 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()));
    }
  case 'l':
    /* This section creates two ArrayLists that hold the sites and polynomials
     * from the voronoi class, and keeps them in order.
     */
    sites = new ArrayList();
    polies = new ArrayList();
    for (Vec2D site : voronoi.getSites()) sites.add(site);
    for (int i=0; i<sites.size(); i++) {
      Vec2D site = sites.get(i);
      for (Polygon2D poly : voronoi.getRegions()) {
        if (poly.containsPoint(site)) polies.add(poly);
      }
    }
    /* This section outputs the sites and centroids, demonstrating that they
     * are in the same order
     *
    for (int i=0; i<sites.size(); i++) {
      Polygon2D poly = polies.get(i);
      Vec2D site = sites.get(i);
      println("i=" + i);
      println("Centroid: " + poly.getCentroid() + " Site: " + site);
    }
     */
    /* This section limits the LLoyd algorithm to regions who's centroids are within the sketch area. 
     * It then updates the sites to be the centroids of the voronoi regions.
     * Then it creates a new voronoi class.
     */ 
    for (int i=0; i<sites.size(); i++) {
      Polygon2D poly = polies.get(i);
      Vec2D site = sites.get(i);
      if (poly.getCentroid().x > 0 && poly.getCentroid().x < width && poly.getCentroid().y > 0 && poly.getCentroid().y < height) sites.set(i, poly.getCentroid());
    }
    voronoi = new Voronoi();
    voronoi.addPoints( sites );
    break;
  }
}

void mousePressed() {
  voronoi.addPoint(new Vec2D(mouseX, mouseY));
}

GoToLoop

When would I want to use an ArrayList vs a List?

Since ArrayList inherits from List, we may choose the latter for the a variable and the former for the object:

• List<Polygon2D> polies = new ArrayList();
• ArrayList<Polygon2D> polies = new ArrayList();

It's more a matter of taste! Although using the most generic is more pro 1337! ;;)

Skipping the for () statement.

Since I dunno that library, I chose to present you the safer for () + add() option! X_X
But of course, if getRegions() indeed returns a List<Polygon2D>, a simpler
List<Polygon2D> polies = voronoi.getRegions(); is the most correct way! =:)

amnon

To handle the edges case, you can use constrain instead of completely discarding those centroids. Also there are some optimizations possible. See the code below (I stripped away some stuff so I could focus on the relevant code better).

Adapted Code

import java.util.List;

import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.processing.*;

ToxiclibsSupport gfx;

Voronoi voronoi = new Voronoi();
List <Polygon2D> polygons = new ArrayList <Polygon2D> ();
List <Vec2D> sites = new ArrayList <Vec2D> ();

void setup() {
  size(600, 600);
  gfx = new ToxiclibsSupport(this);
  smooth();
  noFill();
}

void draw() {
  background(255);
  strokeWeight(1);
  stroke(0);
  for (Polygon2D poly : polygons) {
    gfx.polygon2D(poly);
  }
  strokeWeight(5);
  stroke(0, 0, 255);
  for (Vec2D v : sites) {
    point(v.x, v.y);
  }

  frame.setTitle(round(frameRate) + " fps | numSites: " + sites.size());
}

void keyPressed() {
  if (key == 'x') {
    voronoi = new Voronoi();
    polygons.clear();
    sites.clear();
  }
  if (key == 'r') {
    for (int i=0; i<10; i++) {
      voronoi.addPoint(new Vec2D(random(width), random(height)));
    }
    polygons = voronoi.getRegions();
    sites = voronoi.getSites();
  }
  if (key == 'l') {
    List <Polygon2D> availablePolygons = voronoi.getRegions();
    for (Vec2D v : sites) {
      for (int i=0; i<availablePolygons.size(); i++) {
        Polygon2D poly = availablePolygons.get(i);
        if (poly.containsPoint(v)) {
          Vec2D centroid = poly.getCentroid();
          v.set(constrain(centroid.x, 0, width), constrain(centroid.y, 0, height));
          availablePolygons.remove(i);
        }
      }
    }
    voronoi = new Voronoi();
    voronoi.addPoints(sites);
    polygons = voronoi.getRegions();
  }
}

void mousePressed() {
  voronoi.addPoint(new Vec2D(mouseX, mouseY));
  polygons = voronoi.getRegions();
  sites = voronoi.getSites();
}

asmith33

Nice amnon, those changes make a lot of sense. I wasn't aware of that constrain function, that makes those edge cases behave well.

PS. I spent the last hour or so looking through forums on how to download and install java libraries, but I guess you don't have to?! I ended up just adding that import line and I was able to implement List.

amnon

You already have all java libraries, because you have java. You can import any java.* you need. See the full list here: http://docs.oracle.com/javase/7/docs/api/

clankill3r

@amnon

I really like your relaxation and I made a class to interpolate. I tried to make it as optimized as I could. I think there is a lot of room for optimization in the Voronoi class itself by reusing created object but that could be quite some work.

http://hg.postspectacular.com/toxiclibs/src/44d9932dbc9f9c69a170643e2d459f449562b750/src.core/toxi/geom/mesh2d/Voronoi.java?at=default

// http://forum.processing.org/two/discussion/comment/33576#Comment_33576
import java.util.List;

import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.processing.*;

ToxiclibsSupport gfx;


List <Vec2D> sitesOriginal = new ArrayList <Vec2D>();

VoronoiRelaxer vr = new VoronoiRelaxer();

int iterations = 5;

void setup() {
  size(600, 600);
  gfx = new ToxiclibsSupport(this);
  smooth();
  noFill();
}


// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

void draw() {
  background(255);
  strokeWeight(1);
  stroke(0);

  float t = norm(mouseX, 0, width);

  vr.relax(sitesOriginal, t, iterations);

  for (Polygon2D poly : vr.polygons) {
    gfx.polygon2D(poly);
  }
  strokeWeight(5);
  stroke(0, 0, 255);
//  for (Vec2D v : sitesTarget) {
//    point(v.x, v.y);
//  }

  frame.setTitle(round(frameRate) + " fps | numSites: " + sitesOriginal.size()+ "iterations: "+iterations);
}


// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


void keyPressed() {
  if (key == 'x') {
    //voronoi = new Voronoi();
    //polygons.clear();
    sitesOriginal.clear();
    //sitesTarget.clear();
  }
  if (key == 'r') {
    for (int i=0; i<10; i++) {
      sitesOriginal.add(new Vec2D(random(width), random(height)));
    }
    vr.relax(sitesOriginal, norm(mouseX, 0, width), iterations);
  }
  if (key == '=' || key == '+') {
    iterations++;
  }
  if (key == '-' || key == '_') {
    iterations = max(iterations-1, 1);
  }

}




class VoronoiRelaxer {

  Voronoi voronoi = new Voronoi();

  List <Polygon2D> polygons = new ArrayList <Polygon2D> ();


  List <Vec2D> sitesTarget = new ArrayList <Vec2D> ();

  float lastT = -1;
  float lastIterations = -1;
  float lastVecsSize = -1;

  // . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  void relax(List<Vec2D> origVecs, float t, int iterations) {

    if (t == lastT && lastVecsSize == origVecs.size() && lastIterations == iterations) return;

    t = constrain(t, 0, 1);

    // assure size
    for (int i = sitesTarget.size(); i < origVecs.size(); i++) {
      sitesTarget.add(new Vec2D());
    }


    Voronoi prevVoronoi = null;

    for (int it = 0; it < iterations; it++) {

      voronoi = new Voronoi();

      if (prevVoronoi == null) {
        voronoi.addPoints(origVecs);
      }
      else {
        voronoi.addPoints(sitesTarget.subList(0, origVecs.size()));
      }

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

      int j = 0;

      for (Vec2D v : voronoi.getSites()) {

        for (int i = 0; i < availablePolygons.size (); i++) {

          Polygon2D poly = availablePolygons.get(i);

          if (poly.containsPoint(v)) {
            Vec2D centroid = poly.getCentroid();

            sitesTarget.get(j).set(constrain(centroid.x, 0, width), constrain(centroid.y, 0, height));

            availablePolygons.remove(i);
          }
        }

        j++;
      }

      prevVoronoi = voronoi;
    }

    voronoi = new Voronoi();

    for (int i = 0; i < origVecs.size(); i++) {
      Vec2D v1 = origVecs.get(i);
      Vec2D v2 = sitesTarget.get(i);

      v2.x = lerp(v1.x, v2.x, t);
      v2.y = lerp(v1.y, v2.y, t);

      voronoi.addPoint(v2);

    }


    polygons = voronoi.getRegions();

    lastT = t;
    lastVecsSize = origVecs.size();
    lastIterations = iterations;
  }
}