Fill an image with a svg icon with Pillow in Python

I am trying to get a svg icon using svg2rlg, creating a white image with pillow, using a loop to get a position in the image to paste the icon, check if it is too close to any icon pasted in the past and then pasting it. My wish was that there was minimal space between icons, but when I increase the number of icons they start to overlap each other.

So my main problems are: 1 - Overlapping images 2 - Too much blank space in the resulting image

What i want is:

An image that is as filled up as possible with this icon, but without overlapping images. Minimizing the blank space and having no icon on top of each other.

The code i am trying to run is the following:

# %%
# Import the 'svglib' and 'reportlab.graphics.renderPM' libraries
from svglib.svglib import svg2rlg
from reportlab.graphics.renderPM import drawToPIL, Drawing
import random
from PIL import Image, ImageDraw

# Set the size of the pattern
pattern_size = (2480,3508)

# Load the SVG images using the 'svglib.svg2rlg()' function
icon1 = svg2rlg('./icones_pattern/dog-cosmos-svgrepo-com.svg')

# Set the size of the icons
icon1.scale(1/8,1/8)
icon1.width=200
icon1.height=200

# %%
min_distance =  200 # min distance between icons
image = Image.new('RGB', pattern_size, (255, 255, 255)) # creation of the pil base image

positions = []

for i in range(100):
  is_valid_position = True
  icon = icon1
  icon_width, icon_height = icon1.width, icon1.height

  # Choose a random position for the icon or dot
  x = random.randint(0, pattern_size[0] - icon_width)
  y = random.randint(0, pattern_size[1] - icon_height)

  center_x, center_y = x + icon_width//2, y + icon_height//2

  for j in range(len(positions)):
    prev_x, prev_y = positions[j]
    prev_x += icon_width
    prev_y += icon_height
    distance = ((center_x - prev_x) ** 2 + (center_y - prev_y) ** 2) ** 0.5
    if distance < min_distance:
        is_valid_position = False
        break
  
  if is_valid_position:
    #icon_width *= random.uniform(0.5, 1.5)
    #icon_height *= random.uniform(0.5, 1.5)
    #angle = random.uniform(-45, 45)
    #icon.rotate(angle)

    # Render the 'Drawing' object to a PIL image using the 'drawToPIL()' function
    icon = drawToPIL(icon)

    # Paste the icon or dot onto the image
    image.paste(icon, (x, y))

    # Save the position of the drawn icon or dot
    positions.append((x, y)) 


# %%
# Save the pattern image to a PNG file
image.save('pattern.png')

The input image in svg is the following:

    <?xml version="1.0" encoding="utf-8"?><!-- Uploaded to: SVG Repo, www.svgrepo.com, Generator: SVG Repo Mixer Tools -->
<svg width="800px" height="800px" viewBox="0 0 64 64" xmlns="http://www.w3.org/2000/svg">

<title>dog-cosmos</title>

<g id="dog-cosmos">

<circle cx="37.5" cy="31.5" r="19.5" style="fill:none"/>

<circle cx="51.509" cy="12.6" r="10.8" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="47.709" cy="12.6" r="3.6" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="56.509" cy="14.8" r="1.8" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<path d="M47.171,3.106A4.194,4.194,0,0,0,50.909,5.4a4.181,4.181,0,0,0,3.885-2.652" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="56" cy="9" r="1"/>

<line x1="13.884" y1="22.637" x2="10.203" y2="26.304" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<line x1="10.21" y1="22.63" x2="13.877" y2="26.311" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="38.5" cy="30.5" r="1.5"/>

<path d="M40.923,43.215,32,45s-4.492-3.369-8.209-5.957" style="fill:none;stroke:#000000;stroke-linejoin:round;stroke-width:2px"/>

<path d="M38.067,57.659,41,43V37l1,1,3.424-.856C48.113,36.472,51,34.055,51,31.283V28H43l-2.752-1.651A9.461,9.461,0,0,0,35.378,25H30c-2.761,0-5,3.134-5,7v5a27.219,27.219,0,0,1-3.689,5.311,33.042,33.042,0,0,0,2.48-3.268" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="17.5" cy="8.5" r="1.5"/>

<path d="M33,31v4a4,4,0,0,1-4,4h0a4,4,0,0,1-4-4" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="37.5" cy="31.5" r="19.5" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<path d="M37.5,16A15.431,15.431,0,0,0,29,18.537" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<path d="M6.072,57.659l3.094-14.7a3.817,3.817,0,0,1,4.741-2.9L21,42,14.149,57.659" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<line x1="58" y1="58" x2="3" y2="58" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<line x1="31" y1="50" x2="28" y2="58" style="fill:none;stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2px"/>

<circle cx="34" cy="54" r="1"/>

</g>

</svg>

The resulting image:

We may have to compare the distance between the centers.

In the following part, prev_x and prev_y are the bottom right corner of the previous icon, and not the center:

prev_x, prev_y = positions[j]
prev_x += icon_width
prev_y += icon_height

distance = ((center_x - prev_x) ** 2 + (center_y - prev_y) ** 2) ** 0.5 returns the distance from the center to the bottom right corner.

Modify the code to compute the distance from the center - for testing the same distance in x and in y axis:

prev_x, prev_y = positions[j]
prev_center_x = prev_x + icon_width//2
prev_center_y = prev_y + icon_height//2
distance = ((center_x - prev_center_x) ** 2 + (center_y - prev_center_y) ** 2) ** 0.5

---

Complete code (using 10000 iterations instead of 100):

# %%
# Import the 'svglib' and 'reportlab.graphics.renderPM' libraries
from svglib.svglib import svg2rlg
from reportlab.graphics.renderPM import drawToPIL, Drawing
import random
from PIL import Image, ImageDraw

# Set the size of the pattern
pattern_size = (2480,3508)

# Load the SVG images using the 'svglib.svg2rlg()' function
icon1 = svg2rlg('./icones_pattern/dog-cosmos-svgrepo-com.svg')

# Set the size of the icons
icon1.scale(1/8,1/8)
icon1.width=200
icon1.height=200

# %%
min_distance =  200 # min distance between icons
image = Image.new('RGB', pattern_size, (255, 255, 255)) # creation of the pil base image

positions = []

for i in range(10000):
  is_valid_position = True
  icon = icon1
  icon_width, icon_height = icon1.width, icon1.height

  # Choose a random position for the icon or dot
  x = random.randint(0, pattern_size[0] - icon_width)
  y = random.randint(0, pattern_size[1] - icon_height)

  center_x, center_y = x + icon_width//2, y + icon_height//2

  for j in range(len(positions)):
    prev_x, prev_y = positions[j]
    #prev_x += icon_width
    #prev_y += icon_height
    prev_center_x = prev_x + icon_width//2
    prev_center_y = prev_y + icon_height//2
    #distance = ((center_x - prev_x) ** 2 + (center_y - prev_y) ** 2) ** 0.5
    distance = ((center_x - prev_center_x) ** 2 + (center_y - prev_center_y) ** 2) ** 0.5
    if distance < min_distance:
        is_valid_position = False
        break
  
  if is_valid_position:
    #icon_width *= random.uniform(0.5, 1.5)
    #icon_height *= random.uniform(0.5, 1.5)
    #angle = random.uniform(-45, 45)
    #icon.rotate(angle)

    # Render the 'Drawing' object to a PIL image using the 'drawToPIL()' function
    icon = drawToPIL(icon)

    # Paste the icon or dot onto the image
    image.paste(icon, (x, y))

    # Save the position of the drawn icon or dot
    positions.append((x, y)) 


# %%
# Save the pattern image to a PNG file
image.save('pattern.png')

---

Output:

As you can see, the solution may not be good enough...

A better solution is to check each of the 4 corners of the pasted icon, and make sure it's not inside any bounding rectangle of existing icon:

px0, py0 = positions[j]  # Top left corner
px1, py1 = px0 + icon_width, py0 + icon_height  # Top left corner

is_top_left_inside = (x0 >= px0 and x0 <= px1) and (y0 >= py0 and y0 <= py1)  # top left corner is inside rectangle if: (x0 between px0 and px1) and (y0 between py0 and py1)
is_top_right_inside = (x1 >= px0 and x1 <= px1) and (y0 >= py0 and y0 <= py1)  # top right corner is inside rectangle if: (x1 between px0 and px1) and (y0 between py0 and py1)
is_bot_left_inside = (x0 >= px0 and x0 <= px1) and (y1 >= py0 and y1 <= py1)  # bottom left corner is inside rectangle if: (x0 between px0 and px1) and (y1 between py0 and py1)
is_bot_right_inside = (x1 >= px0 and x1 <= px1) and (y1 >= py0 and y1 <= py1)  # bottom right corner is inside rectangle if: (x1 between px1 and px1) and (y1 between py0 and py1)

is_valid_position = (not is_top_left_inside) and (not is_top_right_inside) and (not is_bot_left_inside) and (not is_bot_right_inside)  # Valid position if non of the corners are inside

if not is_valid_position:
    break

---

Complete code:

# %%
# Import the 'svglib' and 'reportlab.graphics.renderPM' libraries
from svglib.svglib import svg2rlg
from reportlab.graphics.renderPM import drawToPIL, Drawing
import random
from PIL import Image, ImageDraw

# Set the size of the pattern
pattern_size = (2480,3508)

# Load the SVG images using the 'svglib.svg2rlg()' function
icon1 = svg2rlg('./icones_pattern/dog-cosmos-svgrepo-com.svg')

# Set the size of the icons
icon1.scale(1/8,1/8)
icon1.width=200
icon1.height=200


# %%
#min_distance =  200 # min distance between icons
image = Image.new('RGB', pattern_size, (255, 255, 255)) # creation of the pil base image

positions = []

for i in range(10000):
  is_valid_position = True
  icon = icon1
  icon_width, icon_height = icon1.width, icon1.height

  # Choose a random position for the icon or dot
  x = random.randint(0, pattern_size[0] - icon_width)
  y = random.randint(0, pattern_size[1] - icon_height)

  #center_x, center_y = x + icon_width//2, y + icon_height//2
  x0, y0 = x, y  # Top left corner
  x1, y1 = x + icon_width, y + icon_height  # bottom right cornder

  #(x0, y0)           
  #    --------       
  #   |        |      
  #   |        |       (px0, py0)        
  #   |        |           --------    
  #    --------           |        |   
  #        (x1, y1)       |        |   
  #                       |        |   
  #                        --------    
  #                            (px1, py1)

  for j in range(len(positions)):
    px0, py0 = positions[j]  # Top left corner
    px1, py1 = px0 + icon_width, py0 + icon_height  # Top left corner

    is_top_left_inside = (x0 >= px0 and x0 <= px1) and (y0 >= py0 and y0 <= py1)  # top left corner is inside rectangle if: (x0 between px0 and px1) and (y0 between py0 and py1)
    is_top_right_inside = (x1 >= px0 and x1 <= px1) and (y0 >= py0 and y0 <= py1)  # top right corner is inside rectangle if: (x1 between px0 and px1) and (y0 between py0 and py1)
    is_bot_left_inside = (x0 >= px0 and x0 <= px1) and (y1 >= py0 and y1 <= py1)  # bottom left corner is inside rectangle if: (x0 between px0 and px1) and (y1 between py0 and py1)
    is_bot_right_inside = (x1 >= px0 and x1 <= px1) and (y1 >= py0 and y1 <= py1)  # bottom right corner is inside rectangle if: (x1 between px1 and px1) and (y1 between py0 and py1)

    is_valid_position = (not is_top_left_inside) and (not is_top_right_inside) and (not is_bot_left_inside) and (not is_bot_right_inside)  # Valid position if non of the corners are inside

    if not is_valid_position:
        break
  
  if is_valid_position:
    #icon_width *= random.uniform(0.5, 1.5)
    #icon_height *= random.uniform(0.5, 1.5)
    #angle = random.uniform(-45, 45)
    #icon.rotate(angle)

    # Render the 'Drawing' object to a PIL image using the 'drawToPIL()' function
    icon = drawToPIL(icon)

    # Paste the icon or dot onto the image
    image.paste(icon, (x, y))

    # Save the position of the drawn icon or dot
    positions.append((x, y)) 


# %%
# Save the pattern image to a PNG file
image.save('pattern.png')

---

Output:

It's simple geometry, but quite confusing...