How to enforce a minimum distance between curves?

I want to learn to draw non-overlapping random curves.

I’ve written code that generates random curves on the screen but they currently overlap.

In the example above, each curve is drawn by

  • Choosing a random start location
  • Calling beginShape()
  • For a chosen number of N steps
    • Choosing a semi random position and direction away from the last drawn vertex
    • Calling curveVertex() at that new position
  • Calling endShape()

Does anyone have any advice or examples of techniques to prevent overlap?

I was thinking at each new step, somehow figure out the shortest distance to the nearest curve and make sure its above a certain threshold. Not sure how best to do that though.

please format code with </> button * homework policy * asking questions

Generally you want a method of checking whether the vertex you’re about to add is “too close” to another point.

The simplest and least efficient way to do this is to keep a list of points that you’ve already placed, then, each time you go to add a new point, check that the new point isn’t too close to any of the points in the list. The pseudocode looks like this:

existing_points = ...
loop over the number of curves:
    current_curve = ...
    loop over the number of points per curve:
        new_point = ...
        for existing_point in existing_points:
            if distance(existing_point, new_point) < min_distance:
                end the current_curve
        add new_point to current_curve
    add points from current_curve to existing_points
    plot current_curve

This is very inefficient because you’re checking the distance to each point in existing_points each time you create a new point.

The more efficient method is very similar, you just use a data structure that makes it easy to check only the points in the vicinity of new_point. Examples of these data structures are “k-d trees” or a “quad trees”. I’m not sure if there are Processing libraries that provide these data structures, so you’ll have to do some homework on that. I write my Processing sketches in a completely different language (Clojure), so I don’t know how Processing libraries work, unfortunately.

1 Like

Thanks for the pointers Zach!

I implemented the inefficient method and am getting some non-overlapping curves!

The number of vertices per curve seems to be the variable to play around with; the “denser” the vertices per curve, the more accurate the distance checking is (at the cost of being slower).

Ah, I forgot that you’re using splines. The tricky part with splines is that it only takes a few points to define the whole curve. If you select a position at random along the curve, you’re not guaranteed that there’s an actual vertex there. This is why your distance checking is having trouble.

There’s a tradeoff to be had here. If you encode your curves as a bunch of very short line segments:

beginShape()
for (x, y) in curve_points:
    vertex(x, y)
endShape()

you have to have many more vertices, your distance checking is slower, and your rendering is slower, but your distance checking is more accurate. If you encode your curve as a spline (curveVertex vs. vertex) you don’t need as many points, your rendering is faster, but there are fewer and more sparsely distributed points to use as anchors to measure your distance against.

2 Likes

Nice! Thanks for explaining the difference between curve_vertex() (splines) and vertex(). I’d heard of approximating curves with “very short line segments”, but wasn’t sure if it was a viable option or not.

Anyway, I replaced my use of curveVertex with vertex and am starting to see some promising results!

There is still a bit of overlap, the cause of which I’m not sure yet. I’m thinking its because I need to factor in my strokeWidth

  public Curve(PVector start, color c) {
    this.start = start;
    this.c = c;
    vertices = new ArrayList<PVector>();
  }
  
  public void draw(FlowField f) {
    position = start.copy();
    beginShape();
    noFill();
    strokeWeight(10);
    stroke(c, 100);
    vertex(position.x, position.y);
    for (int i = 0; i < numSteps; i++) {       
      PVector force = f.forceAt(position.x, position.y);
      force.setMag(stepLengthPercent * width);
      position.add(force);
      
      if (isTooClose(position)) {
        break;
      }
      
      vertices.add(position.copy());
      vertex(position.x, position.y);
      handleEdges();
    }
    vertex(position.x, position.y);
    endShape();
  }
  
  boolean isTooClose(PVector position) {
    for (Curve c: curves) {
      if (c == this) {
        continue;
      }
      for (PVector p: c.vertices) {
        float distance = position.dist(p);
        if (distance < minDistance) {
           return true;
        }
      }
    }
    
    return false;
  }
}

(Or more likely, I don’t think I’m doing sufficient checks when choosing a start point for each curve)

Without digging into the code, it looks like the distance calculations aren’t picking up all of the “too close” points. You can see that some curves are completely overlapping. A start-position that is that close to an existing curve should be rejected.

Maybe try increasing the minimum distance to something really big and see if you still get overlapping curves.

You were right. I wasn’t storing the first and last vertexes of each curve.

Latest iteration is looking pretty good!

FlowField flowField;
RandomColorGenerator colorPicker;
StartingPointPicker startPicker;
ArrayList<Curve> curves;

// ***********************CONFIGURATION ************
int maxCurves = 600; // Draw up to these many curves, space permitting
int numSegmentsPerCurve = 300;  // The bigger this number is, the longer the lines might get
float segmentLength = 12; // The smaller this number, the less jagged the curves
float increaseRate = 0.02; // Flow Field increase rate, the higher this number, the sharper the changes in direction 
float strokeWeight = 10;
float minDistance = 20; 

// ***********************MAIN METHODS**************
void setup(){
	size(600,600);
  background(255);
  
	flowField = new FlowField(10);
  flowField.update();
  
  curves = new ArrayList<Curve>();

  startPicker = new StartingPointPicker();
  colorPicker = new RandomColorGenerator(0.5, 0.95);
  
  for (int i = 0; i < maxCurves; i++) {
      PVector start = startPicker.getStartingPoint();
      if (start == null) {
        break;
      }
      Curve c = new Curve(start, colorPicker.getColor());
      curves.add(c);

      c.draw(flowField);
  }
  noLoop();
}

// **************************CLASSES******************

class StartingPointPicker {
  public PVector getStartingPoint() {
    PVector p;
    int maxAttempts = 1000;
    int attempts = 0; 
    
    do {
      p = new PVector(random(width), random(height));
      attempts +=1 ;
    } while(isTooClose(p) && attempts < maxAttempts);
    
    if (isTooClose(p)) {
      return null;
    }
    
    return p;    
  }
  
  boolean isTooClose(PVector position) {
    for (Curve c: curves) {
      for (PVector p: c.vertices) {
        float distance = position.dist(p);
        if (distance < minDistance) {
           return true;
        }
      }
    }
    return false;
  }
}


class Curve {
  PVector start;
  PVector position;
  ArrayList<PVector> vertices;
  color c;
    
  public Curve(PVector start, color c) {
    this.start = start;
    this.c = c;
    this.vertices = new ArrayList<PVector>();
  }
  
  public void draw(FlowField f) {
    position = start.copy();
    beginShape();
    noFill();
    strokeWeight(strokeWeight);
    stroke(c, 100);
    vertex(position.x, position.y);
    vertices.add(position.copy());
    
    for (int i = 0; i < numSegmentsPerCurve; i++) {       
      PVector force = f.forceAt(position.x, position.y);
      force.setMag(segmentLength);
      position.add(force);
      
      if (isTooClose(position)) {
        break;
      }
      
      vertex(position.x, position.y);
      vertices.add(position.copy());
    }
    vertex(position.x, position.y);
    endShape();
  }
  
  boolean isTooClose(PVector position) {
    // Return true if too close to a vertex on another curve
    for (Curve c: curves) {
      if (c.equals(this)) {
        continue;
      }
      for (PVector p: c.vertices) {
        float distance = position.dist(p);
        if (distance < minDistance) {
           return true;
        }
      }
    }
    
    // Return true if too close to the border
    if (position.x+minDistance > width) {
      return true;
    }
    if (position.x-minDistance < 0) {
      return true;
    }
    if (position.y+minDistance > height) {
      return true;
    }
    if (position.y-minDistance < 0) {
      return true;
    }
    
    return false;
  }
}

That’s looking much better :+1: Nice job!

Hi @oli, I am actually doing some experiment in the flowfield area and was trying to understand your code. About the forceAt function in the Flowfield class, I know it’s taking his parameter from the StartingPointPicker class, but I was wondering what does it do with it. Can you tell me more about it ?