How to effectively draw exactly N points on the screen?

Question

It sounds like a simple question, but I find it surprisingly difficult to succeed with good performance.

The first algorithm I came up with is to randomly draw points, check from a set if it has already been drawn, and draw it differently. This works great if we draw a few dots, but catastrophically slow down as we get closer to filling the screen.

The best I came up with is to build a list of pixels, shuffle it and select the first n (I used python random.sample for this). It works better, but still a bit slow, because the entire list of pixels needs to be constructed in memory, which is terribly full when drawing 5 points. Here is my python code:

#!/usr/bin/env python """ drawn n random points on the screen """ import pygame from pygame.locals import * import sys import random from itertools import product n = int(sys.argv[1]) s = pygame.display.set_mode() sx, sy = s.get_size() points = random.sample(list(product(range(sx), range(sy))), n) for p in points: s.fill((255, 255, 255), pygame.Rect(*p, 1, 1)) pygame.display.flip() while True: for event in pygame.event.get(): if event.type == QUIT or event.type == KEYDOWN: sys.exit() 

Any suggestions for a better algorithm?

Edit: It just turned out that this problem is called "collector sampling." Wikipedia has a number of good algorithms: https://en.wikipedia.org/wiki/Reservoir_sampling

Answer 1

Sample from a lazy sequence:

 points = [(i // sy, i % sy) for i in random.sample(xrange(sx*sy), n)] 

random.sample will choose whether to materialize the sequence and perform a partial shuffle or select random elements and track the selected indices based on the relative sizes of the sequence and the sample.

Note that this requires being an actual sequence, not an iterator. Contrary to popular belief, xrange (or Python 3 range ) is the actual sequence. The generator does not work here.

Answer 2

If you are going to draw so many glasses that you fill the screen, then you probably do not want to make a list of them or remember everything that you painted.

What you want to do is create a pseudo-random, reversible mapping between points. Call the map E(x,y) . Then you can generate all the points (x,y) in the scan line or in another order, and then for each point (x,y) you draw E(x,y) on the screen. By making sure that the mapping is reversible, you guarantee that each unique (x,y) maps to a unique E(x,y) , so your every point will be different.

One common way to create a function of type E(x,y) is to use the Feistel structure: https://en.wikipedia.org/wiki/Feistel_cipher

This is used to create many cryptographic ciphers such as DES.

In your case, you can do this starting with a good integer hash function H(x) , then set W = screen width and H = screen height, and N = number of rounds before use (5ish will do), you can do your function like this (pseudo code, not python, sorry):

 function E(x,y) for (i = 1 to N) x = (x+(H(y)%W)) % W; y = (y+(H(x)%H)) % H return (x,y) 

Please note that each step is easily reversible. If you want to cancel y = (y+(H(x)%H)) % H , you can just do y = (y-(H(x)%H)) % H (this is pseudocode, so I can pretend that the module operator is working correctly with negative numbers).

Although the function is obviously reversible, since each step is reversible, the Feistel structure provides good mixing, and your points will be displayed in good pseudo-random order if you use a good H hash.

Answer 3

Well, you can consider sample points with a minimum distance between them, which makes them non-overlapping. The choice comes from a selection of a Poisson disk. Python description and code can be found here: http://devmag.org.za/2009/05/03/poisson-disk-sampling/