Sort PVector array by distance

I want to sort PVector[] array by distance between points…but idk how to do that correctly…i tried to make that by myself but stuck a tsorting…i can calculate distance but sort…idk how…help pls…
UPD:solution:

void sortPVectorArray(PVector position, PVector[] positions) {
  for (int i = 0; i < positions.length; i++) {
  // Loops through positions
  // Make sure i is not 0 as positions[positions.length] is out of bounds
    if (i != positions.length-1) {
      while (PVector.dist(positions[i+1], position) < PVector.dist(positions[i], position)) {
        PVector temp1 = positions[i+1]; // Assign temp variables
        PVector temp2 = positions[i];
        positions[i] = temp1;
        positions[i+1] = temp2; // Swap them around
      }
    }
  }
}
1 Like

To get the closest, you want to find the point with the least distance to another point.

To get this, you can create a variable storing the closest point, loop through the points, and test if the current point if closer than the closest point.

PVector findNearest(PVector position, PVector[] positions) {
  PVector closestspot = new PVector();
  float closestdistance = -1;

  for (PVector pos : positions) {
    float distance = PVector.dist(pos, position);
    if (closestdistance == -1 || distance < closestdistance) {
      closestspot = pos;
      closestdistance = distance;
    }
  }

  return closestspot;
}

Use the sketch from this link below as a model: :nerd_face:

But change its Comparator::compare() to use dist() instead. :stuck_out_tongue:

2 Likes

I misread your post thinking you wanted the closest point. Luckily sorting an array is just as easy. :slight_smile:

If the point in front is closer, move the point before that point.

void sortPVectorArray(PVector position, PVector[] positions) {
  for (int i = 0; i < positions.length; i++) { // Loops through positions
    // Make sure i is not 0 as positions[positions.length] is out of bounds
    if (i != positions.length-1) {
      while (PVector.dist(positions[i+1], position) < PVector.dist(positions[i], position)) {
        PVector temp1 = positions[i+1]; // Assign temp variables
        PVector temp2 = positions[i];
        positions[i] = temp1;
        positions[i+1] = temp2; // Swap them around
      }
    }
  }
}
2 Likes

Thx…that what i wanted…

I actually have a library component that I developed (inspired by GoToLoop’s previous post) – VecArrayTool – that lets you do general sorting of PVector arrays by multiple criteria – x-y order, y-x order, heading, magnitude, etc. – among other things, like shifting and rotating the points en masse, re-centering, finding bounds, etc.

Here is the Processing-style class for use as a .pde file into PDE sketches:

VecArrayTool.pde


/**
 * Methods for manipulating arrays vectors (PVector[]),
 * including centering, mirroring, rotating, translating,
 * and sorting by x, y, heading, or magnitude, as well as
 * finding the bounds and center of a point array.
 * 
 * Sorting may be augmented by writing a custom comparator.
 *
 * Class methods assume that all vectors may be treated as
 * points having a shared origin (0,0).
 */
public static class VecArrayTool {
  /**
   * x comparator: sort vectors by x, then y
   */
  public static final Comparator<PVector> VEC_CMP_X = new Comparator<PVector>() {
    @ Override public final int compare(final PVector a, final PVector b) {
      int cmp;
      return
        (cmp = Float.compare(a.x, b.x)) != 0? cmp :
        Float.compare(a.y, b.y);
    }
  };
  /**
   * y comparator: sort vectors by y, then x
   */
  public static final Comparator<PVector> VEC_CMP_Y = new Comparator<PVector>() {
    @ Override public final int compare(final PVector a, final PVector b) {
      int cmp;
      return
        (cmp = Float.compare(a.y, b.y)) != 0? cmp :
        Float.compare(a.x, b.x);
    }
  };
  /**
   * h comparator: sort vectors by heading (angle of rotation from origin)
   */
  public static final Comparator<PVector> VEC_CMP_HEAD = new Comparator<PVector>() {
    @ Override public final int compare(final PVector a, final PVector b) {
      return Float.compare(a.heading(), b.heading());
    }
  };
  /**
   * m comparator: sort vectors by magnitude (distance from origin)
   */
  public static final Comparator<PVector> VEC_CMP_MAG = new Comparator<PVector>() {
    @ Override public final int compare(final PVector a, final PVector b) {
      return Float.compare(a.mag(), b.mag());
    }
  };

  /**
   * random comparator: example of writing a custom sorting comparator.
   * Use with:
   *
   *   VecArrayTool.sort(vecs, VEC_CMP_RANDOM);
   */
  public static final Comparator<PVector> VEC_CMP_RANDOM = new Comparator<PVector>() {
    @ Override public final int compare(final PVector a, final PVector b) {
      return (Math.random()<0.5) ? -1 : 1;
    }
  };
    
  /**
   * Center a point array based on its bounds.
   * Returns a new array.
   *
   * @param   vecs   array of vectors
   * @return         a new PVector array centered on 0, 0
   */
  public PVector[] center(PVector[] vecs) {
    PVector ctr = this.getCenter(vecs);
    return this.translate(vecs, -ctr.x, -ctr.y);
  }

  /**
   * Get the rectangular bounds of an array of vectors
   * defined as an array of extrema.
   * 
   * These extrema define two corners of a bounding rectangle.
   * The later terms (xmax, ymax) are a coordinate,
   * not width, height.
   *
   * @param   vecs   array of vectors
   * @return         array of two bounds [(xmin, ymin), (xmax, ymax)]
   */
  public PVector[] getBounds(PVector[] vecs) {
    float xmin = vecs[0].x;    
    float xmax = vecs[0].x;
    float ymin = vecs[0].y;    
    float ymax = vecs[0].y;
    for (int i=1; i<vecs.length; i++) {
      xmin = (xmin < vecs[i].x) ? xmin : vecs[i].x;
      xmax = (xmax > vecs[i].x) ? xmax : vecs[i].x;
      ymin = (ymin < vecs[i].y) ? ymin : vecs[i].y;
      ymax = (ymax > vecs[i].y) ? ymax : vecs[i].y;
    }
    PVector[] results = new PVector[]{
      new PVector(xmin, ymin), 
      new PVector(xmax, ymax)
    };
    return results;
    //return new float[]{xmin, ymin, xmax, ymax};
  }  

  /**
   * Get center of the array of vectors,
   * defined as the center of the x/y bounds.
   *
   * @param   vecs   array of vectors
   * @return         center x,y
   */
  public PVector getCenter(PVector[] vecs) {
    PVector[] bnds = this.getBounds(vecs);
    return PVector.lerp(bnds[0], bnds[1], 0.5f);
  }

  /**
   * Get width of the array of vectors, defined on the x axis.
   *
   * @param   vecs   array of vectors
   * @return         width
   */
  public float getWidth(PVector[] vecs) {
    PVector[] bnds = this.getBounds(vecs);
    return bnds[1].x - bnds[0].x;
  }

  /**
   * Get height of the array of vectors, defined on the y axis.
   *
   * @param   vecs   array of vectors
   * @return         height
   */
  public float getHeight(PVector[] vecs) {
    PVector[] bnds = this.getBounds(vecs);
    return bnds[1].y - bnds[0].y;
  }

  /**
   * Mirror (reflect) an array of vectors by x, or y, or x/y.
   * Returns a new array.
   *
   * Works around the origin.
   * To mirror a point cloud around its local center,
   * first center, then mirror:
   *
   *   VecArrayTool vat = new VecArrayTool();
   *   PVector[] mirrored = vat.mirror(vat.center(vecs), true, false).
   *
   * To preserve the offset of the resulting cloud, save the
   * center and translate back:
   *
   *   VecArrayTool vat = new VecArrayTool();
   *   PVector ctr = vat.getCenter(vecs);
   *   PVector[] mirrored = vat.mirror(vat.center(vecs), true, false).
   *   mirrored = vat.translate(ctr);
   *
   * 
   * @param   vecs   array of vectors
   * @param   x      mirror across x axis? (horizontal mirror)
   * @param   y      mirror across y axis? (vertical mirror)
   * @return  a new array of points in the form {@code PVector[]}
   */
  public PVector[] mirror(PVector[] vecs, boolean x, boolean y) {
    PVector results[] = new PVector[vecs.length];
    for (int i=0; i<vecs.length; i++) {
      float vx = vecs[i].x;
      float vy = vecs[i].y;
      results[i] = new PVector(x?-vx:vx, y?-vy:vy);
    }
    return results;
  }

  //PVector[] rotate(PVector[] vecs) {
  //}

  /**
   * @param   vecs  a PVector array of points
   */
  public void shuffle(PVector[] vecs) {
    Collections.shuffle(Arrays.asList(vecs));
  }

  /**
   * Sort a point array by a comparison method.
   * Modifies in-place.
   *
   * The method may be specified as a mode string or passed in
   * as a comparator object.
   *
   * Modes include:
   *
   *   "x" : sort by x, then y
   *   "y" : sort by y, then x
   *   "h" : sort by heading
   *   "m" : sort by magnitude
   *
   * Calling with an object may also use built-in modes, e.g.:
   *
   *   VecArrayTool.sort(vecs, VecArrayTool.VEC_CMP_MAG);
   *
   * Heading and magnitude are calculated from the origin.
   * Some applications may wish to center the point cloud first
   * before sorting.
   *
   * @param   vecs   array of vectors
   * @param   mode   sorting mode ("x" / "y" / "h" / "m")
   */
  public void sort(PVector[] vecs, String mode) {
    if (mode.equals("x")) {
      this.sort(vecs, VEC_CMP_X);
    } else if (mode.equals("y")) {
      this.sort(vecs, VEC_CMP_Y);
    } else if (mode.equals("h")) {
      this.sort(vecs, VEC_CMP_HEAD);
    } else if (mode.equals("m")) {
      this.sort(vecs, VEC_CMP_MAG);
    } else {
      // leave unsorted
    }
  }
  /**
   * @param   vecs   array of vectors
   * @param   cmp    a {@code Comparator<PVector>}
   */
  public void sort(PVector[] vecs, Comparator<PVector> cmp) {
    Arrays.sort(vecs, cmp);
  }

  /**
   * Return an ArrayList of vectors.
   * 
   * @param   vecs   array of vectors
   * @return  new points in an {@code ArrayList<PVector>}
   */
  public ArrayList<PVector> toArrayList(PVector[] vecs) {
    return new ArrayList<PVector>(Arrays.asList(vecs));
  }

  /**
   * Translate all points in array by an offset.
   * Offset may be defined x, y or as a PVector (x,y).
   * Returns a new array.
   *
   * @param   vecs   array of vectors
   * @param   x      x offset to translate
   * @param   y      y offset to translate
   * @return         new array of vectors
   */
  public PVector[] translate(PVector[] vecs, float x, float y) {
    return this.translate(vecs, new PVector(x, y));
  }
  /**
   * @param   vecs    array of vectors
   * @param   xyoff   PVector x,y offset to translate
   * @return          new array of vectors
   */
  public PVector[] translate(PVector[] vecs, PVector xyoff) {
    PVector[] results = new PVector[vecs.length];
    for (int i=0; i<vecs.length; i++) {
      results[i] = PVector.add(vecs[i], xyoff);
    }
    return results;
  }
}

…and here is a demo sketch. Press . to change sorting styles, +/- to add/remove points, space to shuffle.

import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Comparator;

PVector[] vecs;
VecArrayTool vat;
String[] modes;
int pointcount;
int modenum;

void setup() {
  size(400, 400);
  ellipseMode(CENTER);
  pointcount = 5;
  modes = new String[]{"x", "y", "h", "m"};
  modenum = 0;
  vat = new VecArrayTool();
  vecs = newPoints(5);
}

void draw() {
  background(255);
  vecs = vat.center(vecs);
  vecs = vat.translate(vecs, width/2, height/2);
  for (PVector vec : vecs) {
    ellipse(vec.x, vec.y, 10, 10);
  }
  drawCurve(vecs, color(0));
  pushStyle();
  fill(0);
  text(modes[modenum], 2, height-5);
  popStyle();
}

void keyReleased() {
  if (key==' ') {  // random points
    vecs = newPoints(pointcount);
  }
  if (key=='.') {  // switch sorting mode
    modenum = (modenum+1) % modes.length;
    vat.sort(vecs, modes[modenum]);
  }
  if (key=='+'||key=='=') {  // add point
    pointcount += 1;
    vecs = Arrays.copyOf(vecs, pointcount);
    vecs[pointcount-1] = new PVector((int)random(width), (int)random(height));
  }
  if (key=='-'||key=='_') {  // drop point
    if(pointcount > 2){
      pointcount -=1;
      vecs = Arrays.copyOf(vecs, pointcount);
    }
  }
  if (key=='m') {  // mirror horizontally
    vecs = vat.mirror(vecs, true, false);
  }
}

void drawCurve(PVector[] vecs, int c) {
  pushStyle();
  noFill();
  stroke(c);
  beginShape();
  curveVertex(vecs[0].x, vecs[0].y);
  for (int i=0; i<vecs.length; i++) {
    curveVertex(vecs[i].x, vecs[i].y);
  }
  curveVertex(vecs[vecs.length-1].x, vecs[vecs.length-1].y);
  endShape();
  popStyle();
}

PVector[] newPoints(int count) {
  PVector[] results = new PVector[count];
  for (int i=0; i<count; i++) {
    results[i] = new PVector((int)random(width), (int)random(height));
  }
  return results;
}

Edit
To make the VecArrayTool.pde a .java file instead:

  1. change extension name to .java
  2. drop keyword “static” from the class line
  3. add required imports to the file:
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Comparator;
import processing.core.PVector;
1 Like

Nice sorting collection there Jeremy! :+1:

However, there are some few glitches there if we place it inside a “VecArrayTool.java” file though: :sweat:

There are 1 bug + 1 glitch at that class declaration above! :bug:

  1. Bug: Java doesn’t allow a top-level class to be redundantly declared as static! All top-level classes are implicitly static already. :flushed:
  2. Glitch: You’ve forgotten to declare VecArrayTool as public! Interestingly, as long as there’s no package statement for the “.java” file, VecArrayTool can be accessed by n1 AFAIK. :money_mouth_face:

Have you actually tested whether your VEC_CMP_RANDOM Comparator actually works? :thinking:

Besides never having a 0 returned, comparing the same PVector can return a diff. value if they happen to be re-compared. :face_with_thermometer:

IMO, using such Comparator as the 2nd argument for sort() will surely throw an IllegalArgumentException, b/c it violates the Comparator’s contract so hard! :dizzy_face:

Thanks, I was wrong when I said

but I should have said “to paste into a PDE tab” – oops. For the .java file version you need to drop the class static AND add a list of imports. I will add instructions for that above.

The random comparator works fine. You can test it by adding

a test to sort()

    } else if (mode.equals("r")) {
      this.sort(vecs, VEC_CMP_RANDOM);

and change the mode list:

  modes = new String[]{"r"};

then press . repeatedly to for new random sorts.

I’m not sure that it violates the contract. A Comparator returns a judgement on two things, and that judgement must be positive, 0, or negative. You could write a comparator “alwaysless” that always declares the second thing less, and that would be perfectly valid. The assumption that comparisons are stable, repeatable, and possibly symmetrical is important to some sorting algorithms and could cause problems, but in this case that isn’t important and isn’t happening.

If you find a bug with it or if you have ideas for making that more performant then I welcome suggestions.

Re:public – yes, that doesn’t matter in PDE, which makes accessible by default – including .java class files with no public declaration – but it is untidy in a file with public on other lines – I added it back. As I mentioned, I’m translating this out of a library under development – in the original, the package statement is package com.jeremydouglass.toolboxing.points;

Whether it violates or not, it didn’t throw any exceptions as I was fearing. :woozy_face:
But why have you left the random mode sort() unused? :zipper_mouth_face:

PDE doesn’t interfere on “.java” files in any way. It is as I stated before: :face_with_monocle:

And if I add that package statement to the “VecArrayTool.java” file, the “.pde” side won’t compile if class VecArrayTool isn’t declared as public as well: :confounded:

The type com.jeremydouglass.toolboxing.points.VecArrayTool is not visible

Only because I provided a simple, short demo. I also left other features of the tool unused as well, including getting bounds, etc, etc. When exploring comparative sorting orders in the demo sketch, I found including random mode to be confusing for the user (me) – it is easier visually to flip back and forth between each of the other stable sorts to understand what they are doing comparatively to the same points, without changing the points periodically.

Exactly. That’s why package statements weren’t in the instructions and haven’t been added to them – you definitely shouldn’t do that.

The whole idea of transforming the PDE snippet back into a full package-declared resource with public qualification etc. is a bit silly – it is ALREADY originally part of a functioning library written in Java, I was just translating it out of that into a PDE cut-paste. If you want it as Java to use in Eclipse / IntelliJ, just request a preview of the library. For everybody else – cut-paste in PDE, and anything else is muddying the waters.