CODEWITHSUNDEEP
algorithm
Michael Schlottke-Lakemper
Michael Schlottke-Lakemper

Reputation: 9321

Mapping unit square to (0, 1)

In general, I am looking for an algorithm that (efficiently, hopefully) maps any point in the unit square (i.e. (0, 1) x (0, 1) to the (open or closed) interval (0, 1).

More specifically, my problem is as follows: given 2 points in 2D, how can I find an ordering between them (i.e. one goes before the other) that is

One possibility that springs to mind is a space-filling curve such as Morton or Hilbert, but I can't seem to find the description for the continuous case (only for discrete potints) and I'm sure there must be an alternative.

Upvotes: 0

Views: 1535

Answers (2)

Andreas H.
Andreas H.

Reputation: 6085

Since computers can not represent continuous numbers, we ultimately have to stick to the discrete case (no matter what number representation we are using).

Lets assume the "unit interval" consits of $N$ numbers. Then the "unit square" consists of $N^2$ discrete elements.

Practically this means we need twice as much bits for representation of elements of the unit square.

That essentially means that concatenation of x and y coordinate will do the job. Which in fact yields a discrete serpentine type space filling curve.

Since the mapping is bijective, the well ordering of the discrete unit interval directly also translates to a well ordering on the unit square.

The point is, that in any case you need twice as much bits and it always comes down to a bit combination in some way.

I am not really sure if that is what you had in mind. Maybe you yourself are not so clear about what you want/need?

Upvotes: 1

amit
amit

Reputation: 178461

If you have doubles or any other type used by computers to mimic read numbers that has a finite set of values you can get - you cannot get a bijection from (0,1)x(0,1) to (0,1) - there isn't one, since |(0,1)x(0,1)| > |(0,1) for this case.
One lossy solution is to use the average of the two elements: f(x,y)=(x+y)/2 - but of course, as expected - there will be clashes between different values (it cannot be avoided).

However, if you are dealing with real numbers (the 'real' (0,1)), you can.

Each real number r can be represented by an infinite vector from the alphabet {0,1,...,9}. 1 So, you can create a new vector which is interleaving between the different digits:

for example: 

r1=0.3360000... r2=0.518000....
f(r1,r2) = 0.3531680000....

If you want f((x,y)) == f((y,x)), you can simply "sort" each pair, and put the smaller element first. For the above example, you will get:

f(r1,r2) = 0.3513680000....

Note that this solution has clashes as well, to avoid it - you can introduce a new function g():

g(3i) = min{r1[i], r2[i]}
g(3i+1) = max{r1[i],r2[i]}
g(3i+2) = r1[i]<r2[i] ? 0 : 1

For the above example, this will give you:

g(r1,r2) = 0.351132681002002.....

(1) or any other alphabet with 2 or more characters in it

Upvotes: 0

Related Questions