Tuesday, July 1, 2014

Slow but dense poisson disc distribution sampling

The idea for this algorithm is to somewhat randomly place many dots that are all at least a certain distance apart, without placing so many that it becomes hexagonal close packed packing which is the densest possible. It ends up looking a lot like how the light sensitive cells are arranged on the retina.
This algorithm is slow but has a good end result here it is for 200x200 no two closer than 5 units apart:
The algorithm makes a list of every single possible pixel value shuffled in random order F, then starts with a field with only one random point on it p of list P, pops the first value v off of F and adds it to P if the distance from v to any point p in P is greater than d, where d is the minimum distance between points. The algorithm stops when there are no longer any values in F. In the above at the end there were 2337 points in P.
I could add logic so the points are on a toroidal surface with the top and bottom attached and the sides attached, also if all the points p in P were stored in an octree type structure I think there could be some good performance gains.

**Python Source Code**
import random
from random import shuffle
import Image
def fill(grid, sizegrid):
    for i in range(0, sizegrid[0]):
        for j in range(0, sizegrid[1]):
def distance(pointa, pointb, mindistance):
    if abs(pointa[0]-pointb[0]) >= mindistance:
        return mindistance+1
    if abs(pointa[1]-pointb[1]) >= mindistance:
        return mindistance+1
    return ((pointa[0]-pointb[0])**2 + (pointa[1]-pointb[1])**2)**.5 
def plot(points, sizegrid):
    p ="RGB", sizegrid)
    for i in points:
        if i[0] >= 0 and i[1] >= 0:
            p.putpixel(i, (255,0,0))"out.png")
def add(a, points,mindistance):
    for point in points:
        if distance(point, a, mindistance)<mindistance:
            return False
    return True
def main():
    sizegrid = (200, 200)
    points = [[random.randint(0, sizegrid[0]-1), random.randint(0, sizegrid[1]-1)]]
    fullgrid = []
    fill(fullgrid, sizegrid)
    mindistance = 5
    while(len(fullgrid) > 0):
          f = fullgrid.pop()
          if add(f,points, mindistance):
    plot(points, sizegrid)

No comments:

Post a Comment