Algoritmo per la generazione di valori di colore RGB non ripetuti, distanziati

Question

Desidero avere un metodo statico, che ogni volta chiamato restituirà un valore di colore che non è ancora visualizzato e non è troppo vicino all'ultimo colore restituito (ad esempio return new Color(last_value += 10) non lo farò). Inoltre, non dovrebbe essere casuale, quindi ogni volta che l'applicazione viene avviata, la sequenza dei colori restituiti sarebbe la stessa.

La prima cosa che mi è venuta alla mia testa, è quello di iterare su un array con un passo numero di primordiale, qualcosa di simile:

private static HashMap<Integer, Boolean> used = new HashMap<>(); 
    private static int[] values = new int[0xfffff]; // 1/16th of possible colors 
    private static int current = 0, jump = values.length/7; 

    public static Color getColour(){ 
     int value = values[current]; 
     used.put(current, true); 
     current += jump; 
     current %= values.length; 
     //have some check here if all colors were used 
     while (used.containsKey(current)){ 
      current++; 
      current%=values.length; 
     } 
     return new Color(value); 
    } 

Ma non mi piace che, dal momento che i colori saranno vicini l'uno altro da alcune chiamate indietro.

Answer 1

Un buon modo per generare sequenze casuali non ripetitive è l'uso di LFSR.

/** 
* Linear feedback shift register 
* 
* Taps can be found at: See http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf See http://mathoverflow.net/questions/46961/how-are-taps-proven-to-work-for-lfsrs/46983#46983 See 
* http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm See http://www.yikes.com/~ptolemy/lfsr_web/index.htm See 
* http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html 
* 
* @author OldCurmudgeon 
*/ 
public class LFSR implements Iterable<BigInteger> { 

    // Bit pattern for taps. 
    private final BigInteger taps; 
    // Where to start (and end). 
    private final BigInteger start; 

    // The poly must be primitive to span the full sequence. 
    public LFSR(BigInteger primitivePoly, BigInteger start) { 
     // Where to start from (and stop). 
     this.start = start.equals(BigInteger.ZERO) ? BigInteger.ONE : start; 
     // Knock off the 2^0 coefficient of the polynomial for the TAP. 
     this.taps = primitivePoly.shiftRight(1); 
    } 

    public LFSR(BigInteger primitivePoly) { 
     this(primitivePoly, BigInteger.ONE); 
    } 

    // Constructor from an array of taps. 
    public LFSR(int[] taps) { 
     this(asPoly(taps)); 
    } 

    private static BigInteger asPoly(int[] taps) { 
     // Build the BigInteger. 
     BigInteger primitive = BigInteger.ZERO; 
     for (int bit : taps) { 
      primitive = primitive.or(BigInteger.ONE.shiftLeft(bit)); 
     } 
     return primitive; 
    } 

    @Override 
    public Iterator<BigInteger> iterator() { 
     return new LFSRIterator(start); 
    } 

    private class LFSRIterator implements Iterator<BigInteger> { 
     // The last one we returned. 

     private BigInteger last = null; 
     // The next one to return. 
     private BigInteger next = null; 

     public LFSRIterator(BigInteger start) { 
      // Do not return the seed. 
      last = start; 
     } 

     @Override 
     public boolean hasNext() { 
      if (next == null) { 
       /* 
       * Uses the Galois form. 
       * 
       * Shift last right one. 
       * 
       * If the bit shifted out was a 1 - xor with the tap mask. 
       */ 
       boolean shiftedOutA1 = last.testBit(0); 
       // Shift right. 
       next = last.shiftRight(1); 
       if (shiftedOutA1) { 
        // Tap! 
        next = next.xor(taps); 
       } 
       // Never give them `start` again. 
       if (next.equals(start)) { 
        // Could set a finished flag here too. 
        next = null; 
       } 
      } 
      return next != null; 
     } 

     @Override 
     public BigInteger next() { 
      // Remember this one. 
      last = hasNext() ? next : null; 
      // Don't deliver it again. 
      next = null; 
      return last; 
     } 

     @Override 
     public void remove() { 
      throw new UnsupportedOperationException("Not supported."); 
     } 

     @Override 
     public String toString() { 
      return LFSR.this.toString() 
        + "[" + (last != null ? last.toString(16) : "") 
        + "-" + (next != null ? next.toString(16) : "") + "]"; 
     } 
    } 

    @Override 
    public String toString() { 
     return "(" + taps.toString(32) + ")-" + start.toString(32); 
    } 

} 

Ora è sufficiente un valore di tap 8+8+8=24.

L'utilizzo è semplice.

public void test() { 
    // Sample 24-bit tap found on page 5 of 
    // http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf 
    int[] taps = new int[]{24, 23, 22, 17}; 
    LFSR lfsr = new LFSR(taps); 
    int count = 100; 
    for (BigInteger i : lfsr) { 
     System.out.println("Colour: " + new Color(i.intValue())); 
     if (--count <= 0) { 
      break; 
     } 
    } 
} 

Caratteristiche di un LFSR:

• E volontà ripetizione - ma non fino a quando tutte le possibili sequenze di bit sono stati generati (tranne 0).
• Il numero generato è statisticamente un buon numero casuale.
• La stessa sequenza verrà generata ogni volta (scegliere un diverso tap se si desidera una sequenza diversa).

Per ottenere la spaziatura richiesta, suggerirei di aggiungere un filtro e scartare quelli che sono troppo vicini (secondo il criterio) a quello precedente.