Minimum Spanning Tree - Minimum distance problem

p5.js Coding Questions
1

Hey there, I am having some issue with the minimum distance method.

In this test, I am trying to reproduce; 9.9: Minimum Spanning Tree from the coding train in Processing.js (https://www.youtube.com/watch?v=BxabnKrOjT0&t=357s). source code here

I tried to use Arrays, but it seems to me that the splice function doest quite work the same way with processing.js compared to p5.js (I do not know more about P5.js).

Now I am working on a version of the code with ArrayList but, I do not quite understand the minimum distance method, so I have some IndexOutOfBoundException error.

ArrayList<PVector> vertices = new ArrayList<PVector>();
ArrayList<PVector> unreached;
ArrayList<PVector> reached;

int verticesBase = 10;


//-------------------------------------------------------------


void setup() {
  size(800, 800);
  while (vertices.size() < verticesBase) {
    vertices.add(new PVector(random(width), random(height)));
  }
}


//-------------------------------------------------------------


void draw() {
  background(51);

  unreached = new ArrayList<PVector>();
  reached = new ArrayList<PVector>();

  for (int i = 0; i < vertices.size(); i++) {
    PVector v = vertices.get(i);
    unreached.add(new PVector(v.x, v.y));
  }



  reached.add(unreached.get(0));
  unreached.remove(0);



  println(""+vertices.size());
  println(""+unreached.size());
  println(""+reached.size());


  while (unreached.size() > 0) {
    float record = 10000;
    int rIndex;
    int uIndex;
    for (int i = 0; i < reached.size(); i++) {
      for (int j = 0; j < unreached.size(); j++) {
        PVector v1 = reached.get(i);
        PVector v2 = unreached.get(j);
        float d = dist(v1.x, v1.y, v2.x, v2.y);
        if (d < record) {
          record = d;
          rIndex = i;
          uIndex = j;
        }
      }
    }
    stroke(255);
    strokeWeight(2);
    line(reached.get(rIndex).x, reached.get(rIndex).y, unreached.get(uIndex).x, unreached.get(uIndex).y);
    reached.add(unreached.get(uIndex));
    unreached.remove(rIndex);
  }



  // --- Display

  for (int i = 0; i < vertices.size(); i++) {
    PVector v = vertices.get(i);
    fill(255);
    noStroke();
    ellipse(v.x, v.y, 15, 15) ;
  }

  for (int i = 0; i < unreached.size(); i++) {
    PVector v = unreached.get(i);
    fill(255, 117, 26);
    noStroke();
    ellipse(v.x, v.y, 10, 10) ;
  }

  for (int i = 0; i < reached.size(); i++) {
    PVector v = reached.get(i);
    fill(153, 214, 255);
    noStroke();
    ellipse(v.x, v.y, 5, 5) ;
  }
}



//-------------------------------------------------------------


void mousePressed() {
  vertices.add(new PVector(mouseX, mouseY));
}

Thank you for any advice
Cheers

1 Like
2

My mistake, I messed up with the index
here is the final code

ArrayList<PVector> vertices = new ArrayList<PVector>();
ArrayList<PVector> unreached;
ArrayList<PVector> reached;

int verticesBase = 10;


//-------------------------------------------------------------


void setup() {
  size(800, 800);
  while (vertices.size() < verticesBase) {
    vertices.add(new PVector(random(width), random(height)));
  }
}


//-------------------------------------------------------------


void draw() {
  background(51);

  unreached = new ArrayList<PVector>();
  reached = new ArrayList<PVector>();

  for (int i = 0; i < vertices.size(); i++) {
    PVector v = vertices.get(i);
    unreached.add(new PVector(v.x, v.y));
  }


  reached.add(unreached.get(0));
  unreached.remove(0);


  println(""+vertices.size());
  println(""+unreached.size());
  println(""+reached.size());


  while (unreached.size() > 0) {
    float record = 10000;
    int rIndex = 0;
    int uIndex= 0;
    for (int i = 0; i < reached.size(); i++) {
      for (int j = 0; j < unreached.size(); j++) {
        PVector v1 = reached.get(i);
        PVector v2 = unreached.get(j);
        float d = v1.dist(v2);
        if (d < record) {
          record = d;
          rIndex = i;
          uIndex = j;
        }
      }
    }
    stroke(255);
    strokeWeight(2);
    line(reached.get(rIndex).x, reached.get(rIndex).y, unreached.get(uIndex).x, unreached.get(uIndex).y);
    reached.add(unreached.get(uIndex));
    unreached.remove(uIndex);
  }



  // --- Display

  for (int i = 0; i < vertices.size(); i++) {
    PVector v = vertices.get(i);
    fill(255);
    noStroke();
    ellipse(v.x, v.y, 15, 15) ;
  }

  for (int i = 0; i < unreached.size(); i++) {
    PVector v = unreached.get(i);
    fill(255, 117, 26);
    noStroke();
    ellipse(v.x, v.y, 10, 10) ;
  }

  for (int i = 0; i < reached.size(); i++) {
    PVector v = reached.get(i);
    fill(153, 214, 255);
    noStroke();
    ellipse(v.x, v.y, 5, 5) ;
  }
}



//-------------------------------------------------------------


void mousePressed() {
  vertices.add(new PVector(mouseX, mouseY));
}
1 Like
3

Thank you for sharing your solution!

1 Like