Archived

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

_DarkWIng_

2D -> 1D mapping

Recommended Posts

_DarkWIng_    602
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 this post


Link to post
Share on other sites
Cedric    158
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 this post


Link to post
Share on other sites
_DarkWIng_    602
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 this post


Link to post
Share on other sites
OmniBrain    148
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 this post


Link to post
Share on other sites
johnb    351
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.

Share this post


Link to post
Share on other sites