What could be the fastest way to build an array of sequence ordered list with numpy?

Question

Say that we start with this situation:

blue numbers correspond to index of the position

This was generated by using this script:

# u v parameters allow to define how many points according to x and y

u, v = (3, 3)
x = np.linspace(0, 2, u)
y = np.linspace(0, 1, v)

# meshgrid used to create a grid out of several arrays
xx, yy, zz = np.meshgrid(x, y, 0)

# reshaping matrix
coords = np.dstack((xx,yy,zz))
coords = np.vstack(coords)

Considering that u and v can be different and very large numbers, the main objective would be to create an array of list following this scheme:

meaning something like :

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

@hpaulj here are some examples which shows the influence of u and v parameters

The solution I was able to find corresponds to this:

listing = np.array([((u)*j+i, (u)*j+i+1, (u)*j+i+u+1, (u)*j+i+u) for j in range(v-1) for i in range(u-1)])

Can anyone think of a better way (cleaner, faster, more array) to achieve the same result?

Answer 1

Something like this, not necessarily fastest possible, but I think its much cleaner than your current version

import numpy as np

points_indices = np.arange(9).reshape((3, 3))

quads = np.array([
    points_indices[:-1, :-1].flatten(),  # left bottom corners
    points_indices[:-1, 1:].flatten(),    # right bottom corners
    points_indices[1:, 1:].flatten(),   # top right corners
    points_indices[1:, :-1].flatten(),   # top-left corners
]).T

print(quads)

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

You may want to remove those comments.

Answer 2

If you have u columns and v rows, assuming both u >= 2 and v >= 2, then a cycle starting at index i will be [i, i + 1, i + u + 1, i + u], assuming i is a valid starting point, i.e. not on the right or top edge. You can use this plus a little broadcasting magic to build your array in a few simple instructions:

u, v = 3, 3
indices = np.empty((v - 1, u - 1, 4), dtype=int)
indices[:, :, :] = [0, 1, u+1, u]
start_index = np.arange(u * v).reshape(v, u)[:-1, :-1]
indices += start_index[:, :, None]
indices = indices.reshape([-1, 4])

Answer 3

This is an indexing problem. Your grid is given by

grid = np.arange(u * v).reshape(u, v)

We assume u >= 2 and v >= 2. The first box can be obtained thusly:

grid[[0, 1, 1, 0], [0, 0, 1, 1]]

All the other boxes are obtained by incrementing the indices shown here. In fact, we have the following indices

x = np.tile(np.array([0, 1, 1, 0]) + np.arange(u - 1)[:, None], (v - 1, 1))
y = np.repeat(np.array([0, 0, 1, 1]) + np.arange(v - 1)[:, None], u - 1, axis=0)

Now you can do

grid[x, y]

But even that's not technically necessary. The elements of grid follow a very deterministic formula:

grid[i, j] == i + u * j

That means that you don't need grid at all, just the indices x and y:

x + u * y