Jason (jcreed) wrote,

Been reading a bit about the Poisson disk distribution, which is easy enough to describe, but tricky to sample from. What it is is: you let uniformly randomly distributed points arrive, and you accept the ones that are not within r distance of any previously accepted point. The linked article describes one way to do this, but evidently the standard problem with this distribution in principle is you don't know when to stop generating points. The theoretical distribution is: keep generating points until no more can be.

I think probably you could do something with quadtrees, for if some circles don't cover all the grid cells at first:
you could keep making the grid smaller until either they do:
or else you find a point in a not-necessarily covered square that actually does have some acceptable space.

And I think you can probably speed up the point sampling by doing it more locally, treating the arrivals process as a 3d poisson process in spacetime, and taking longer, skinnier, more timey-wimey bits
that nonetheless have the same volume, and taking a geometric distribution to determine how many arrivals are in that chunk, and the uniform distribution over where they are in the chunk.
Tags: math, poisson
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded