Most inefficient algorithm to visit each elements of a 2d array once

Question

I'm creating panorama images, and for this I use a camera that I move programmatically step by step. The images are captured rows by rows.

So basically the captures can be seen as some kind a 2d array:

[ 0, 1, 2, 3 ] # row 1
[ 4, 5, 6, 7 ] # row 2

Where the camera moves sequentially through the numbers.

I noticed that if a car moves in front of the camera and follows the same pace as the camera, the car appears on every picture and the panorama looks weird.

So, I had the following idea: move the camera in a non-sequential order that way the car is very likely to be only captured once. I then thought about how to capture the images in a way that the camera travels the most between each position.

I found a way for single-row panoramas. Basically it start at the beginning, jumps half way right, goes back half-way left minus 1, and repeats.

Here are examples:

# 1x5 --> [0, 2, 4, 1, 3]          # sequential indices: 0 3 1 4 2
# 1x6 --> [0, 2, 4, 1, 3, 5]       # sequential indices: 0 3 1 4 2 5
# 1x7 --> [0, 2, 4, 6, 1, 3, 5]    # sequential indices: 0 4 1 5 2 6 3
# 1x8 --> [0, 2, 4, 6, 1, 3, 5, 7] # sequential indices: 0 4 1 5 2 6 3 7

To be clear, this means that for 1x6 (0, 2, 4, 1, 3, 5) the camera moves as follow:

x----- # pos 1
---x-- # pos 2
-x---- # pos 3
----x- # pos 4
--x--- # pos 5
-----x # pos 6

So basically it jumps all the time by at least n/2, which looks optimal as no capture ends up being the neighbor of another one and the distance between captures looks maximized and fluctuates very little.

The simplified code I use is something like:

def index_for(n, cols)
  col = n % cols
  if n.even?
    col/2
  else
    (col / 2.0).ceil + (cols / 2.0).ceil - 1
  end
end

# Sequential indices [0, 4, 1, 5, 2, 6, 3]
seq = (0..6).map{ |i| index_for(i, 7) }

# Visualization [0, 2, 4, 6, 1, 3, 5]
(0..6).map{ |i| seq.index(i) }

I tried making it work with several rows, and almost got there but then gave up. Here are examples of the idea I had:

 # 3x4
 [0,  2, 9, 11]
 [4,  6, 1,  3]
 [8, 10, 5,  7]

 # 2x5
 [0, 2, 5, 7, 9]
 [4, 6, 8, 1, 3]

If you look at the numbers, we see that the left side is usually simply the even numbers, and the right side are odd numbers but shifted in a modulus way. This shifting of the odd numbers is tricky to algorithmize, because the logic change slightly depending on the rows/cols being even/odd.

At the moment I ignore the rows and simply reapply the same algorithm for each rows. That means the 2x5 is done like this:

 [0, 2, 4, 1, 3]
 [5, 7, 9, 6, 8]

So, here are my questions:

• What is the best algorithm to achieve what I want, with multiple rows? I read about https://en.wikipedia.org/wiki/Longest_path_problem and I think it'd be possible to construct a graph where there exist paths between all nodes of the grid, and the weight for each edge would be the distance between the nodes. This sounds very complicated and not easy to code tho.
• What would be the simplest/most practical algorithm to apply for multiple rows? I'm okay with "good-enough" solutions (the dimensions of the grid should remain within 1x3 to 3x9). I don't want solutions based on randomness, because I want the captures to always happen in the same order each time the panorama is captured.

EDIT: additional informations: the car usually moves slowly (at the speed of the sequential captures), so jumping around is a good way to avoid repetitions. It's also better to see the car in 2-3 tiles than in 7 of them if the car moves exactly at the speed of the camera (this happened). The panoramas are usually around 180°, but 360° should be supported. There's a pause of around 3 seconds between each image capture. The panoramas are mostly about capturing the construction of giant construction sites (buildings), but sometimes a car or a person walks in front of the building. We don't care about the moving parts, the goal is to capture the building and minimize the person/car photobombing the panorama.

Answer 1

Ok I have found as simpler formula for each rows:

The code becomes trivial:

def index_for(n, cols)
  (n + cols * (n % 2)) / 2
end

(0..7).map{ |i| index_for(i, 8) }
=> [0, 4, 1, 5, 2, 6, 3, 7]

So, for now I'll just use this for each row. I'll wait a while in the case someone comes up with a better answer to my questions.