# How to sort coordinates?
**URL:** https://discourse.processing.org/t/how-to-sort-coordinates/45599
**Category:** Coding Questions
**Created:** [January 15, 2025, 8:30am UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599 "2025-01-15T08:30:40Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 15, 2025, 8:30am UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/1 "2025-01-15T08:30:40Z")
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!
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 15, 2025, 9:06am UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/2 "2025-01-15T09:06:56Z")
What mode are you using Java, p5js, Python… ?
What are you using to rperesent [x,y] dots., PVector, array tuples, user defined class … ?
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 15, 2025, 2:20pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/3 "2025-01-15T14:20:42Z")
i use java mode.
and IntList x, y arrays
---
### Author:  [@GoToLoop](https://discourse.processing.org/u/GoToLoop)
#### Post date: [January 16, 2025, 2:14am UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/4 "2025-01-16T02:14:44Z")
Proper ways to do sorting in Java is by instantiating a Comparator w/ a **compare()** callback method:
> [@Sorting an array](https://discourse.processing.org/t/sorting-an-array/20992/4):
>
> [Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html#compare(T,T)](http://Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html#compare(T,T))[Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html#reversed()](http://Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html#reversed())[Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html#sort(T[],java.util.Comparator)](http://Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html#sort(T%5B%5D,java.util.Comparator)) // https://Discourse.processing.org/t/sorting-an-array/20992/4 // GoToLoop (2020/May/18) import java.util.Arrays; import java.util.Comparator; final PVector[] vecs = { new PVector(100, -100), new PVector…
Or defining a Comparable class w/ a **compareTo()** callback method:
> [@The operator \> is undefined for the argument - HOW TO RESOLVE ERROR (OOP)](https://discourse.processing.org/t/the-operator-is-undefined-for-the-argument-how-to-resolve-error-oop/38705/6):
>
> If you wish you can take a look at a very old deck of cards implementation I did a long time ago: [Picking cards at random, then excluding those from further picking. - Processing 2.x and 3.x Forum](https://forum.Processing.org/two/discussion/2801/picking-cards-at-random-then-excluding-those-from-further-picking-#Item_2) It’s split into 2 sketches: 1 creates & saves the “.csv” file, while the other loads it and makes a deck of cards out of it. For convenience I’ve merged them now into 1 sketch w/ 4 “.pde” tabs: “Table\_CSV\_Card\_Pack.pde”: /\*\* \* Table CSV Card Pack (v1.0.1) \* by GoToLoop (2022/Sep/13) \* \* htt…
> [@What does "Error on int" mean?](https://discourse.processing.org/t/what-does-error-on-int-mean/42264/13):
>
> Now I understand why you wanted findClosestPaletteColor() to be a regular instance method: You’ve got rid of its 1st parameter! Instead the previous parameter became a clone of the current C3 instance. Just so you know, you can keep both static & non-static versions for findClosestPaletteColor(). And those new r(), g() & b() helper functions can be converted to static inside C3Base: static abstract class C3Base { static final color r(final color c) { return c \>\> 020 & 0xff; } sta…
But given you’re using 2 [IntList](https://processing.org/reference/IntList.html) 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()**](https://processing.org/reference/IntList_size_.html) by using the bitshift operators [`<<`](https://processing.org/reference/leftshift.html) & [`>>`](https://processing.org/reference/rightshift.html); then call method [**sort()**](https://processing.org/reference/IntList_sort_.html) and then split the single container back to **x** & **y** containers:
```java
/**
* 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]);
}
}
```
```auto
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]
```
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 16, 2025, 2:30pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/5 "2025-01-16T14:30:45Z")
@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
```auto
Original coordinates
[5, 5] [3, 4] [2, 5] [4, 4] [5, 4]
Sorted coordinates
[2, 5] [3, 4] [4, 4] [5, 4] [5, 5]
```
```Processing
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;
}
```
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 2:33pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/6 "2025-01-16T14:33:23Z")
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!
---
### Author:  [@eightohnine](https://discourse.processing.org/u/eightohnine)
#### Post date: [January 16, 2025, 2:52pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/7 "2025-01-16T14:52:01Z")
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?
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 16, 2025, 2:55pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/8 "2025-01-16T14:55:53Z")
This is not a trivial problem and creating an efficient algorithm to solve this depends on many things.
1. The maximum number of points to be stored. If there is no definitive maximum number then typically how many will there be?
2. Are the coordinate values always integers?
3. Is there a predefined range of acceptable x and y values e.g. (0 - 3000)?
4. In your diagram it appears that only touching points are considered neighbours. If that is correct then the point much have a physical size. You need to explain what constitutes a neighbour.
5. If the points have a physical size then then is it the same for all points?
> [@AniManOtaku](#):
>
> There is an array of points it can be a PVector or IntList (x, y), it doesn’t matter.
It does matter especially if sorting is to be part of the algorithm. That is why I asked the question in my first post.
---
### Author:  [@GoToLoop](https://discourse.processing.org/u/GoToLoop)
#### Post date: [January 16, 2025, 2:58pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/9 "2025-01-16T14:58:08Z")
> [@quark](#):
>
> It does this by combining the `x` and `y` values into a single `long` values.
Container IntList can’t store `long` ranged values:
> **[IntList / Reference](https://processing.org/reference/intlist)**
>
> Helper class for a list of int values. Lists are designed to have some features of ArrayList, but to maintain the simplicity and efficiency of working with arrays. Functions such as s…
Therefore I’m merging `x` & `y` pairs as 1 `int` value.
> [@quark](#):
>
> … but not with negative integers.
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.
---
### Author:  [@eightohnine](https://discourse.processing.org/u/eightohnine)
#### Post date: [January 16, 2025, 3:09pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/10 "2025-01-16T15:09:40Z")
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.
```Processing
import controlP5.*;
ControlP5 cp5;
int numPoints = 100;
float cutoff = 100;
ArrayList points = new ArrayList<>();
ArrayList 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 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 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 points;
Line(ArrayList points) {
this.points = points;
}
void draw() {
noFill(); // Ensure no fill for the lines
beginShape();
for (Point p : points) {
vertex(p.x, p.y);
}
endShape();
}
}
```
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 16, 2025, 3:13pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/11 "2025-01-16T15:13:12Z")
> [@GoToLoop](#):
>
> Container IntList can’t store `long` ranged values:
I never said it did. The sorting function creates a local array of type `long` and each element holds a single coordinate pair.
> [@GoToLoop](#):
>
> 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`.
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.
---
### Author:  [@GoToLoop](https://discourse.processing.org/u/GoToLoop)
#### Post date: [January 16, 2025, 3:27pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/12 "2025-01-16T15:27:08Z")
> [@quark](#):
>
> … both of our original solutions are now purely academic.
Indeed… 🤣
> [@quark](#):
>
> The sorting function creates a local array of type `long` and each element holds a single coordinate pair.
Still in my solution, the merged pair is of primitive datatype `int` stored in Processing’s IntList container:
> [@GoToLoop](#):
>
> ```auto
> static final int xyMerge(final int... xy) {
> return xy[0] << 16 | (char)xy[1];
> }
>
> ```
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.
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 3:38pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/13 "2025-01-16T15:38:46Z")
I’ve tried to do this before, but I’m not sure my code works fast enough.
```Processing
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
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 3:42pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/14 "2025-01-16T15:42:15Z")
1. the points can be as many as 1,000,000 or even more, so as I said I need a fast algorithm.
2. Cordinate numbers are always integer.
3. The range is from 0 to 10,000.
4. Neighboring points are those that touch each other. That is, the distance between dot1 and dot2 \<= diameter.
5. They all have the same diameter.
Also, multiple points cannot have the same cordinates.
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 3:45pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/15 "2025-01-16T15:45:06Z")
> [@quark](#):
>
> It does matter especially if sorting is to be part of the algorithm. That is why I asked the question in my first post.
I mean it doesn’t matter for me what to use.
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 16, 2025, 3:46pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/16 "2025-01-16T15:46:55Z")
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?
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 3:54pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/17 "2025-01-16T15:54:54Z")
Yeah, the diameter can’t be really big, no more than 300. And the dots don’t move.
---
### Author:  [@eightohnine](https://discourse.processing.org/u/eightohnine)
#### Post date: [January 16, 2025, 3:55pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/18 "2025-01-16T15:55:08Z")
> [@AniManOtaku](#):
>
> Neighboring points are those that touch each other. That is, the distance between dot1 and dot2 \<= diameter.
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?
---
### Author:  [@AniManOtaku](https://discourse.processing.org/u/AniManOtaku)
#### Post date: [January 16, 2025, 4:03pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/20 "2025-01-16T16:03:26Z")
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.
---
### Author:  [@quark](https://discourse.processing.org/u/quark)
#### Post date: [January 16, 2025, 5:29pm UTC](https://discourse.processing.org/t/how-to-sort-coordinates/45599/21 "2025-01-16T17:29:54Z")
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
- there are 40,000 points
- each point has a diameter of 50
- the domain coordinates (x and y) are in the range ≥0 and \<16384
The domain range was chosen to be a power of 2 in this case 2^{14}=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
```auto
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
```auto
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
[Next page](https://discourse.processing.org/t/how-to-sort-coordinates/45599.md?page=2)