Basicly I am trying to figure out a formula that calculates a unique identification number for a dot in 2 dimensional space. Conditions : if f(x,y) = c then there is no other X1, Y1 so that f(X1,Y1) = c both x and y are integers and c must be also an integer (double may not be suited since its precision is questionable and im not sure if it's suited to use as a key in hashtable).
Asked
Active
Viewed 157 times
1
-
1This could be anything from simple to impossible. Are x and y integers and have a certain range? – Anders Forsgren Jun 25 '12 at 06:56
-
Better suited for [math.stackexchange.com](http://math.stackexchange.com) – Burhan Khalid Jun 25 '12 at 06:56
-
if you have upper limit and lower limits for x,y then i would try some thing like this, for example 0< x < 100 , 0 < y < 100, then c = 100*x+y. that means 0 < c < 10000. – Sudar Nimalan Jun 25 '12 at 07:15
1 Answers
1
This is, of course, quite trivial. Let me outline an algorithm, I'll leave the coding as an exercise for whoever cares to do it.
Take a sheet of paper, better make it a large one, and draw a grid of squares on it. Label the columns with the numbers from min to max, so for integers that would be from 1 to, well, a large number. Label the rows the same way. I'll suppose that you started labelling rows and columns at 1, then the top-left cell of this grid will be at (1,1).
In the cell at (1,1) write the number 1. In cell (2,1) write 2, in (1,2) write 3, in (1,3) write 4, in (2,2) write 5, ....
You now have an invertible mapping from the 2D integer 'space' into 1D integer space.
Thanks to Cantor for his help with this one.
High Performance Mark
- 77,191
- 7
- 105
- 161
-
Similar to enumerating the positive rationals, except that it also counts reducible fractions. – wberry Jun 25 '12 at 07:41
-
Decoding is a bit trickier, considering that you have to calculate which diagonal you are on, possibly by identifying the next-lowest triangular number `T` to the input and then solving `n(n + 1)/2 = T`. – wberry Jun 25 '12 at 08:05