How to point on non-linear range to linear and back?

Question

I have a list of linear ranges which represent one big range:

                                          X'
 100    200 300    400 500    600 700     |       900    (X)
|----------|----------|----------|--------+----------|
 0                                        |       100    (Y)
                                          Y'

X consists of the following ranges (even and round numbers are just examples for ease of comprehension, they could be anything, no proportions here at all):

• From 100 to 200
• From 300 to 400
• From 500 to 600
• From 700 to 900

On the flip side, Y has just one range:

• From 0 to 100

Both X and Y are of the same length, just different units. Let's say one is dollars and another is percents (or any other similarly unrelated units). So Y'0 == X'100 and Y'100 == X'900.

Given any point in Y, what is equivalent point in X and vise-versa, given a point in X - what is it in Y?

Is this a typical math problem? Does it have a name?

Answer 1

How many ranges do you have? Is it acceptable that the algorithm is O(number of ranges)?

If so, below is the description of the algorithm. Let me explain it on your (original) example.

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

1) What you're doing to do is to map the value X in range A (100-800) to the value Y in continous range B (0-399) (as the total number of elements in your range is 400). Then it's easy to change position in B to percents, I will omit this part.

2) Create a list of records, where each records represents one range mapping.

struct RangeRecord {
  int start_in_a;
  int start_in_b;
};

In your case, you will get the following list:

{100, 0}, {300, 100}, {500, 200}, {700, 300}

3) When you need to map a number X from A to B, you iterate the list to find first record with start_in_a <= X.Then your value Y is

Y = X + start_in_b - start_in_a;

4) The algorithm is symmettric, you just iterate the list to find the first record with start_in_b <= Y, and then

X = Y + start_in_a - start_in_b.

Note 1. For error checking purposes, you might keep the range size in RangeRecord, as well.

Note 2. If O(number of ranges) is not good enough, keep the records as a tree instead of a list. You will need O(log(number of ranges)) operations then,

Answer 2

Say you have one range (a, b) and another one (c, d). Now you have a number i for which a < i < b. You can "normalize" it by subtracting a and dividing by b - a - this gives you a value between 0 and 1. You can then use this value to transfer it into the other range by reversing this calculation with the other bounds, so to speak multiply it by (d - c) and add c.

Say the corresponding point in the other range is i'. Then,

i' = (i - a) / (b - a) * (d - c) + c

The term you are searching for is scaling and translation.

Answer 3

This is not really solvable because the problem is underspecified. Even for the same ranges, there can be different sliders like this:

1  100 101       1000
|-----|-----------|

1        100 101 1000
|-----------|-----|

For each range like [1..100] you need to know how which percent points on the slider correspond to it. In the above examples this could be something like [0%..33%] or [0%..66%]. Once you have this information, it's easy to determine in which of the ranges and at which position of that range a given data point is and to what value it corresponds.

Answer 4

You have three things you need to adjust for in converting from some X' to Y' and vice versa:

1. The ranges start at different places.
2. One of them is discontinuous.
3. The size of each step is different between the two ranges.

It might be helpful (at least while developing your solutions) to consider a similar range Z, which is the range 0 to 503 and has a one-to-one mapping with the 504 possible values in X. That is, for each discontinuity, if the X value is greater than the upper end of the discontinuity, subtract 99 (the size of the discontinuity). Then X'100 = Z'0, X'200 = Z'100, X'300 = Z'101, X'400 = Z'201, X'500 = Z'202, etc. The introduction of the Z range resolves problems 1 and 2 in the list above.

To convert from Z to Y, you just multiply by 101/504, which scales Z onto Y.

Answer 5

Assuming the piecewise linear arrangement you imply, you can find X by:

X = 4*Y + 100*int(1 + Y/25.)

and the reverse for Y:

X2 = int(X/100.)
X3 = X2-int(X2/2.)
Y = (X-100*X3)/4.

edit: This solution works for the original range you gave:

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

And of course, the reverse formula only holds for valid values of X.

Here's a figure of the two curves. The green is your original specification and the blue is the reverse curve (again, only valid for the valid x-values). alt text http://img523.imageshack.us/img523/8858/66945008.png