P: 8

Hi everyone. I have 3 arrays of doubles that represent 3D coordinates. The arrays are of 8000 points so I put here a little example.
x = { 0.3 , 0.6 , 0.2} y = {2.0 , 0.3 , 0.2} z = {1.0 , 2.0 , 3.0}
So x(0),y(0),z(0) is a 3D point x(1),y(1),z(1) is another 3D point and so on. What I would like to do is to sort the 3D points in space from the closest to (0,0,0), so the 3 arrays are simultaneously sorted but maintaining the fact that x(i),y(i),z(i) is a 3D point. I've seen that it can be made for 2 arrays using array.sort(x,y) where x is sorted and y is recolocated following x index.
Can this be done for the 3 arrays?
(Hope I've explained myself :P ) Many thanks.
 
Share this Question
100+
P: 579

Hi everyone. I have 3 arrays of doubles that represent 3D coordinates. The arrays are of 8000 points so I put here a little example.
x = { 0.3 , 0.6 , 0.2} y = {2.0 , 0.3 , 0.2} z = {1.0 , 2.0 , 3.0}
So x(0),y(0),z(0) is a 3D point x(1),y(1),z(1) is another 3D point and so on. What I would like to do is to sort the 3D points in space from the closest to (0,0,0), so the 3 arrays are simultaneously sorted but maintaining the fact that x(i),y(i),z(i) is a 3D point. I've seen that it can be made for 2 arrays using array.sort(x,y) where x is sorted and y is recolocated following x index.
Can this be done for the 3 arrays?
(Hope I've explained myself :P ) Many thanks.
I don't think so
 
P: 8

Well I've done it. Just a bit of thinking and some auxiliar arrays, albeit lot of memory usage, here's the code:  Dim x() As Double = {3.0, 2.0, 1.0}

Dim y() As Double = {4.0, 5.0, 6.0}

Dim z() As Double = {1.0, 3.0, 2.0}

Dim auxx() As Double

Dim auxy() As Double

Dim auxz() As Double


ReDim auxx(UBound(x))

x.CopyTo(auxx, 0)

Array.Sort(x, y)

Array.Sort(auxx, z)


ReDim auxy(UBound(y))

y.CopyTo(auxy, 0)

Array.Sort(y, x)

Array.Sort(auxy, z)


ReDim auxz(UBound(z))

z.CopyTo(auxz, 0)

Array.Sort(z, x)

Array.Sort(auxz, y)
And the output is:
x={3.0, 1.0, 2.0} y={4.0, 6.0, 5.0} z={1.0, 2.0, 3.0}
Which if you make some calcs the module of {x(i), y(i), z(i)} is sorted by its proximity to {0, 0, 0}
Hope this weird question helps someone.
  Expert 5K+
P: 8,434

Seems as though the simplest thing would be to combine the arrays into a single array of userdefined type. In other words, something like...  Type CoordTyp

X As Double

Y As Double

Z As Double

Distance As Double

End Type


Dim CoOrd(1 to 8000) As CoordTyp
Then, once your array is populated with the X/Y/Z values, I'd suggest you fill in the Distance values, then sort the CoOrd array based on that field.
 
P: 8

Seems as though the simplest thing would be to combine the arrays into a single array of userdefined type. In other words, something like...  Type CoordTyp

X As Double

Y As Double

Z As Double

Distance As Double

End Type


Dim CoOrd(1 to 8000) As CoordTyp
Then, once your array is populated with the X/Y/Z values, I'd suggest you fill in the Distance values, then sort the CoOrd array based on that field.
Yeah that seems a much more elegant way.
I don't know what kind of algorithm does the sort function use in order to evaluate the efficiency of both codes. Your proposal only has 1 sort call but needs to do (x^2 + y^2 + z^2) ^ 0.5 for all points to calculate distances. I'll have to check both codes but at first sight (not knowing what the sort function actually does) your code seems much faster ;). Many thanks.
  Expert 5K+
P: 8,434

Yeah that seems a much more elegant way.
I don't know what kind of algorithm does the sort function use in order to evaluate the efficiency of both codes. Your proposal only has 1 sort call but needs to do (x^2 + y^2 + z^2) ^ 0.5 for all points to calculate distances. I'll have to check both codes but at first sight (not knowing what the sort function actually does) your code seems much faster ;). Many thanks.
I'll be interested to hear the result. But surely you need to calculate the distance no matter what the method used, since you want the points sorted by it.
I'm afraid I didn't really take the time to understand your code, but got the impression that it would lose the relationship between the three arrays. I take it this is not the case?
 
P: 8

I'm afraid I didn't really take the time to understand your code, but got the impression that it would lose the relationship between the three arrays. I take it this is not the case?
Well, first of all: many thanks. I've been working on this and making some tries and you're probably right about losing the relationship between arrays. There is something I'm missing and I don't quite understand at all.
This is what I tried to do with my code,and what I understand with array.sort (surely I'm wrong so any help is wellcomed)
If you sort 2 arrays one acting as key, then what I thought is that the key array is sorted and the 2cond array is corresponded to that key array, i.e.
x={3,2,1} y={ a,b,c}
array.sort(x,y)
' output: x={1,2,3} ; y={c,b,a}
Is that correct?
If this is ok. then if you save a copy of the key array before the first sort and reuse that copy in a second sort the 3 arrays should maintain their relationship,i.e
x={3,2,1} y={a,b,c} z={what, is, wrong}
x.copyto(aux,0)
' output: x={3,2,1} aux={3,2,1}
array.sort(x,y)
' output: x={1,2,3} ; y={c,b,a}
array.sort(aux,z)
' output: x={1,2,3} ; z={wrong, is, what}
This actually worked on the example I posted previously but doesn't with larger arrays so there's something wrong I do not actually see.
  100+
P: 103

I'm not sure about the sort method you have but if you want to keep the 3D points together why don’t you use one array  Dim mPoint3d(6, 2) As Double
This is only 7 points but should get the idea across. Access the individual points with the first number and the X,Y,Z axis by the second number. Example: to get the X axis of the 1st point mPoint3d(0,0) or the Y Axis of the 3rd point
mPoint3d(2,1)
  Expert 5K+
P: 8,434

Well, first of all: many thanks. I've been working on this and making some tries and you're probably right about losing the relationship between arrays. There is something I'm missing and I don't quite understand at all.
This is what I tried to do with my code,and what I understand with array.sort (surely I'm wrong so any help is wellcomed)
If you sort 2 arrays one acting as key, then what I thought is that the key array is sorted and the 2cond array is corresponded to that key array...
But surely that's the problem, right there. You are keeping two arrays synchronised. That means they are now completely out of step with the third. In other words, you are moving around your X and Y coordinates, so they no longer correspond to the Z's.
This is why I suggested using a structure that keeps them together. May or may not make a difference to the efficiency, but will certainly be simpler to work with. On the other hand, I'm not familar with the array.sort routine you're using  is it a feature of VB.Net? Can it handle userdefined types like this?
  Expert 5K+
P: 8,434

...Example: to get the X axis of the 1st point mPoint3d(0,0) or the Y Axis of the 3rd point mPoint3d(2,1)
And if you want the numbers to make any sense, start your array at 1 instead of the stupid 0.
Computers, running just about any language, seem to love starting lists, arrays and so on at zero, but this is quite counterintuitive to the human mind. I always recommend starting at 1 so it makes sense to the most important part of the process  you.
 
P: 8

On the other hand, I'm not familar with the array.sort routine you're using  is it a feature of VB.Net? Can it handle userdefined types like this?
I'm using the sort method that is contained in the Array class (I'm programming in Visual Basic 2005 Express). The sorting method is divide and conquer type..(I suppose the algorithm is not the key point).
As I've read the method asumes the type of elements your array has. So if you create an array of integers like
x={1,6,5,3} and you call array.sort(x) the output is x={1,3,5,6}
This method also works with two arrays using one as key values. It sorts the first array (If they are doubles which is my case from lower values to higher) and uses the indexes of the first array to relocate the values of the second array, so they're corresponded.
You can customize the sorting method (for example to sort an array of strings in a keysensitive order) but I have no need to change anything as it works ok for me as it is.
For multidimensional arrays I've seen examples of sorting but I haven't seen a way to sort a multidimensional array using for example one row as the key values.
But surely that's the problem, right there. You are keeping two arrays synchronised. That means they are now completely out of step with the third. In other words, you are moving around your X and Y coordinates, so they no longer correspond to the Z's.
But that's why I save a copy of the X array before sorting. Sorting (X,Y) sorts X array(from lower to higher values) and makes Y indexes to correspond with X ones. If I then use a copy of X array (which I made before sorting) to sort Z, the copy of X and X itself should be sorted in the same way and, as are used as key indexes, X, Z and Y should keep their correspondence. I still cannot see the problem. :(
  Expert 5K+
P: 8,434

...But that's why I save a copy of the X array before sorting. Sorting (X,Y) sorts X array(from lower to higher values) and makes Y indexes to correspond with X ones. If I then use a copy of X array (which I made before sorting) to sort Z, the copy of X and X itself should be sorted in the same way and, as are used as key indexes, X, Z and Y should keep their correspondence. I still cannot see the problem. :(
Um... I guess so.
Well, if your technique is sound then the problem must lie in the implementation. But I still don't see how this help, if you wanted the coordinates sorted by distance from the zero point.
Personally I would just calculate the distance for each point then throw the array (the combined structure) into a Quicksort routine. Calculating the distances doesn't have to be done all at once. Perhaps it could be done whenever the coordinates are set or changed.
Um... I wonder, how would it go if you simply added together the X/Y/Z values to get a relative "distance" value, without bothering about the squares? If it works, it would certainly execute faster than computing the real distance.
  Expert 5K+
P: 8,434

Update: I tried displaying some values from a quick X+Y, side by side with SQR(X^2+Y^2). As you'd expect they weren;'t the same, except when X or Y was zero. How precise does the distance sort need to be?
  Expert 5K+
P: 8,434

Update: I tried displaying some values from a quick X+Y, side by side with SQR(X^2+Y^2). As you'd expect they weren;'t the same, except when X or Y was zero. How precise does the distance sort need to be?
Another update: Averaging the X/Y values seems to provide a better result, still without the expensive squares and roots.
 
P: 8

Um... I wonder, how would it go if you simply added together the X/Y/Z values to get a relative "distance" value, without bothering about the squares? If it works, it would certainly execute faster than computing the real distance.
Once again, many many thanks. I should explain further what I'm working in so you get a better idea. I have a point cloud that comes from a laser scanner in a text file which is updated periodically. I have to process that data in order to triangulate those points, remove some surfaces and other things. As you may have noticed Basic won't probably be the language I'll use to implement those algorithms because I need them to run as fast as possible. But meanwhile project goes on I'm just playing a bit with Basic and making some tries.
Returning to the arraysortthing, the values I've got can be positive or negative.(if I understand your suggestion) if you have for example this two points: p1={1,1,0}
and p2={1,1,0}, they're both at the same distance from the origin but adding the coordinates doesn't produce the same result.
  100+
P: 103

Sounds like you need to calculate the distance from 0,0,0 to your point then sort you arrays baste on that value to me.
  100+
P: 103

I search for a formula to calculate the distance between two 3D points and found this page: www.geocities.com/SiliconValley/2151/math3d.html
Here is the formula you would need to calculate the distance I copied it from the web page listed above:
"The distance between two points <Ax,Ay,Az> and <Bx,By,Bz> can be found by again using the pythagorus theorem:
dx = AxBx
dy = AyBy
dz = AzBz
distance = sqrt(dx*dx + dy*dy + dz*dz)"
  Expert 5K+
P: 8,434

...Returning to the arraysortthing, the values I've got can be positive or negative.(if I understand your suggestion) if you have for example this two points: p1={1,1,0} and p2={1,1,0}, they're both at the same distance from the origin but adding the coordinates doesn't produce the same result.
Oops! I was assuming all positive values.
I suppose you might try using the absolute value (ABS function)  it's probably still faster than using squares and roots.
What are the boundaries and granularity (if that's the correct term) of your numbers? Because I'm thinking that the fastest way to "calculate" the distance from the midpoint might be to simply look it up in a threedimensional array. In other words, calculate them all once, and cache the results in an array. Then you just use your coordinates as indeces into the array.
But of course this is probably only feasible for relatively small possible coordinates.
  Expert 5K+
P: 8,434

I search for a formula to calculate the distance between two 3D points and found this page:
...
Thanks for the input, Tig. The main problem is the sorting, as the coordinates are currently held in three separate arrays, complicating synchronisation.
I have suggested a way to handle the sorting by using a structure, now I think we're really just playing around with alternatives. (If the final algorithm needs to be translated to some other language, as intimated, then perhaps the combined X/Y/Z structure won't translate over and will actually require the three arrays.)
    Question stats  viewed: 3014
 replies: 18
 date asked: Apr 2 '07
