#### Archived

This topic is now archived and is closed to further replies.

# 2D -> 1D mapping

This topic is 5900 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I need a fast function that maps 2D coordinats to 1D array. The input data is normalized 2D vector. And I need to map it simple 1D array. So far I have been using arctan2(x,y) to map it to [-2PI..2PI] and then transform it to [0..size]. But since arctan2 is slow as hell I need something faster... And as don''t need to transform this 1D value back to 2D coordinats there must be some fast way to do it... Any ideas how... even cheap hacks count Something in the form of : int ArrayPosition( float x, float y ) { int pos; // do your magic stuff here return pos; }; You should never let your fears become the boundaries of your dreams.

##### Share on other sites
If your vectors are normalized, why not store simply x / y?

The problem is that you'll still lose part of the information: -3 / -4 = 3 / 4. If you are willing to fiddle with the bits, there are plenty of ways to do this kind of stuff. You could sacrifice one bit to flag if it's in the first-second quadrant, or in the third-fourth quadrant.

In fact, now that I think about it, if your vectors are normalized, why not store only the x component? You can always find the y component with pythagoras, although you will lose the sign of y, so you'll still have to find a way to encode it somehow.

The simplest way is probably
pos = ((int)(x * 2 ^ 16) << 16) | ((int)(y * 2 ^ 16))

Cédric

[edited by - cedricl on April 29, 2002 3:37:19 PM]

##### Share on other sites
I already tried that but somehow it doesn''t work. I''m losing way to much information if just store x or y. The problem is that vectors should be even distributed in array(like in a hash) and here they are not.

You should never let your fears become the boundaries of your dreams.

##### Share on other sites
with a normalized vector V you have:
Vx = sin (arccos(Vy))

So if vectors are normalized, x and y aren't independent any more, and you simply can drop one axis and are done.

Your problem could still be the values are not evenly distributed, values around -1 and 1 are more common than values around 0...

Edit: formula didn't show up like I wanted...

[edited by - OmniBrain on April 30, 2002 4:29:47 AM]

##### Share on other sites
You could use an algebraic function which has similar properties to tan. E.g.

r = f(t) = t/(t^2 - 1)

-1 < t < 1

is much like tan (compare the graphs of them to see how). The inverse function is the solution to the quadratic

r.t^2 - t - r = 0

i.e.

t = [1 - sqrt(1 + 4r^2)] / 2r

where r is the ratio of x and y.

You need to take a square root to derive it, but it''s still probably quicker than atan as many processors/APIs have accelerated sqrt. You also may be able to simplify it further. Because it''s like tan it should have a similar distribution.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 13
• 9
• 12
• 9
• ### Forum Statistics

• Total Topics
631438
• Total Posts
3000073
×