3

Generally we traverse the array by row or column but here I want to traverse it in an angle. I will try and explain what I mean, So lets say if the angle is 45 degree then rather than row by col it would search as (0,0) then (0,1) (1,0) then (0,2) , (1,1) ,(2,0) and so on.. .(sorry could not upload an image as I am new user and not allowed to do so, may be try and imagine/draw an array that would help get what I am trying to say) But what will happen if the user inputs an angle like 20 degree how can we determine how to search the array.

i just wanted to know if there is any algorithm which does something similar to this? Programming language is not an issue i guess the issue is more of algoritham sort. Any ideas would be welcome. Please feel free to ask if I am not able to explain clearly what I am looking for.

Thanks guys.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
CC_aka_ck
  • 33
  • 3

3 Answers3

6

Easy. Take an angle (let's say 45). This corresponds to a vector v=(1, 1) in your case. (This can be normalized to a unitary vector (sqrt(2)/2, sqrt(2)/2), but this is not necessary)

For every single point in your array, you have their coordinates (x, y). Simply do the scalar product of these coordinates with the vector. Let's call f(x, y) = scalarProduct((x, y), v)

Sort the values of f(x, y) and you've got the "traversing" you're looking for!

A real example. Your matrix is 3x3 The scalar products are :

(0,0).(1,1) = 0

(0,1).(1,1) = 1

(0,2).(1,1) = 2

(1,0).(1,1) = 1

(1,1).(1,1) = 2

(1,2).(1,1) = 3

(2,0).(1,1) = 2

(2,1).(1,1) = 3

(2,2).(1,1) = 4

If you order these scalar products by ascending order, you obtain the ordering (0,0), (1,0), (1,0), (2,0), (1,1), (0,2), (2,1)...

And if you want to do it with the angle 20, replace all occurences of v=(1, 1) with v=(cos(20), sin(20))

Here's an illustration of a geometrical interpretation. The scalar products correspond to the intersections of the vector v (in red) with the blue lines.

Illustration

B. Decoster
  • 7,723
  • 1
  • 32
  • 52
  • Can you upload an image, please? Do your solution looks like a morton curve? – Micromega Jul 12 '11 at 09:17
  • Definitely not a Morton curve, I think we disagree on the question of the OP. – B. Decoster Jul 12 '11 at 09:26
  • Thank you for your image but, I thought of a 2d-diagram with Excel of the sorted points. Looks interesting, though. – Micromega Jul 12 '11 at 09:29
  • @Frevez thanks a lot for that. I guess that was exactly what i was looking for.. Eventually what I want is i can easily move in between the array. Like I can easily jump from row to row-1 and col to col +1 or something like that.. so I guess by traversing the array in the fashion u have mentioned, I will write new rowNum and colNum in a cache and use that. thanks a lot man.. – CC_aka_ck Jul 13 '11 at 07:20
1

For every starting point (the leftmost point of every row), use trigonometry to determine an ending point for the given angle. The tan(angle) is defined as (height difference / width of the array), so your height differece is tan(angle)*(witdh of the array). You only have to calculate the height difference once. If y+height difference is greater than the height of the array, just subtract the height (or use the modulo operator).

Now that you have a starting point and an ending point you could use Bresenham's Algorithm to determine the points in between: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

David Tanzer
  • 2,732
  • 18
  • 30
0

You want to look for a space-filling-curve for example a morton curve or z-curve. If you want to subdivide the array in 4 tiles you may want to look for a hilbert curve or a moore curve.

Micromega
  • 12,486
  • 7
  • 35
  • 72