473,325 Members | 2,442 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Anyone know how to sort 3 arrays?

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.
Apr 2 '07 #1
18 3356
vijaydiwakar
579 512MB
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
Apr 2 '07 #2
Well I've done it. Just a bit of thinking and some auxiliar arrays, albeit lot of memory usage, here's the code:

Expand|Select|Wrap|Line Numbers
  1.         Dim x() As Double = {3.0, 2.0, 1.0}
  2.         Dim y() As Double = {4.0, 5.0, 6.0}
  3.         Dim z() As Double = {1.0, 3.0, 2.0}
  4.         Dim auxx() As Double
  5.         Dim auxy() As Double
  6.         Dim auxz() As Double
  7.  
  8.         ReDim auxx(UBound(x))
  9.         x.CopyTo(auxx, 0)
  10.         Array.Sort(x, y)
  11.         Array.Sort(auxx, z)
  12.  
  13.         ReDim auxy(UBound(y))
  14.         y.CopyTo(auxy, 0)
  15.         Array.Sort(y, x)
  16.         Array.Sort(auxy, z)
  17.  
  18.         ReDim auxz(UBound(z))
  19.         z.CopyTo(auxz, 0)
  20.         Array.Sort(z, x)
  21.         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.
Apr 2 '07 #3
Killer42
8,435 Expert 8TB
Seems as though the simplest thing would be to combine the arrays into a single array of user-defined type. In other words, something like...

Expand|Select|Wrap|Line Numbers
  1. Type CoordTyp
  2.   X As Double
  3.   Y As Double
  4.   Z As Double
  5.   Distance As Double
  6. End Type
  7.  
  8. 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.
Apr 8 '07 #4
Seems as though the simplest thing would be to combine the arrays into a single array of user-defined type. In other words, something like...

Expand|Select|Wrap|Line Numbers
  1. Type CoordTyp
  2.   X As Double
  3.   Y As Double
  4.   Z As Double
  5.   Distance As Double
  6. End Type
  7.  
  8. 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.
Apr 9 '07 #5
Killer42
8,435 Expert 8TB
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?
Apr 9 '07 #6
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.
Apr 11 '07 #7
Tig201
103 100+
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
Expand|Select|Wrap|Line Numbers
  1. 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)
Apr 11 '07 #8
Killer42
8,435 Expert 8TB
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 user-defined types like this?
Apr 11 '07 #9
Killer42
8,435 Expert 8TB
...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 counter-intuitive to the human mind. I always recommend starting at 1 so it makes sense to the most important part of the process - you.
Apr 11 '07 #10
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 user-defined 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. :(
Apr 12 '07 #11
Killer42
8,435 Expert 8TB
...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.
Apr 12 '07 #12
Killer42
8,435 Expert 8TB
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?
Apr 12 '07 #13
Killer42
8,435 Expert 8TB
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.
Apr 12 '07 #14
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 array-sort-thing, 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.
Apr 12 '07 #15
Tig201
103 100+
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.
Apr 12 '07 #16
Tig201
103 100+
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 = Ax-Bx
dy = Ay-By
dz = Az-Bz
distance = sqrt(dx*dx + dy*dy + dz*dz)"
Apr 12 '07 #17
Killer42
8,435 Expert 8TB
...Returning to the array-sort-thing, 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 mid-point might be to simply look it up in a three-dimensional 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.
Apr 13 '07 #18
Killer42
8,435 Expert 8TB
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.)
Apr 13 '07 #19

Sign in to post your reply or Sign up for a free account.

Similar topics

13
by: Gram | last post by:
Hello, Can anyone help out with a bubble sort for strings using ASP? I have a text file of words id like to sort and count. Thanks in advance for any help. Gram.
6
by: Xiaozhu | last post by:
say, if you had parallel arrays containing the sales person id, the month, and the sales figures (for that person in that month), sorting on sales figure and preserve the order of figures within...
36
by: HERC777 | last post by:
just paste the below into notepad, call it iqsort.html double click it and your IE browser will run it. (neat! a universal programming language we can all run!) it falls out from the sort...
1
by: strotee | last post by:
#include <iostream> #include <ctime> using namespace std; // function declarations void swap(int *a, int *b); void sort(int arr, int beg, int end); int main() {
3
by: cpuracr8 | last post by:
i've been looking through the topics here and i can't quite find one that helps me. i'm trying to sort a struct that contains three arrays using the sort() function. the three arrays are parallel...
6
by: Ali Chambers | last post by:
Hi, I have a two arrays that I wish to sort. One is the index array (full of floating point values). The other is a string array: ARRAY 1 ARRAY 2 ------- -------- -1.2 textA 12 textB...
21
by: yeti349 | last post by:
Hi, I'm using the following code to retrieve data from an xml file and populate a javascript array. The data is then displayed in html table form. I would like to then be able to sort by each...
22
by: AB | last post by:
Hello All, I'm trying to replicate a general purpose sort function (think qsort) void sort(void *arr, const int num, size_t size, int (*cmp)(void *a, void *b)) { int i = 0 ; int j = 0 ;
10
by: ikarus | last post by:
Hello C++ Gurus! I'm comparing sorting algorithm for study goals. I've compared STL std::sort and hand-coded introsort on millions (tens of millions) of integers array sorting. It was tested...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.