Algorithm to compare number sets (Mind bender????) 1

[TheInsider]

Hi,
I have the following dilemma:

I want to compare sets of 2 or 3 numbers with each other to find the closest match. Lets say I want to compare 2 numbers for the following example. I have a multi-dimensional array X[5][2] containing the following arbitrary data:

X[0][0] = 1, X[0][1] = 2
X[1][0] = 2, X[1][1] = 4
X[2][0] = 5, X[2][1] = 8
X[3][0] = 7, X[3][1] = 9
X[4][0] = 3, X[4][1] = 1

Therefore my sets are:

(1, 2)
(2, 4)
(5, 8)
(7, 9)
(3, 1)

Now I want to find the index (pair) in the array that contains the closest match to the following arbitrary sets of numbers:

(4, 9)
(5, 6)
(9, 1)

My initial solution was to take the number pairs and turn them into numbers themselves.

For example the array sets would become:
(1, 2) -> 12
(2, 4) -> 24
(5, 8) -> 58
(7, 9) -> 79
(3, 1) -> 31

And my number sets to compare would become:

(4, 9) -> 49
(5, 6) -> 56
(9, 1) -> 91

Ok, now I would go through each number I created from the sets in the array and subtract my number from it. Keeping in mind to subtract the smaller number from the larger. The number created from the array set, that when subtracted from my number with the smallest difference, would be my closest match...right?

So:

49 best matches 58 -> 58 - 49 = 9 (smallest difference)
56 best matches 58 -> 58 - 56 = 2 (smallest difference)
91 best matches 79... wait a minute! The difference is being heavily weighted on the "9" in (9, 1). Neither of these two numbers should take precedence so (3, 1) is a better match, but my system does not pick this up! I would also like to be able to do this with sets of 3 or 4 numbers. Any mathematicians out there who can give me a better algorithm? Obviously creating numbers out of the set and subtracting them is not the way to go.

Any help is GREATLY appreciated!!!!! Thanks in advance.

Rob Marriott
rob@career-connections.net

 

[AlexRadu]

Hi.

First of all you should precisely define what is your "proximity" criteria. What exactly do you mean by a pair being "close" to another pair. Is it the sum of the two differences between the numbers in the corresponding positions ? Or what ? Answering this question will be 90% of your solution.

Ex: (4,2) and (5,3) -> the differences are (1,1). The sum would be 2. OTOH, (4,2) and (5,1) are quite different, although the give a sum of differences = 0.

 

[TheInsider]

Hi,
By closest, I do mean the smallest difference. I guess the best analogy of what I am doing would be to think of these sets as plotted points on a grid. I plot five points. Now I want to take a single arbitrary point and find the closest of the five points. To make things slightly harder, I REALLY want to use sets of 3, not 2. ie. (x, y, z)
I am using an array of structures. The structure has one variable for x, one for y, and one for z. Then I have a single-dimension array that holds the individual structures or "points". I want to write a function that receives as parameters the arbitrary x, y, and z points and returns the index of the single-dimension array containing the closest point.
Thanks,

Rob Marriott
rob@career-connections.net

 

[TheInsider]

Thanks AlexRadu,
I re-though my task and realized that there was another implementation that was analogous to what I was trying to do. I did a search and found a tutorial!

Rob Marriott
rob@career-connections.net

 

[Durkin]

I think you should get the formula for the length of a line on a 3D graph and use that. I'd tell you what it is but my maths is more than a little rusty. Durkin
alandurkin@bigpond.com

 

[TheInsider]

Thanks, I found a tutorial that gave me the 3D math that I that was looking for. I had over-complicated the problem originally, then AlexRadu replied with a good point - what am I really doing? It's like when you are trying to solve a problem, so you bring a coleague over to ask their opinion, then while you are explaining the problem to them, you realize the answer.

Rob Marriott
rob@career-connections.net

 

[swilliams]

You are finding the shortest straight line distance between the point in question and your possible closest points.

If your point that you are working with is (X,Y,Z) and you want to find the closest of the points (x1,y1,z1), (x2,y2,z2) and (x3,y3,z3) then you should work out the scalar distance between (X,Y,Z) and each of the three comparison points and pick the one with the shortest distance.
To calculate the scalar distance between the point (X,Y,Z) and (x1,y1,z1) you should work out:
square root of((X-x1)squared + (Y-y1)squared + (Z-z1)squared).

(From a maths graduate and ex maths teacher!!!).

Simon