How to sort coordinates?

Processing Coding Questions
22

I wrote the code and I was able to sort 10000 points in 30 seconds which is pretty good, but is there a faster way?
I used a loop for and checked for each point the closest to it in the chunk. In this way, I stored the points that were supposed to form lines in the array.
( Unfortunately the code was accidentally deleted and I can’t leave it here)

23

Did you mean 30 milliseconds?

Interesting with my code, shown below, I got this result

Population size = 10000
Number of tests without CSP  49995000
Number of tests with CSP  12049
Create domain, points and connection tests took 8 milliseconds

Sketch

import java.util.*;

final int DOMAIN_SIZE = (int) Math.pow(2, 14);
final int CELL_SIZE = (int) Math.pow(2, 8);
final int GRID_SIZE = DOMAIN_SIZE / CELL_SIZE;
final int POINT_SIZE = 50;

final int NBR_POINTS = 10000;

Domain domain;

public void setup() {
  size(400, 400);
  int time = millis();
  println("Population size = " + NBR_POINTS);
  println("Number of tests without CSP ", (NBR_POINTS *(NBR_POINTS-1)/2) );
  domain = new Domain(DOMAIN_SIZE, CELL_SIZE);
  domain.populateRandomly(NBR_POINTS);
  domain.findConnections();
  println("Create domain, points and connection tests took " + (millis() - time) + " milliseconds");
  // At this stage every point in domain.population contains a set of points
  // it is connected to. Note connections are 2-way, if p0 --> p9 then p9 --> p0
}

public void exit() {
  super.exit();
}

public class Point {
  int x, y;
  HashSet<Point> connected;

  Point(int x, int y) {
    this.x = x;
    this.y = y;
    this.connected = new HashSet<Point>();
  }

  boolean connectsTo(Point p) {
    return Math.abs(this.x - p.x) <= POINT_SIZE
      && Math.abs(this.y - p.y) <= POINT_SIZE;
  }

  void addConnection(Point p) {
    connected.add(p);
  }
}

public class Cell {
  ArrayList<Point> points;

  Cell() {
    points = new ArrayList<Point>();
  }

  void addPoint(Point p) {
    points.add(p);
  }
}

public class Domain {
  Cell [][] grid;
  ArrayList<Point> population = new ArrayList<Point>();
  int domainSize, cellSize;

  Domain(int dsize, int csize) {
    this.domainSize = dsize;
    this.cellSize = csize;
    int grid_size = dsize / csize;
    grid = new Cell[grid_size][grid_size];
    for (int i = 0; i < grid_size; i++)
      for (int j = 0; j < grid_size; j++)
        grid[i][j] = new Cell();
  }

  void populateRandomly(int nbr) {
    for (int i = 0; i < nbr; i++) {
      Point p = new Point((int)random(1, domainSize-1),
        (int)random(1, domainSize-1));
      addPoint(p);
      population.add(p);
    }
  }

  void addPoint(Point p) {
    grid[p.x >> 8][p.y >> 8].addPoint(p);
  }

  void findConnections() {
    int ntests = 0;
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[i].length; j++) {
        ArrayList<Point> pts = grid[i][j].points;
        int nbr = pts.size();
        if (nbr > 1) {
          for (int m = 0; m < nbr - 1; m++) {
            Point pm = pts.get(m);
            for (int n = m+1; n < nbr; n++) {
              Point pn = pts.get(n);
              if (pm.connectsTo(pn)) {
                pm.addConnection(pn);
                pn.addConnection(pm);
              }
              ntests++;
            }
          }
        }
      }
    }
    println("Number of tests with CSP  " + ntests);
  }
}
2 Likes
25

Sorry I must have just written bad code. Thanks for your help!

26

Nothing to apologise for :smile: I have been programming for decades and at one time I wouldn’t have known where to start with this problem.

Don’t forget all programmers no matter how experienced they are now started from scratch. :grinning:

2 Likes