main.py

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import math
import argparse
import random

parser = argparse.ArgumentParser()
parser.add_argument('-stepbystep', action='store_true', help='Run the animation step by step')
args = parser.parse_args()
step_by_step = args.stepbystep

def Run(image_path,mesh_length=10,threshold=128):
    image = Image.open(image_path)
    grayscale_image = image.convert('L')
    width, height = grayscale_image.size
    binary_image = np.zeros((height, width), dtype=np.uint8)

    for y in range(height):
        for x in range(width):
            if grayscale_image.getpixel((x, y)) > threshold:
                binary_image[y, x] = 255

    list_of_black_cord = poisson_disk_sample_black_pixels(binary_image, mesh_length)
    if not list_of_black_cord:
        print("No black pixels found for point sampling.")
        return

    visited = {}
    tracker={}
    index=1
    for ele in list_of_black_cord:
        visited[ele] = False
        tracker[ele]=index
        index+=1

    fig, ax = plt.subplots()
    
    # Show scatter points at the beginning
    x_cord = [ele[0] for ele in list_of_black_cord]
    y_cord = [ele[1] for ele in list_of_black_cord]
    scatter = ax.scatter(x_cord, y_cord, c="blue", s=1)
    ax.set_xlim(0, width)
    ax.set_ylim(-height, 0)
    
    if step_by_step:
        for ele in list_of_black_cord:
            ax.text(ele[0], ele[1], str(tracker[ele]), fontsize=8, color='blue')
        
        print("Press Enter to after every connection to continue")
    
    def update(frame):
        nonlocal visited

        ele = list(visited.keys())[frame]
        visited[ele] = True
        curr_closest_neb_list = find_closest_elem_list(ele, list_of_black_cord)

        for curr_closest_neb in curr_closest_neb_list:
            if step_by_step:
                print(f"Connect {tracker[ele]} --> {tracker[curr_closest_neb]}")
                input("")
            line = ax.plot([ele[0], curr_closest_neb[0]], [ele[1], curr_closest_neb[1]], c="red", linewidth=1)[0]
    anim = FuncAnimation(fig, update, frames=len(visited), repeat=False,interval=2)
    plt.show()

def find_closest_elem_list(src, final_list):
    NEIGHBORS = 4
    temp_dist_list = []

    for candidate in final_list:
        if candidate != src:
            distance = calculate_distance(src, candidate)
            temp_dist_list.append((distance, candidate))

    temp_dist_list.sort()
    list_to_return = []

    for i in range(min(NEIGHBORS, len(temp_dist_list))):
        list_to_return.append(temp_dist_list[i][1])

    return list_to_return

def calculate_distance(point1, point2):
    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)

def poisson_disk_sample_black_pixels(binary_image, min_distance, attempts_per_point=30):
    height, width = binary_image.shape
    radius = max(1.0, float(min_distance))
    cell_size = radius / math.sqrt(2)
    grid_width = math.ceil(width / cell_size)
    grid_height = math.ceil(height / cell_size)
    grid = [[None for _ in range(grid_width)] for _ in range(grid_height)]
    active_points = []
    samples = []

    def is_black(x, y):
        xi = int(x)
        yi = int(y)
        return 0 <= xi < width and 0 <= yi < height and binary_image[yi, xi] == 0

    def grid_coords(point):
        return int(point[0] / cell_size), int(point[1] / cell_size)

    def fits(point):
        if not is_black(point[0], point[1]):
            return False

        grid_x, grid_y = grid_coords(point)
        min_x = max(0, grid_x - 2)
        max_x = min(grid_width, grid_x + 3)
        min_y = max(0, grid_y - 2)
        max_y = min(grid_height, grid_y + 3)

        for y in range(min_y, max_y):
            for x in range(min_x, max_x):
                neighbor = grid[y][x]
                if neighbor is None:
                    continue
                if calculate_distance(point, neighbor) < radius:
                    return False

        return True

    def add_point(point):
        samples.append(point)
        active_points.append(point)
        grid_x, grid_y = grid_coords(point)
        grid[grid_y][grid_x] = point

    black_pixels = np.argwhere(binary_image == 0)
    if len(black_pixels) == 0:
        return []

    start_y, start_x = black_pixels[random.randrange(len(black_pixels))]
    add_point((float(start_x), float(start_y)))

    while active_points:
        source = random.choice(active_points)
        found_candidate = False

        for _ in range(attempts_per_point):
            angle = random.uniform(0, 2 * math.pi)
            distance = random.uniform(radius, 2 * radius)
            candidate = (
                source[0] + math.cos(angle) * distance,
                source[1] + math.sin(angle) * distance,
            )

            if fits(candidate):
                add_point(candidate)
                found_candidate = True
                break

        if not found_candidate:
            active_points.remove(source)

    unique_points = []
    seen_points = set()

    for x, y in samples:
        point = (int(round(x)), -int(round(y)))
        if point in seen_points:
            continue
        seen_points.add(point)
        unique_points.append(point)

    return unique_points

if __name__ == "__main__":
    image_path = 'mona_lisa_invert.jpg'
    Run(image_path)