Hello Everyone, Welcome to this article about Poisson Disk sampling.

Youtube video: https://youtu.be/kzPmjAhBNfY

For a Deeper understanding and explanation , I strongly recommend to read this paper or atleast take a look at it:

https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

Poisson-disk sampling is a random process for selecting points from a subdomain of a metric space. A selected point must be disk-free,
at least a minimum distance, r, from any previously selected point. Thus each point has an associated disk of radius r that precludes the selection of nearby points. The selected points are called a sample or distribution.

In this article i'm gonna just try to explain the python implementation , but i'm gonna leave the link for both the python and C# code at the end of this article.

for this python implementation we gonna use pygame:

if you don't have pygame , you can install it just by running this command in your terminal

'pip install pygame'.

So first we gonna make a new file 'sample.py' which gonna have Vector class that's gonna store the direction of the vector but also it gonna have two functions , one to normalize the vector and another to get the magnitude of the vector.

import math
class Vector2:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def normalize_vector(self):
        magnitude = math.sqrt(self.x * self.x + self.y * self.y)
        self.x = self.x/magnitude
        self.y = self.y/magnitude


    def set_magnitude(self, new_magnitude):
        self.normalize_vector()
        x = self.x * new_magnitude
        y = self.y * new_magnitude

        return Vector2(x, y)

Now we can make our root file 'main.py'.

First let import the libraries that we gonna use and initialize pygame and some constant variables that we gonna use such as the width and the height of the screen

import pygame
import math
import random
from Sample import Vector2
import colorsys

width, height = 1920, 1080
size=(width, height)
black, white, green = (10, 10, 10), (230, 230, 230), (95, 255, 1)
hue = 0

pygame.init()
screen = pygame.display.set_mode(size)
clock = pygame.time.Clock()
fps = 60

let's initialize the variables that we gonna use like the grid lists which gonna store all our samples. and also iniatialize a vector of a random direction.

x = random.randint(50, width-50)
y = random.randint(50, height-50)
position = Vector2(x, y)

cl = x // w
rw = y // w
columns = width // w
rows = height // w
active_list = []

grid = [i for i in range(math.ceil(columns * rows))]

for i in range(math.ceil(columns * rows)):
    grid[i] = None
grid[math.ceil(cl+rw*columns)] = position
active_list.append(position)

we gonna also make a function that convert hsv colors to rgb colors since we need a smooth changing color of our disc or points and a splice list function.

def list_splice(target, start, delete_count=None, *items):
    if delete_count == None:
        delete_count = len(target) - start

    total = start + delete_count
    removed = target[start:total]
    target[start:total] = items
    return removed

def hsv_to_rgb(h, s, v):
    return tuple(round(i * 255) for i in colorsys.hsv_to_rgb(h, s, v))

Now we can make the main loop of our program,

run = True
while run:
    # set framerate
    clock.tick(fps)
    # clear screen color
    screen.fill(black)
    
    # handle user input
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE:
                run = False
    
    
    if len(active_list) > 0:
        randIndex = random.randint(0, len(active_list)-1)
        current_position = active_list[randIndex]
        found = False
        for n in range(k):
            offset = Vector2(random.uniform(-2, 2), random.uniform(-2, 2))
            new_magnitude = random.randint(r, r*2)
            offset = offset.set_magnitude(new_magnitude)
            offset.x = offset.x + current_position.x
            offset.y = offset.y + current_position.y

            col = math.ceil(offset.x/w)
            row = math.ceil(offset.y/w)

            if row < rows-screen_offset and col < columns-screen_offset and row > screen_offset and col > screen_offset:
                checker = True
                for i in range(-1, 2):
                    for j in range(-1, 2):
                        index = math.ceil( col + i + (row+j) * columns)

                        neighbour = grid[index];
                        if neighbour is not None:
                            dist = math.sqrt((offset.x - neighbour.x) ** 2 + (offset.y - neighbour.y) ** 2)
                            if dist < r:
                                checker = False


                if checker is True:
                    found = True
                    grid[math.ceil(col + row * columns)] = Vector2(offset.x, offset.y)
                    active_list.append(Vector2(offset.x, offset.y))
                    break
        if found is not True:
            list_splice(active_list, randIndex+1, 1)
    
    # draw all the sample in the grid
    for cell in grid:
        if cell is not None:
            pygame.draw.circle(screen, white, (math.ceil(cell.x), math.ceil(cell.y)), 16)

    for disk in active_list:
        pygame.draw.circle(screen, hsv_to_rgb(hue, 1, 1), (math.ceil(disk.x), math.ceil(disk.y)), 16)

    pygame.display.flip()
    hue += 0.0009
pygame.quit()

you can now run you main file to see the result

Github code python version: Poisson disc sampling with python

Github code C# version: Poisson disc sampling with c#

Youtube channel: Auctux

thank you ✌️