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
2 1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.