CODEWITHSUNDEEP
algorithmmathgeometry
CC_aka_ck
CC_aka_ck

Reputation: 33

Traversing a 2D array in an angle

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.

Upvotes: 3

Views: 1641

Answers (3)

B. D
B. D

Reputation: 7798

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

Upvotes: 6

David Tanzer
David Tanzer

Reputation: 2742

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

Upvotes: 1

Cybercartel
Cybercartel

Reputation: 12592

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.

Upvotes: 0

Related Questions