Formula for selecting each pixel in a bitmap without repeating

Question

I'm looking for an algorithm, now I'm programming fast, but pseudocode or any similar syntax of the "C family" will do.

Imagine a large list of values, such as pixels in a bitmap. You want to select each visually randomly, one at a time, and you never select the same one twice, and you always end up choosing them all.

I used it before in a fractal generator, so it was not just a line-by-line rendering, but it was slowly creating it in a stochastic way, but that was a long time ago in a Java applet and I no longer have code.

I don’t think he used a pseudo-random number generator, and the main thing that I liked about it was that it didn’t make the rendering time take longer than just a linear approach. Any of the shuffling algorithms that I have looked at will make the rendering take longer with so many values ​​that I need to deal with, unless I miss something.

EDIT: I used the array shuffle method. I will shuffle once when the application loads, and it won’t take so long. Here is the code for my Dealer class.

import Foundation import Cocoa import Quartz class Dealer: NSObject { //######################################################## var deck = [(CGFloat,CGFloat)]() var count = 0 //######################################################## init(_ w:Int, _ h:Int) { super.init() deck.reserveCapacity((w*h)+1) for y in 0...h { for x in 0...w { deck.append((CGFloat(x),CGFloat(y))) } } self.shuffle() } //######################################################## func shuffle() { var j:Int = 0 let total:Int = deck.count-1 for i:Int in 0...total { j = Int(arc4random_uniform(UInt32(total))) deck.swapAt(i, j) } } //######################################################## func deal() -> (CGFloat,CGFloat) { let result = deck[count] let total:Int = deck.count-1 if(count<total) { count=count+1 } else { count=0 } return(result) } //######################################################## } 

init is called once and it causes a shuffle, but if you want, you can call shuffle again if necessary. Every time you need a “card”, you name a deal. It ends at the beginning when the deck is executed.

Answer 1

if you have enough space to store all the pixel positions that you can shuffle in them:

 const int xs=640; // image resolution const int ys=480; color pixel[sz]; // image data const int sz=xs*ys; // image size int adr[sz],i,j; for (i=0;i<sz;i++) adr[i]=i; // ordered positions for (i=0;i<sz;i++) // shuffle them { j = random(sz); // pseudo-randomness with uniform distribution swap(pixel[i],pixel[j]); } 

Thus, you are guaranteed that each pixel is used once and, most likely, all of them are shuffled ...

Answer 2

You need to implement a pseudo-random number generator with a theoretically known period that is more than very close to the number of elements in your list. Suppose that R() is a function that implements such an RNG.

Then:

 for i = 1...N do idx = R() while idx > N output element(idx) end 

• If the RNG period is greater than N, this algorithm is guaranteed to complete and never output the same element twice
• If the RNG period is close to N, this algorithm will be fast (i.e., the do-while loop will basically do 1 iteration).
• If the RNG is of good quality, the visual result will be enjoyable; here you have to do experiments and decide what is good enough for you.

To find an RNG that has a well-known period, you must study the theory of RNG, which is very extensive (maybe too extensive); Wikipedia has useful links. Start with Linear Congruent Generators : they are very simple, and there is a chance that they will be of good enough quality.

Answer 3

Here's a working example based on linear feedback shift registers . Since the n-bit LFSR has a maximum sequence length of 2 steps ⁿ -1, this will work best when the number of pixels is less than 2. For other sizes, pseudo-random coordinates are discarded until it is obtained that is in the specified range of coordinates. It is still quite effective; in the worst case (where w × h is degree 2), there will be an average of two LSFR iterations for each coordinate pair.

The following code is in Javascript, but it should be easy enough to port it to Swift or any other language.

Note. For large areas of the canvas, such as 1920 × 1024, it would be more reasonable to use smaller repeating fragments (for example, 128 × 128). The tile will be inconspicuous.

 var lsfr_register, lsfr_mask, lsfr_fill_width, lsfr_fill_height, lsfr_state, lsfr_timer; var lsfr_canvas, lsfr_canvas_context, lsfr_blocks_per_frame, lsfr_frame_rate = 50; function lsfr_setup(width, height, callback, duration) { // Maximal length LSFR feedback terms // (sourced from http://users.ece.cmu.edu/~koopman/lfsr/index.html) var taps = [ -1, 0x1, 0x3, 0x5, 0x9, 0x12, 0x21, 0x41, 0x8E, 0x108, 0x204, 0x402, 0x829, 0x100D, 0x2015, 0x4001, 0x8016, 0x10004, 0x20013, 0x40013, 0x80004, 0x100002, 0x200001, 0x400010, 0x80000D, 0x1000004, 0x2000023, 0x4000013, 0x8000004, 0x10000002, 0x20000029, 0x40000004, 0x80000057 ]; nblocks = width * height; lsfr_size = nblocks.toString(2).length; if (lsfr_size > 32) { // Anything longer than about 21 bits would be quite slow anyway console.log("Unsupposrted LSFR size ("+lsfr_size+")"); return; } lsfr_register = 1; lsfr_mask = taps[lsfr_size]; lsfr_state = nblocks; lsfr_fill_width = width; lsfr_fill_height = height; lsfr_blocks_per_frame = Math.ceil(nblocks / (duration * lsfr_frame_rate)); lsfr_timer = setInterval(callback, Math.ceil(1000 / lsfr_frame_rate)); } function lsfr_step() { var x, y; do { // Generate x,y pairs until they are within the bounds of the canvas area // Worst-case for an n-bit LSFR is n iterations in one call (2 on average) // Best-case (where w*h is one less than a power of 2): 1 call per iteration if (lsfr_register & 1) lsfr_register = (lsfr_register >> 1) ^ lsfr_mask; else lsfr_register >>= 1; y = Math.floor((lsfr_register-1) / lsfr_fill_width); } while (y >= lsfr_fill_height); x = (lsfr_register-1) % lsfr_fill_width; return [x, y]; } function lsfr_callback() { var coords; for (var i=0; i<lsfr_blocks_per_frame; i++) { // Fetch pseudo-random coordinates and fill the corresponding pixels coords = lsfr_step(); lsfr_canvas_context.fillRect(coords[0],coords[1],1,1); if (--lsfr_state <= 0) { clearInterval(lsfr_timer); break; } } } function start_fade() { var w = document.getElementById("w").value * 1; var h = document.getElementById("h").value * 1; var dur = document.getElementById("dur").value * 1; lsfr_canvas = document.getElementById("cv"); lsfr_canvas.width = w; lsfr_canvas.height = h; lsfr_canvas_context = lsfr_canvas.getContext("2d"); lsfr_canvas_context.fillStyle = "#ffff00"; lsfr_canvas_context.fillRect(0,0,w,h); lsfr_canvas_context.fillStyle = "#ff0000"; lsfr_setup(w, h, lsfr_callback, dur); } 

 Size: <input type="text" size="3" id="w" value="320"/> × <input type="text" size="3" id="h" value="240"/> in <input type="text" size="3" id="dur" value="3"/> secs <button onclick="start_fade(); return 0">Start</button> <br /> <canvas id="cv" width="320" height="240" style="border:1px solid #ccc"/>