Sort a set of 3D points

[Rasoul77]

Is that possible to add an example code to show how one can use this octree package in order to sort a set of 3D points based on, for example Ecuadorian distance metric?

[jcranch]

I'm not sure I completely understand the question. Let me guess what you mean.

You've got a set of points x_1, ..., x_n in 3D, constrained to lie on a sphere. You also have another point y, and you want to sort the points x_1, ..., x_n based on how far they are, in great circle distance, from y.

But, on a sphere, while Euclidean distance is not the same as great circle distance, they're directly related: you can just sort them in order of how close they are in Euclidean distance from y and get the same answers.

[Rasoul77]

Thanks for the quick reply! :) Let me explain my problem: I have a set of 3D points, SET = {(x0, y0, z0), ..., (x_n, y_n, z_n)}, I want to sort them like this:

1. Select a random point from SET, let's name it Query, and remove Query from SET,
2. Create another empty set, let's name it SORTED,
3. Add Query to SORTED, so SORTED = {Query},
4. Find the closest point in SET to Query, if success, then let's name it CLOSEST, if not, go to 9
5. Add CLOSEST to SORTED,
6. Remove CLOSEST from SET,
7. Query <- CLOSEST,
8. Go to 4
9. Done

[jcranch]

It would be possible to add advice on doing that, but I haven't yet seen why that's a natural thing to do.

You should be able to implement the algorithm you describe (using the nearest_to_point method in Octree to find the nearest point).

[jcranch]

What you're trying to do is the so-called "nearest neighbour algorithm", right? The greedy approximation for the travelling salesman problem?