Dive into NumPy! Start organizing, rearranging, and sampling your data.

Python Data Analysis and Visualization

From Python to Numpy

# Bridson method
If the vectorization of the previous method poses no real difficulty, the speed improvement is not so good and the quality remains low and dependent on the k parameter. The higher, the better since it basically governs how hard to try to insert a new sample. But, when there is already a large number of accepted samples, only chance allows us to find a position to insert a new sample. We could increase the k value but this would make the method even slower without any guarantee in quality. It's time to think out-of-the-box and luckily enough, Robert Bridson did that for us and proposed a simple yet efficient method:

## Step 0:

Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by $\frac{r}{\sqrt{n}}$, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default `−1` indicates no sample, a non-negative integer gives the index of the sample located in a cell.

## Step 1:

Select the initial sample, `x_0`, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list” (an array of sample indices) with this index (zero).

## Step 2:
While the active list is not empty, choose a random index from it (say $i$). Generate up to k points chosen uniformly from the spherical annulus between radius $r$ and $2r$ around $x_i$. For each point in turn, check if it is within distance r of existing samples (using the background grid to only test nearby samples). If a point is adequately far from existing samples, emit it as the next sample and add it to the active list. If after $k$ attempts no such point is found, instead remove $i$ from the active list.
$$$$
## Implementation
The implementation poses no real problem. Note that not only is this method fast, but it also offers a better quality (more samples) than the DART method even with a high $k$ parameter. Here's the complete `Bridson` implementation:



In this lesson, we will try to do the blue noise sampling using the Bridson method. First we will discuss the step-by-step approach and then implement it in code.

Coding Example: Blue Noise Sampling using Bridson method

Bridson method