Exception in Toxiclibs voronoi.addPoint() when image is large (5k x 5k or larger)

[mocelet]

I am using the Toxiclibs voronoi mesh to generate a set of non-overlapping lines in a circle, and have based my sketch on the example code I found at https://forum.processing.org/one/topic/toxiclib-voronoi-example-sketch.html

For smaller image sizes (3000x3000 and smaller) the code below is working as intended, but on larger images (5000x5000 and larger) I sometimes get an exception when voronoi.addPoint() is called:

Warning: Checking all triangles for DelaunayVertex(4802.423828125,1680.7874755859375)
Warning: No triangle holds DelaunayVertex(4802.423828125,1680.7874755859375)
IllegalArgumentException: No containing triangle
IllegalArgumentException: No containing triangle
IllegalArgumentException: No containing triangle

In the saved image I see all the points, but the mesh between the points is not present in the lower right part of the image. As the image size increases, the size of the region without mesh also increases (10% size image, let me know if you want to see the full size image):

My goal is to have a 30000 x 30000 image, with the lines evenly distributed across the circle, so any help would be greatly appreciated.

The full sketch is:

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();

// switches
boolean doShowPoints = true;
boolean doShowHelp = false;
boolean doSave = true;

int seed=12345;
int imageDim = 5000;
int numPoints = 0;

void settings(){
  size(imageDim, imageDim);
}  

void setup() {
  randomSeed(seed);
  smooth();

  xpos=new FloatRange(0, width);
  ypos=new FloatRange(0, height); 
  
  gfx = new ToxiclibsSupport(this);
  textFont(createFont("SansSerif", 10));
  
  addRandomPoints(1000);
}

void draw() {
  //White background
  background(255);
  
  //Background circle
  fill (170, 170, 170);
  ellipse(width*0.5, height*0.5,width, height);
  
  // draw all voronoi polygons, clip them if needed...
  stroke(0);
  noFill();
  for(Polygon2D tri : voronoi.getRegions()) {
    java.util.List<Vec2D> vert = tri.vertices;
    
    for(int i=0; i<vert.size(); i++){
      Vec2D p1=vert.get(i);
      Vec2D p2=vert.get((i+1) % vert.size());
      
      Vec2D start=p1.interpolateTo(p2,0.1);
      Vec2D end=p1.interpolateTo(p2,0.9);
      
      if(onCircle(start) && onCircle(end)){
        gfx.line(start,end);
      }
    }
  }
  
  // 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("Points" + numPoints + "_" + DateUtils.timeStamp() + ".tif");
    doSave = false;
  }
}

void keyPressed() {
  switch(key) {
  case ' ':
    doSave = true;
    break;
  case 'x':
    voronoi = new Voronoi();
    break;
  case 'p':
    doShowPoints = !doShowPoints;
    break;
  case 'h':
    doShowHelp=!doShowHelp;
    break;
  case 'r':
    addRandomPoints(100);
    break;
  }
}

void addRandomPoints(int count){
  Vec2D p = new Vec2D(0,0);
  for (int i = 0; i < count; i++) {
      p.set(xpos.pickRandom(), ypos.pickRandom());
    
    try {
      voronoi.addPoint(p);
    }
    catch(Exception e) {
      numPoints--;
    }
  }
  numPoints += count;
}

boolean onCircle(Vec2D a) {
  Vec2D c = new Vec2D(width/2, height/2);
  float maxRadPx = width/2;
 
  return (a.distanceTo(c) <= maxRadPx);
}

[micycle]

Often a Delaunay Triangulation (from which a Voronoi diagram is computed) is initialised with a large triangle.

Indeed if we look at the source code we see this is the case:

ToxicLibs doesn’t seem to support adding a vertex that lies outside this initial triangle.

Not quite to scale, but this show’s going on (remember in Processing the y-axis is flipped):

Lucky for you the DEFAULT_SIZE size field is public, so you can increase easily it to support a larger diagram.

Voronoi.DEFAULT_SIZE = 30000;
voronoi =  new Voronoi();

[mocelet]

You are a star. Thank you.

I couldn’t get it to recognise .DEFAULT_SIZE as something it could set, but passing a larger initial size to the constructor fixes the problem.