Building Anti-Clustering Heuristics for Generative Art

The Clustering Problem in Generative Art

When you randomly place elements on a canvas, they inevitably cluster. Random does not mean evenly distributed. Some areas end up dense while others remain empty. For generative art, this creates compositions that look unbalanced and amateur. The human eye expects a degree of spatial harmony that pure randomness cannot provide.

I built anti-clustering heuristics for an autonomous art generation system, and the visual quality difference was dramatic. Here is how the algorithms work.

Minimum Distance Enforcement

The simplest anti-clustering technique: reject any placement that is too close to an existing element.

import numpy as np
from dataclasses import dataclass

@dataclass
class Point:
    x: float
    y: float
    radius: float = 1.0

class MinDistancePlacer:
    def __init__(self, min_distance: float, canvas_size: tuple[float, float]):
        self.min_distance = min_distance
        self.canvas_w, self.canvas_h = canvas_size
        self.placed: list[Point] = []
    
    def try_place(self, max_attempts: int = 100) -> Point | None:
        for _ in range(max_attempts):
            candidate = Point(
                x=np.random.uniform(0, self.canvas_w),
                y=np.random.uniform(0, self.canvas_h)
            )
            
            if self._is_valid(candidate):
                self.placed.append(candidate)
                return candidate
        
        return None  # Could not find valid placement
    
    def _is_valid(self, candidate: Point) -> bool:
        for existing in self.placed:
            dist = np.sqrt(
                (candidate.x - existing.x) ** 2 + 
                (candidate.y - existing.y) ** 2
            )
            if dist < self.min_distance:
                return False
        return True

The Problem with Simple Rejection

Simple rejection sampling works but has two issues: it gets exponentially slower as the canvas fills up, and it does not guarantee good distribution. We can do better.

Poisson Disk Sampling

Poisson disk sampling produces a distribution where no two points are closer than a minimum distance, while still appearing natural and random. It is the gold standard for anti-clustering in generative art.

class PoissonDiskSampler:
    def __init__(self, width: float, height: float, min_dist: float, k: int = 30):
        self.width = width
        self.height = height
        self.min_dist = min_dist
        self.k = k  # Candidates per point
        self.cell_size = min_dist / np.sqrt(2)
        self.grid_w = int(np.ceil(width / self.cell_size))
        self.grid_h = int(np.ceil(height / self.cell_size))
        self.grid = [[None] * self.grid_w for _ in range(self.grid_h)]
        self.points = []
        self.active = []
    
    def sample(self) -> list[Point]:
        # Start with a random initial point
        initial = Point(
            x=np.random.uniform(0, self.width),
            y=np.random.uniform(0, self.height)
        )
        self._add_point(initial)
        self.active.append(initial)
        
        while self.active:
            idx = np.random.randint(len(self.active))
            source = self.active[idx]
            found = False
            
            for _ in range(self.k):
                # Generate candidate in annulus around source
                angle = np.random.uniform(0, 2 * np.pi)
                dist = np.random.uniform(self.min_dist, 2 * self.min_dist)
                candidate = Point(
                    x=source.x + dist * np.cos(angle),
                    y=source.y + dist * np.sin(angle)
                )
                
                if self._is_valid(candidate):
                    self._add_point(candidate)
                    self.active.append(candidate)
                    found = True
                    break
            
            if not found:
                self.active.pop(idx)
        
        return self.points
    
    def _is_valid(self, point: Point) -> bool:
        if not (0 <= point.x < self.width and 0 <= point.y < self.height):
            return False
        
        gx = int(point.x / self.cell_size)
        gy = int(point.y / self.cell_size)
        
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nx, ny = gx + dx, gy + dy
                if 0 <= nx < self.grid_w and 0 <= ny < self.grid_h:
                    neighbor = self.grid[ny][nx]
                    if neighbor is not None:
                        dist = np.sqrt(
                            (point.x - neighbor.x) ** 2 + 
                            (point.y - neighbor.y) ** 2
                        )
                        if dist < self.min_dist:
                            return False
        return True
    
    def _add_point(self, point: Point):
        self.points.append(point)
        gx = int(point.x / self.cell_size)
        gy = int(point.y / self.cell_size)
        self.grid[gy][gx] = point

Density-Aware Placement

Sometimes you want varying density across the canvas rather than uniform distribution. I use a density map that controls how tightly elements can be packed in different regions.

class DensityAwarePlacer:
    def __init__(self, density_map: np.ndarray, base_min_dist: float):
        self.density_map = density_map  # 2D array, values 0-1
        self.base_min_dist = base_min_dist
        self.placed = []
    
    def get_local_min_dist(self, x: float, y: float) -> float:
        # Higher density = smaller minimum distance
        map_h, map_w = self.density_map.shape
        mx = int(x / self.canvas_w * map_w) % map_w
        my = int(y / self.canvas_h * map_h) % map_h
        density = self.density_map[my, mx]
        
        # Density of 1.0 = half the base distance
        # Density of 0.0 = double the base distance
        return self.base_min_dist * (2.0 - 1.5 * density)
    
    def try_place(self, x: float, y: float) -> bool:
        local_min = self.get_local_min_dist(x, y)
        
        for existing in self.placed:
            dist = np.sqrt((x - existing.x) ** 2 + (y - existing.y) ** 2)
            if dist < local_min:
                return False
        
        self.placed.append(Point(x, y))
        return True

Repulsion-Based Relaxation

For the most natural-looking distributions, I apply a physics-inspired relaxation step after initial placement. Points repel each other like charged particles, gradually settling into an equilibrium.

def relax_points(points: list[Point], iterations: int = 50, strength: float = 0.1) -> list[Point]:
    positions = np.array([[p.x, p.y] for p in points])
    
    for _ in range(iterations):
        forces = np.zeros_like(positions)
        
        for i in range(len(positions)):
            for j in range(i + 1, len(positions)):
                diff = positions[i] - positions[j]
                dist = np.linalg.norm(diff)
                if dist < 1e-6:
                    continue
                
                # Inverse square repulsion
                force = strength * diff / (dist ** 3)
                forces[i] += force
                forces[j] -= force
        
        positions += forces
    
    return [Point(x=p[0], y=p[1]) for p in positions]

Visual Results

The difference between random placement and anti-clustered placement is immediately visible. Random placement produces awkward clusters and empty voids. Poisson disk sampling creates a natural, balanced distribution that feels intentional without looking mechanical.

For my art system, combining Poisson disk sampling with density maps and a relaxation pass produces compositions that consistently look professionally designed. These heuristics are simple to implement but have an outsized impact on visual quality.