Reputation: 166
I currently have a program where I need to access every pixel of an image in random order. My current approach is to store all coordinate combinations and shuffle them, but this leads to too much memory usage for larger images and results in an out of memory crash.
Is there some function where f(1) -> f(n*n) covers all coordinates uniquely but in random order without using too much time or space?
It doesn't have to be completely random, the points selected just have to be spread out. It would be preferable for it to be in Javascript but an explanation is also fine.
Upvotes: 1
Views: 51
Reputation: 189789
I don't think there's an O(1) solution but if complete randomness isn't important, divide the image into n regions and then (linearly or randomly) visit each pixel at offset m in each of the regions.
As a reductive example, you could randomize only the X coordinates, and then serially or randomly visit every Y pixel of the currently selected X coordinate; but slicing the image into some other arrangement of rectangles of the same size will make it less obvious how the traversal proceeds.
For example, slice any image into 256x256 rectangles, and you reduce your original algorithm's space requirements to 1/65536.
Upvotes: 2
Reputation: 19855
You could build a custom linear congruential generator or find one with a cycle of at least n * n
(but preferably not much greater). Discard outcomes n * n
or larger. For non-discarded values i
in the range 0 <= i < n*n
, decompose into (x,y)
pairs using a very old trick: x <- floor(i / n)
and y <- i % n
.
Upvotes: 3