STUB (YEAH, I’M MAKING LOTS OF THESE) TO REMIND MYSELF TO DO A WRITE-UP.
[h2]Uniform Feature Points[/h2]
Let us imagine that we have a 100x100 meter field and in this field we what there to be, on average, two flowers per meter squared. So we could create an array with 100x100x2 = 20,000 elements to explicitly store the positions of each flower. Using a seeded uniform random number generator we could then fill the array with repeatable coordinates for each. If we were to examine the placement of flowers we would notice that there would be regions with none and areas where they are clummped up.
rng.setSeed(someValue);
for(int i=0; i<100*100*2; i++) {
float x = 100*rng.nextFloat();
float y = 100*rng.nextFloat();
doMyFlower(x,y);
}
Now if were to examine each square meter (or some other regular chunk) and count the number of flowers it contains, then the “distribution” of the counts approaches the Poisson distribution (Wikipedia, MathWorld).
So instead of precomputing a explicit list of “features”, the space in question can be broken down into parts. For each part one computes a poisson random number to determine the number of features inside it.
// From Knuth, reasonable on modern machines for smallish
// means. There are many ways this can be computed.
// eMean = exp(-mean)
public static final int poisson(float eMean)
{
int r = 1;
float t = rng.nextFloat();
while (t > eMean) {
r++;
t *= rng.nextFloat();
}
return r-1;
}
// Sketch below this point
private static final float FLOWER_POWER = (float)Math.exp(-2);
private void doSomeCellFlowerThing(...)
{
rng.setSeed(hashOfThisCell);
int num = poisson(FLOWER_POWER);
for(int i=0; i<num; i++) {
// coordinates local to the square meter in this example
float x = rng.nextFloat();
float y = rng.nextFloat();
...
}
}
Assuming that the chosen hashing function does a reasonable job, then the “look” of the localized vs. global versions should be similar. Up until now I’ve avoided too much techo-speak but some definitions are required. All of the above rng.nextFloat() calls are assume to return a uniformly distributed random number on [0,1) which is the standard base contract for a uniform floating point result (actually the inclusion/exclusion of the end-points may vary, but I’m assuming the presented). In probability a uniform distribution (Wikipedia, MathWorld) means that all results on the range are equally probable…like in a single fair die roll. So in the examples above the ‘x’ coordinate of each flower is completely independent of ‘y’, which should be expected. Moreover the coordinates of each flower is independent of any other. This leads to the previously mentioned empty and clumpped up areas. This result, like many from probability, is likely to seem counter-intuitive. Most likely “uniform” will tend to invoke notions of uniformly (or evenly) covered areas. This is a radially different notion of uniform as implies that all of the values are related to each other rather than independent. Note that these two different notions of uniform approach one another as the number of features (or event) increase.