<p>You approach will work, and in general any square of size &lt; <a href="https://i.sstatic.net/sYEU8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sYEU8.png" alt="enter image description here"></a> 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?</p>

<p>There are two reasons why <a href="https://i.sstatic.net/SnBBv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SnBBv.png" alt="enter image description here"></a> is usually better than <a href="https://i.sstatic.net/qH0GY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qH0GY.png" alt="enter image description here"></a>:</p>

<ol>
<li><p>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).</p>

<p>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 <a href="http://staffwww.dcs.shef.ac.uk/people/S.Maddock/research/gamito/papers/poisson.pdf" rel="nofollow noreferrer">Gamito et al.'s paper</a>, Figure 12. Even in 4D you can be severely storage limited.</p></li>
<li><p>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.</p></li>
</ol>

<p><strong>Basically, your method works, but it is usually not more efficient.</strong> </p>

<p>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 <a href="http://staffwww.dcs.shef.ac.uk/people/S.Maddock/research/gamito/papers/poisson.pdf" rel="nofollow noreferrer">Gamito et al.'s paper</a>, also see <a href="http://www.sandia.gov/~samitch/papers/eurographics_mps-final-with-appendix.pdf" rel="nofollow noreferrer">Ebeida et al.'s paper</a>.</p>

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

CC BY-SA 3.0
2015-09-02T22:28:52.713Z
[Vote for MathJax formatting on this site.](http://meta.computergraphics.stackexchange.com/questions/18/should-we-have-mathjax-support)
luser droog
CC BY-SA 3.0
2015-09-02T23:14:53.637Z
I've added this question to that meta post as an example of further need for MathJax
trichoplax is on Codidact now
CC BY-SA 3.0
2015-09-08T01:56:03.440Z
@trichoplax, you used mathurl for pasting images? I'm reading from Android app and i can't check.
psicomante
CC BY-SA 3.0
2015-09-08T14:05:50.627Z
@psicomante yes I used mathurl.com and included the links inline - are they readable on Android? It's the next best thing until we get MathJax activated.
trichoplax is on Codidact now
CC BY-SA 3.0
2015-09-08T14:07:56.430Z
@psicomante press edit under the question if you want to see the markup (you need to add `.png` to the end of the mathurl.com link to make it show as an image here). Any questions just @mention me in [chat].
trichoplax is on Codidact now
CC BY-SA 3.0
2015-09-08T15:38:13.600Z
@trichoplax yep, they are almost perfectly readable on Android SE app. It's a good tool until MathJax activated
psicomante
CC BY-SA 3.0
2015-09-02T21:44:15.287Z
2015-09-08T18:22:51.277Z
2015-09-08T18:22:51.277Z
ap_
<p>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:</p>

<ul>
<li><a href="http://devmag.org.za/2009/05/03/poisson-disk-sampling/" rel="nofollow noreferrer">Dev.Mag</a></li>
<li><a href="http://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3" rel="nofollow noreferrer">mbostock</a></li>
</ul>

<p>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.</p>

<p>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 <em>strictly</em> greater than $r$).</p>

<p>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.</p>

<p><a href="https://i.sstatic.net/cE5KI.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/cE5KI.png" alt="Grid with side length r over root 2"></a>
<a href="https://i.sstatic.net/r3PJ9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/r3PJ9.png" alt="Grid with side length r over 2"></a></p>

<p>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.</p>

<p>My main question is this: <strong>Is this approach still correct, and does it give identical results?</strong></p>

<p>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?</p>

<hr>

<p><sub><em>Images produced with this <a href="https://jsfiddle.net/wkneysgj/" rel="nofollow noreferrer">jsfiddle</a> (in case I need to edit them later).</em></sub></p>

CC BY-SA 3.0
2015-08-24T00:26:41.520Z
If you are worried about the square root, you can probably square both sides of the equation.
Alan Wolfe
CC BY-SA 3.0
2015-08-24T00:35:46.710Z
@AlanWolfe I can precompute the square root - it's only ever root 2. My main reason for changing the side length is the significant reduction in area. I just wonder if it broke anything...
trichoplax is on Codidact now
<grid>
Is this smaller grid for Poisson disc sampling still correct?
trichoplax is on Codidact now
# Is this smaller grid for Poisson disc sampling still correct?

(Asked by: username_0 on 2015-08-23)

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](http://devmag.org.za/2009/05/03/poisson-disk-sampling/)
* [mbostock](http://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3)

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.

[![Grid with side length r over root 2](https://i.sstatic.net/cE5KI.png)](https://i.sstatic.net/cE5KI.png)
[![Grid with side length r over 2](https://i.sstatic.net/r3PJ9.png)](https://i.sstatic.net/r3PJ9.png)

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](https://jsfiddle.net/wkneysgj/) (in case I need to edit them later).*

**Tags:** grid

> **Comments:**
> **username_1**: If you are worried about the square root, you can probably square both sides of the equation.  
> **username_0**: @username_1 I can precompute the square root - it's only ever root 2. My main reason for changing the side length is the significant reduction in area. I just wonder if it broke anything...  

---

## 1 answers

### Answer by username_2 on 2015-09-02. Score: 5 | Accepted answer

You approach will work, and in general any square of size < [![enter image description here](https://i.sstatic.net/sYEU8.png)](https://i.sstatic.net/sYEU8.png) 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 [![enter image description here](https://i.sstatic.net/SnBBv.png)](https://i.sstatic.net/SnBBv.png) is usually better than [![enter image description here](https://i.sstatic.net/qH0GY.png)](https://i.sstatic.net/qH0GY.png):

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](http://staffwww.dcs.shef.ac.uk/people/S.Maddock/research/gamito/papers/poisson.pdf), 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](http://staffwww.dcs.shef.ac.uk/people/S.Maddock/research/gamito/papers/poisson.pdf), also see [Ebeida et al.'s paper](http://www.sandia.gov/~samitch/papers/eurographics_mps-final-with-appendix.pdf).

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

> **Comments:**
> **username_3**: [Vote for MathJax formatting on this site.](http://meta.computergraphics.stackexchange.com/questions/18/should-we-have-mathjax-support)  
> **username_0**: I've added this question to that meta post as an example of further need for MathJax  
> **username_4**: @username_0, you used mathurl for pasting images? I'm reading from Android app and i can't check.  
> **username_0**: @username_4 yes I used mathurl.com and included the links inline - are they readable on Android? It's the next best thing until we get MathJax activated.  
> **username_0**: @username_4 press edit under the question if you want to see the markup (you need to add `.png` to the end of the mathurl.com link to make it show as an image here). Any questions just @mention me in [chat].  
> **username_4**: @username_0 yep, they are almost perfectly readable on Android SE app. It's a good tool until MathJax activated  

---

