My English is not good, so I am using a translator. I apologize for any grammar issues.

On a canvas (temporarily sized 1×1), I want to randomly generate some points, with the distance between these points ideally being between 20 and 25 units. This can be thought of as filling the canvas with as many small circles with diameters between 20 and 25 units as possible (similar to the problem of packing non-equal diameter balls). I am considering using Poisson disk sampling for this, setting the sampling distance range to 20-25 and the K parameter to 3000 (to generate more points).

However, when drawing circles with a radius of 20 units on these points, some gaps are still visible. The distances between points around these gaps exceed 25 units. I want to fill these gaps with smaller circles so that the canvas doesn’t look empty. The radii of these smaller circles should be determined by the size of the gaps (as long as the small circles do not intersect with the circles around the gaps). But I don’t know how to use code to determine the positions of the gaps and which circles are around the gaps.

Check the rendering of the random nine grid points, there will be some circles intersecting, I don’t know why?

There will be overlap in the nine grid examination, so I switched to the twenty-five grid examination

The radius is 0.01, directly 0.20, and the green represents the circle around the gap. I want to draw another circle in the gap

According to the code written in the paper

the code：

import numpy as np

# Define the function generate_poisson_disk_samples to generate a set of Poisson disk samples
def generate_poisson_disk_samples(width, height, r, k=3000):
    # Initialize the grid
    cell_size = r / np.sqrt(2)  # Calculate the size of each grid cell
    cols = int(np.ceil(width / cell_size))  # Calculate the number of columns in the grid
    rows = int(np.ceil(height / cell_size))  # Calculate the number of rows in the grid
    grid = np.empty((cols, rows), dtype=np.int32)  # Create an empty grid
    grid.fill(-1)  # Fill the grid with -1, indicating no points

    # Initialize the active list and result list
    active_list = []  # List to store active points
    result = []  # List to store the final points

    # Generate the initial point
    x, y = np.random.uniform(0, width), np.random.uniform(0, height)  # Generate a random initial point
    active_list.append((x, y))  # Add the initial point to the active list
    result.append((x, y))  # Add the initial point to the result list
    grid[int(x // cell_size), int(y // cell_size)] = 0  # Mark the initial point in the grid with 0

    # Main loop, continue until the active list is empty
    while active_list:
        # Get the coordinates of the current point from the active list
        current_x, current_y = active_list.pop(0)
        # Try to generate new points around the current point
        for _ in range(k):
            # Randomly choose an angle
            angle = np.random.uniform(0, 2 * np.pi)
            # Calculate the coordinates of the new point
            new_x = current_x + np.cos(angle) * np.random.uniform(r, 0.025)
            new_y = current_y + np.sin(angle) * np.random.uniform(r, 0.025)
            # Check if the new point is within the valid range
            if 0 <= new_x < width and 0 <= new_y < height:
                col, row = int(new_x // cell_size), int(new_y // cell_size)  # Map the new point to the grid's column and row
                valid = True  # Assume the new point is valid
                # Check if the distance between the new point and surrounding points is greater than r
                for i in range(max(col - 2, 0), min(col + 3, cols)):  # Check the 3x3 grid around the point
                    for j in range(max(row - 2, 0), min(row + 3, rows)):  # Check the 3x3 grid around the point
                # for i in range(max(col - 2, 0), min(col + 3, cols)):  # Check the 5x5 grid around the point (five rows and five columns)
                #     for j in range(max(row - 2, 0), min(row + 3, rows)):  # Check the 5x5 grid around the point (five rows and five columns)
                        if grid[i, j] != -1:
                            dist = np.sqrt((new_x - result[grid[i, j]][0]) ** 2 + (new_y - result[grid[i, j]][1]) ** 2)
                            if dist < r or dist > 0.025: # For 3x3 grid, check both minimum and maximum distances
                            if dist < r:  # For 5x5 grid, only check minimum distance
                                valid = False  # If the distance is less than r, the new point is invalid
                                break
                    if not valid:
                        break
                # If the new point is valid, add it to the active list and result list, and update the grid
                if valid:
                    active_list.append((new_x, new_y))
                    result.append((new_x, new_y))
                    grid[col, row] = len(result) - 1
    # Return the generated set of Poisson disk samples
    return result