Come disegnare in modo preciso esattamente N punti sullo schermo?

Question

Sembra una domanda facile, ma trovo sorprendentemente difficile riuscire a ottenere buoni risultati.

Il primo algoritmo che ho creato è quello di disegnare punti casualmente, controllare da un set se è già stato disegnato e disegnarlo diversamente. Funziona bene se stiamo disegnando pochi punti ma rallenta catastroficamente mentre ci avviciniamo allo schermo.

Il meglio che ho trovato è quello di costruire l'elenco dei pixel, mischiarlo e scegliere il primo n (ho usato python's random.sample per quello). Funziona meglio, ma è ancora un po 'lento perché l'intera lista di pixel deve essere costruita in memoria, che è orribilmente esagerata quando si disegnano 5 punti. Ecco il mio codice Python:

#!/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() 

Qualche suggerimento per un algoritmo migliore?

Modifica: Appena scoperto questo problema è chiamato "campionamento del serbatoio". Wikipedia ha una serie di buoni algoritmi: https://en.wikipedia.org/wiki/Reservoir_sampling

Answer 1

esempio da una sequenza artificiale:

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

random.sample sceglieranno se materializzare la sequenza ed eseguire un riordino parziale o pick elementi casuali e monitorare indici selezionati, sulla base le dimensioni relative della sequenza e del campione.

Si noti che deve essere una sequenza effettiva, anziché un iteratore, affinché funzioni. Contrariamente alla credenza comune, xrange (o Python 3 range) è una sequenza effettiva. Un generatore non funzionerebbe qui.

Answer 2

Se si stanno disegnando così tanti punti che si riempiono lo schermo, probabilmente non si vuole fare un elenco di essi o ricordare tutti quelli che hai disegnato.

Quello che vuoi fare è creare una mappatura pseudo-casuale e invertibile tra i punti. Chiama la mappatura E(x,y). Quindi, è possibile generare tutti i punti (x,y) nella linea di scansione o in un altro ordine e quindi per ogni punto (x,y), si disegna E(x,y) sullo schermo. Assicurandoti che la mappatura sia invertibile, ti assicuri che ogni singola (x,y) mappa su un unico E(x,y), quindi ogni punto che disegni sarà distinto.

Un modo comune per fare una funzione come E(x,y) è quello di utilizzare una struttura di Feistel: https://en.wikipedia.org/wiki/Feistel_cipher

Questo è usato per fare un sacco di cifrari crittografici come DES.

Nel tuo caso, si può fare questo a partire da una funzione di buon intero hash H(x), poi dato W = larghezza dello schermo e H = l'altezza dello schermo, e N = il numero di giri da utilizzare (5ish farà), è possibile rendere la vostra funzione come questo (pseudocodice, non pitone, 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) 

si noti che ogni passo è facilmente invertibile. Se vuoi annullare y = (y+(H(x)%H)) % H, puoi semplicemente fare y = (y-(H(x)%H)) % H (questo è pseudocodice, quindi posso fingere che l'operatore del modulo funzioni correttamente con numeri negativi).

Anche se la funzione è ovviamente invertibile, perché ogni passo è invertibile, la struttura Feistel fornisce una buona miscelazione ed i tuoi punti verrà fuori in un bel modo pseudo-casuale, se si utilizza un buon hash H.

Answer 3

Beh, potrebbe voler considerare i punti di campionamento con una distanza minima tra di loro, rendendoli così non sovrapposti. Mi viene in mente il campionamento del disco di Poisson. Descrizione e codice Python possono essere trovati qui: http://devmag.org.za/2009/05/03/poisson-disk-sampling/