Is this smaller grid for Poisson disc sampling still correct?

Question

I've seen a number of 2D Poisson disc sampling algorithms online that use a grid to accelerate checking for existing points within the minimum radius [![r][r image]][r link] of a candidate point. For example:

• Dev.Mag
• mbostock

They use a grid of squares of side $\frac{r}{\sqrt2}$, which is the same side length that I intuitively came up with when implementing this myself.

I can see the reason - that is the largest square that cannot contain more than 1 point (assuming the minimum is not attainable - the distance between two points must be strictly greater than $r$).

However, having thought about it further, I adjusted the grid size to $\frac{r}2$ instead. This finer grid means 4 additional squares need to be checked (the 4 corner squares are now within the radius), but the total area covered by the required squares is less, so that on average fewer points will need to go through the Euclidean distance check. The difference can be visualized using the same style as the diagram in the first linked article.

For a candidate new point, existing points must be checked in all squares that are within a radius $r$ of the corners of the candidate's square. Here the two grid sizes are shown side by side, to scale, for the same radius $r$. This shows clearly that a significantly smaller area is being checked. Each square is exactly half the area of the previous approach, and even if the 4 outer corner squares are excluded in the previous approach (left image), this still gives an area $2 \cdot \frac{21}{25} = 1.68$ times larger than in the new approach.

My main question is this: Is this approach still correct, and does it give identical results?

I'm also interested to know whether there is any reason to favor the $\frac{r}{\sqrt2}$ approach. Using $\frac{r}{2}$ seems more efficient in time, which seems worth the cost in space efficiency. Is there anything I'm missing?

---

_{Images produced with this jsfiddle (in case I need to edit them later).}

Answer 1

You approach will work, and in general any square of size < will work fine because the invariant "at most 1 point per square" is valid. Extrapolating from your idea, it means that one should get the best reduction in area checks for infinitesimally small squares. But we don't want to do that, right?

There are two reasons why is usually better than :

1. How much state do you want to manage? Each square can either be "occupied" or "unoccupied" and contains a pointer to its sample point (if any).

   For very large domains with small r, storage costs can be hard to manage. The problem is much worse if you're working with many dimensions. See Gamito et al.'s paper, Figure 12. Even in 4D you can be severely storage limited.

2. In your proposed grid size, each candidate points checks 24 squares, as opposed to 20 in the usual method. There is a per-square cost (e.g. checking whether square is occupied and fetching sample point if it is) which increases the overall cost in your method.

Basically, your method works, but it is usually not more efficient.

However, the state of the art in unbiased Poisson-disk sampling techniques actually successively reduces the grid size as the uncovered area reduces. In addition to Gamito et al.'s paper, also see Ebeida et al.'s paper.

P.S. Sorry, I don't know how to do math formatting in Stack Exchange.