# How to enforce a minimum distance between curves?

**URL:** <https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875>\
**Category:** Libraries\
**Created:** [June 23, 2021, 5:43pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875 "2021-06-23T17:43:45Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![oli](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/oli/32/13732_2.png) [@oli](https://discourse.processing.org/u/oli)\
**Post date:** [June 23, 2021, 5:43pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/1 "2021-06-23T17:43:46Z")

</div>

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.

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/9/98341870b0b734730dce1b449b884990dd5cf833.jpeg)

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](https://discourse.processing.org/faq/#homework) \* [asking questions](https://discourse.processing.org/t/2147)

---

<div class="post-metadata">

**Author:** ![zmitchell](https://avatars.discourse-cdn.com/v4/letter/z/c2a13f/32.png) [@zmitchell](https://discourse.processing.org/u/zmitchell)\
**Post date:** [June 23, 2021, 8:03pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/2 "2021-06-23T20:03:54Z")

</div>

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:

```nohighlight
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.

---

<div class="post-metadata">

**Author:** ![oli](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/oli/32/13732_2.png) [@oli](https://discourse.processing.org/u/oli)\
**Post date:** [June 23, 2021, 11:15pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/3 "2021-06-23T23:15:12Z")

</div>

Thanks for the pointers Zach!

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

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/a/a3f8c9208a3bc68200babc30e606a913c4e37056.png)

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).

---

<div class="post-metadata">

**Author:** ![zmitchell](https://avatars.discourse-cdn.com/v4/letter/z/c2a13f/32.png) [@zmitchell](https://discourse.processing.org/u/zmitchell)\
**Post date:** [June 23, 2021, 11:41pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/4 "2021-06-23T23:41:50Z")

</div>

> [@oli](#):
>
> 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:

```plaintext
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.

---

<div class="post-metadata">

**Author:** ![oli](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/oli/32/13732_2.png) [@oli](https://discourse.processing.org/u/oli)\
**Post date:** [June 24, 2021, 4:36am UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/5 "2021-06-24T04:36:01Z")

</div>

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`

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/f/ff7dd9def9c92a2c69131a0c80c338480ebc3f21.png)

```auto
  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;
  }
}

```

---

<div class="post-metadata">

**Author:** ![oli](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/oli/32/13732_2.png) [@oli](https://discourse.processing.org/u/oli)\
**Post date:** [June 24, 2021, 4:39am UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/6 "2021-06-24T04:39:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![zmitchell](https://avatars.discourse-cdn.com/v4/letter/z/c2a13f/32.png) [@zmitchell](https://discourse.processing.org/u/zmitchell)\
**Post date:** [June 24, 2021, 4:06pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/7 "2021-06-24T16:06:49Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![oli](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/oli/32/13732_2.png) [@oli](https://discourse.processing.org/u/oli)\
**Post date:** [June 24, 2021, 10:12pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/8 "2021-06-24T22:12:03Z")

</div>

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

Latest iteration is looking pretty good!

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/666ef041ca121e74a78084c25dd024dc02248db9.png)

```auto
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;
  }
}

```

---

<div class="post-metadata">

**Author:** ![zmitchell](https://avatars.discourse-cdn.com/v4/letter/z/c2a13f/32.png) [@zmitchell](https://discourse.processing.org/u/zmitchell)\
**Post date:** [June 24, 2021, 10:59pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/9 "2021-06-24T22:59:40Z")

</div>

That’s looking much better 👍 Nice job!

---

<div class="post-metadata">

**Author:** ![dams2007](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/dams2007/32/7434_2.png) [@dams2007](https://discourse.processing.org/u/dams2007)\
**Post date:** [February 11, 2022, 1:39pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/10 "2022-02-11T13:39:17Z")

</div>

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 ?

---

<div class="post-metadata">

**Author:** ![neofit](https://avatars.discourse-cdn.com/v4/letter/n/ea5d25/32.png) [@neofit](https://discourse.processing.org/u/neofit)\
**Post date:** [July 23, 2022, 5:51pm UTC](https://discourse.processing.org/t/how-to-enforce-a-minimum-distance-between-curves/30875/11 "2022-07-23T17:51:16Z")

</div>

This is a great example. Thanks for sharing.

Any tips or suggestions on translating this code to p5js? Sorry, I am not familiar with processing.

Thanks!