Is there any way to quickly sort the cordinates of dots?
I have an array of Vertex dots[ ] I need to sort it so that the index neighbors are also neighboring dots.
Example:
Input: (5,5)(3,4)(2,5)(4,4)(5,4)
Output: (2,5)(3,4)(4,4)(5,4)(5,5)
Thanks in advance!
What mode are you using Java, p5js, Python… ?
What are you using to rperesent [x,y] dots., PVector, array tuples, user defined class … ?
i use java mode.
and IntList x, y arrays
Proper ways to do sorting in Java is by instantiating a Comparator w/ a compare() callback method:
Or defining a Comparable class w/ a compareTo() callback method:
But given you’re using 2 IntList containers already, and seems like the values within both x & y containers are within short and even the byte range, I’ve come up w/ a hackish solution which merges both containers as 1 container w/ same size() by using the bitshift operators << & >>; then call method sort() and then split the single container back to x & y containers:
/**
* IntList XY Merge (v1.0.0)
* GoToLoop (2025/Jan/15)
* https://Discourse.Processing.org/t/how-to-sort-cordinates/45599/4
*/
final IntList
x = new IntList(5, 3, 2, 4, 5),
y = new IntList(5, 4, 5, 4, 4);
final int[] xyArr = new int[2];
void setup() {
println("input x:", x);
println("input y:", y);
final IntList xy = mergeXYLists(x, y, xyArr);
println("unsorted xy:", xy);
xy.sort();
println("sorted xy:", xy);
splitXYLists(xy, x, y, xyArr);
println("sorted x:", x);
println("sorted y:", y);
exit();
}
static final int xyMerge(final int... xy) {
return xy[0] << 16 | (char)xy[1];
}
static final int[] xySplit(final int xy) {
return new int[] { xy >> 16, (short)(xy & 0xffff) };
}
static final int[] xySplit(final int xy, final int[] split) {
split[0] = xy >> 16;
split[1] = (short)(xy & 0xffff);
return split;
}
static final IntList mergeXYLists(final IntList x, final IntList y) {
return mergeXYLists(x, y, new int[2]);
}
static final IntList mergeXYLists
(final IntList x, final IntList y, final int[] tmp)
{
final int len = x.size();
final IntList xy = new IntList(len);
for (int i = 0; i < len; ++i) {
tmp[0] = x.get(i);
tmp[1] = y.get(i);
xy.append(xyMerge(tmp));
}
return xy;
}
static final void splitXYLists
(final IntList xy, final IntList x, final IntList y)
{
splitXYLists(xy, x, y, new int[2]);
}
static final void splitXYLists
(final IntList xy, final IntList x, final IntList y, final int[] tmp)
{
final int len = xy.size();
for (int i = 0; i < len; ++i) {
xySplit(xy.get(i), tmp);
x.set(i, tmp[0]);
y.set(i, tmp[1]);
}
}
input x: IntList size=5 [ 5, 3, 2, 4, 5 ]
input y: IntList size=5 [ 5, 4, 5, 4, 4 ]
unsorted xy: IntList size=5 [ 327685, 196612, 131077, 262148, 327684 ]
sorted xy: IntList size=5 [ 131077, 196612, 262148, 327684, 327685 ]
sorted x: IntList size=5 [ 2, 3, 4, 5, 5 ]
sorted y: IntList size=5 [ 5, 4, 4, 4, 5 ]
@GoToLoop has provided a completely valid solution to your problem but there is always more than one way of doing something. The sketch below works with all possible positive int values (i.e. 0 - 2147483647 inclusive) but not with negative integers.
It does this by combining the x and y values into a single long values. Then creating an array of long values that can be sorted directly. The sketch output is
Original coordinates
[5, 5] [3, 4] [2, 5] [4, 4] [5, 4]
Sorted coordinates
[2, 5] [3, 4] [4, 4] [5, 4] [5, 5]
import java.util.Arrays;
IntList x = new IntList(5, 3, 2, 4, 5);
IntList y = new IntList(5, 4, 5, 4, 4);
void setup() {
println("Original coordinates");
printCoordArrays(x, y);
sortCoords(x, y);
println("Sorted coordinates");
printCoordArrays(x, y);
}
boolean printCoordArrays(IntList xList, IntList yList) {
if (xList.size() != yList.size()) return false;
for (int i = 0; i < xList.size(); i++)
print(" [" + xList.get(i) + ", " + yList.get(i) + "] ");
println();
return true;
}
/*
Given a pair of IntList variables representing x and y values
for coordinates sort them so that they are in icreasing x order
any coordinate pairs with matching x values will be sorted by
the y value.
This function will work for all positive integers that can be
held in an 'int' data type i..e. all integers in the range
0 to 2147483647 inclusive.
Negative integers will give inconsistant results.
The function returns false if the arrays are of different size
leaving the arrays unchanged, Otherwise the elements of the
x and y arrays are sorted by x then y
*/
boolean sortCoords(IntList xList, IntList yList) {
if (xList.size() != yList.size()) return false;
long[] a = new long[x.size()];
for (int i = 0; i < xList.size(); i++) {
a[i] = (((long)xList.get(i)) << 32) | yList.get(i);
}
Arrays.sort(a);
for (int i = 0; i < xList.size(); i++) {
xList.set(i, (int)( a[i] >> 32));
yList.set(i, (int) a[i]);
}
return true;
}
I’m sorry I’m not explaining things very well. Your code doesn’t work the way I need it to.
There is an array of points it can be a PVector or IntList (x, y), it doesn’t matter. Neighboring points (points that are nearest in radius) must have neighboring indices.
For example:
points 1 2 3 4 are neighbors and form a line, points 5 6 form another line, points 7 8 9 10 another line.
All points are initially stored in the same array in random order.
I need to sort all points quickly and so that neighboring points form lines and have neighboring indices. Or it is possible to divide the line points into separate arrays. For example, create a Line class that contains points.
This is very difficult and unfortunately I don’t know how to do it. I would be very grateful if you could help me somehow!
Given your description of what you are trying to do, I’m now wondering if this is less about sorting indices and more about finding and creating the lines from a set of random points?
My spontaneous approach is to start off with the first point in that list and then iterate against all other points and – checking against a max. distance cutoff – finding the closest one, and then using this new point again finding the the next closest one in the list, rinse and repeat. If no other points are found within that max. distance cutoff, then all collected points up to this moment are considered a line.
After you have found these lines, the initial indices of the individual points seem useless? Unless I’m still misunderstanding what you are trying to do?
This is not a trivial problem and creating an efficient algorithm to solve this depends on many things.
It does matter especially if sorting is to be part of the algorithm. That is why I asked the question in my first post.
Container IntList can’t store long ranged values:
Therefore I’m merging x & y pairs as 1 int value.
Actually it does work (partially) w/ negative values as long as they’re within the 16-bit short range, which is from -32768 to 32767.
However the y part will “malfunction” if it’s negative and the sort order has to be determined by the y part.
The reason for that bug is b/c the y part is converted to unsigned char when being merged.
I’ve quickly prompted ChatGPT to whip together a “lines from random points” inspired sketch.
Important: This is not meant to be a solution. Instead it can be used check if the output is approaching what you had in mind. And it can help define the source problem better and help define the bounding criteria for your sketch.
For example, I immediately see a lot of lines that contain loops, so don’t have optimised pathing.
I also sense a “travelling salesman” type of complexity to this ask.
import controlP5.*;
ControlP5 cp5;
int numPoints = 100;
float cutoff = 100;
ArrayList<Point> points = new ArrayList<>();
ArrayList<Line> lines = new ArrayList<>();
void setup() {
size(800, 800);
// Initialize ControlP5
cp5 = new ControlP5(this);
// Slider for the number of points
cp5.addSlider("numPoints")
.setPosition(20, 20)
.setRange(10, 500) // Min and max values for points
.setValue(numPoints)
.setNumberOfTickMarks(10);
// Slider for the cutoff distance
cp5.addSlider("cutoff")
.setPosition(20, 60)
.setRange(10, 200) // Min and max values for cutoff
.setValue(cutoff)
.setNumberOfTickMarks(10);
generateAndConnectPoints();
}
void draw() {
background(30);
// Draw lines (no fill)
stroke(255);
strokeWeight(1);
for (Line line : lines) {
line.draw();
}
// Draw points
fill(255, 0, 0);
noStroke();
for (Point p : points) {
p.draw();
}
}
void generateAndConnectPoints() {
// Clear existing points and lines
points.clear();
lines.clear();
// Generate random points
for (int i = 0; i < numPoints; i++) {
points.add(new Point(random(width), random(height)));
}
// Find and connect points
while (!allPointsUsed()) {
ArrayList<Point> linePoints = new ArrayList<>();
Point start = findUnusedPoint();
if (start != null) {
Point current = start;
while (current != null) {
linePoints.add(current);
current.used = true;
Point closest = findClosest(current, linePoints);
current = closest; // Move to next point or end if null
}
if (linePoints.size() > 1) {
lines.add(new Line(linePoints));
}
}
}
}
// Called when sliders are adjusted
void controlEvent(ControlEvent theEvent) {
numPoints = (int) cp5.getController("numPoints").getValue();
cutoff = cp5.getController("cutoff").getValue();
generateAndConnectPoints();
redraw();
}
// Find the closest unused point to `current` that isn't in the line already
Point findClosest(Point current, ArrayList<Point> linePoints) {
Point closest = null;
float minDist = cutoff;
for (Point p : points) {
if (!p.used && !linePoints.contains(p)) {
float d = dist(current.x, current.y, p.x, p.y);
if (d < minDist) {
minDist = d;
closest = p;
}
}
}
return closest;
}
// Check if all points are used
boolean allPointsUsed() {
for (Point p : points) {
if (!p.used) return false;
}
return true;
}
// Find an unused point
Point findUnusedPoint() {
for (Point p : points) {
if (!p.used) return p;
}
return null;
}
// Point class
class Point {
float x, y;
boolean used;
Point(float x, float y) {
this.x = x;
this.y = y;
this.used = false;
}
void draw() {
ellipse(x, y, 6, 6);
}
}
// Line class
class Line {
ArrayList<Point> points;
Line(ArrayList<Point> points) {
this.points = points;
}
void draw() {
noFill(); // Ensure no fill for the lines
beginShape();
for (Point p : points) {
vertex(p.x, p.y);
}
endShape();
}
}
I never said it did. The sorting function creates a local array of type long and each element holds a single coordinate pair.
Well spotted and if it could be applied to both the x and y coordinates then it might be worth mentioning.
Of course since the OP has given a much more informative description of the problem then both of our original solutions are now purely academic.
Indeed… 
Still in my solution, the merged pair is of primitive datatype int stored in Processing’s IntList container:
Notice that the x part is left-shifted by 16 bits, which corresponds to type short.
So the returning 32-bit int is composed of 2 merged 16-bit short values.
I’ve tried to do this before, but I’m not sure my code works fast enough.
IntList x=new IntList(),y=new IntList();
IntList sx=new IntList(),sy=new IntList(); //sorted x,y
sx.append(x.get(0));
sy.append(y.get(0));
x.remove(0);
y.remove(0);
boolean stop=false;
int icp=0; //index of current point
IntList priority;
int ibp=0; // index of best priority
while (!stop) {
priority=new IntList();
for (int i=0; i<x.size(); i++) {
int d=round(dist(
sx.get(icp), sy.get(icp),
x.get(i), y.get(i)));
if (abs(sx.get(icp)-x.get(i))==1 &
abs(sy.get(icp)-y.get(i))==1)
priority.append(2);
else if (d==1)
priority.append(d);
else
priority.append(d*2);
ibp=priority.index(priority.min());
}
if (ibp<x.size()) {
sx.append(x.get(ibp));
sy.append(y.get(ibp));
icp++;
x.remove(ibp);
y.remove(ibp);
priority.remove(ibp);
}
if (x.size()==0)
stop=true;
}
( The code mode doesn’t work on android web again. why? )
Also, multiple points cannot have the same cordinates.
I mean it doesn’t matter for me what to use.
Thanks for that information it really helps. Just one more question roughly what size is the diameter. it can’t be too large because of the small range.
Nearly forgot do the points move?
Yeah, the diameter can’t be really big, no more than 300. And the dots don’t move.
Will a point always have either one or two touching neighbours? Or might there also be no touching neighbours or three and more touching neighbours?
Oh, yeah, I know what you mean. Dots usually have one or two neighbors. But sometimes one dot can touch three or more at once, which is really a problem. I’m going to make an algorithm later that removes points that I think are unnecessary. There can be points without neighbors too.
With an 10000 x 10000 range, a point diameter of 300 and 1 million plus random points it will be almost impossible to place the points without a connection from every point to every other point. I suspect that you need to rethink these numbers.
The problem here is similar to collision detection where you what to test each point against every other point. Now if we have n points then the number of tests is n*(n-1)/2 so if n = 1,000,000 there are approximately 500,000,000,000 tests far too much. What we need is a means to reduce the number of tests.
The simplest solution is to use cell space partitioning (CSP).
The following description is to show the potential benefits of CSP. To simplify the situation I have made the following assumptions
The domain range was chosen to be a power of 2 in this case 2^{16}=16384 because it will have benefits later.
The domain has to be split into cells like a chessboard. The cell size should be at least 4 * the point diameter, in this case 200 (4 * 50) but for efficiency we want the grid size to be the next smallest power of 2. So the next power of two greater than 200 is 256 (256 = 2^8)
This means that the domain is like a chess board with 64 cells on each side so lets do the maths.
There are 64*64 = 4096 cells so if the points are evenly distributed there will be approximately 10 points per cell.
So number of testes per cell would be 10*9/2 = 45 so the total number of tests would be 45 * 4096 = 184,320 tests so to summarize
The number of tests would be -
799,980,000 without cell space partitioning and
184,320 with cell partitioning 
I said that using powers of 2 would help efficiency. A quick demonstration using our example.
Consider a point at position [x, y] where both the x and y are integers in the range ≥0 to <16384 and a domain with a cell size of (2^8) we can calculate the 2D position of the cell [cx, cy] using bit manipulation
cx = (x >> 8);
cy = (y >> 8)
we can use this to decide on the cell to store the point.
If needed we can find the position within the cell
mask = (1 << 8) - 1;
px = (x & mask);
py = (y & mask);
To use this approach you would need to create at least three classes
Point - cannot use PVector because the coordinates are stored as floats. It can be a very small class because it is simple a means of storing a position.
Cell - each cell must have its own list of Points
Domain a 2D grid of cells