sorting algorithm - acc coordinates

Could someone please advise or give some insights what would be the best way to sort many 3d points according their x, y, z position.

Suppose I have a large box with many points. Now I want get information how many points are in each part of the box. Assume I split the box into many small boxes 100x100x100, i.e. first box will be 0..100 x 0..100 x 0..100, the second one 100..200 x 0..100 x 0..100, and so on. I can iterate now through all the random points and get their x, y, z position, and increase counter in the specific box if the point is within its boundaries.

What would be the best way to start from?
Divide by 100
I am sorry I don't understand. How exactly I can avoid writing many many if statements?
1
2
3
int counter_box0 = 0;
if (x < 100 & y < 100 & z <100)
     counter_box0 ++;

and so for each box
If you can define the property that makes one point "less than" another, so if point p1 < point p2 then p1 comes before p2 in the sorted result, then you can just use std::sort.
well, do you *have* to use boxes? what is your real goal? If you can use 'rings' (slices based off distance from a handy "as if" 0,0,0 point ) that is a much easier problem. Square things don't play as nice in 3-d as round things.

If you can't do that, and it has to be boxes, then you deal with it.
here, if you just want to count (counting is easy, most everything else is not compared to rings/radii splitup) the # in a box...
for(all the points)
{
// what box is it in?
//increment that
}
ok, so now we have a problem, what box is it in?
its in box / 100, sort of.
that is, if your boxes are arranged
[0][0][0] //all < 100
[0][0][1] // <100, < 100, 100-200
[0][1][0] // <100, 100-200, <100
...
[3][4][5]//300-400, 400-500, 500-600
... etc
or something like that (the way you arrange them is arbitrary)
then division by 100 gives you the answer, as stated (without explains):
boxes[x/100][y/100][z/100] ++;
where
int boxes[max_x][max_y][max_z]{};
see how box in {350,420,555} goes into [3][4][5] counter?
Last edited on
yes! thank you very much. I felt it should be smth like that, but could not see the obvious
Topic archived. No new replies allowed.