<s> from math import pi , sin , cos , hypot , floor <EOL> import random <EOL> class Grid ( object ) : <EOL> def __init__ ( self , r ) : <EOL> self . r = r <EOL> self . size = r / <NUM_LIT:2> ** <NUM_LIT:0.5> <EOL> self . cells = { } <EOL> def points ( self ) : <EOL> return self . cells . values ( ) <EOL> def normalize ( self , x , y ) : <EOL> i = int ( floor ( x / self . size ) ) <EOL> j = int ( floor ( y / self . size ) ) <EOL> return ( i , j ) <EOL> def nearby ( self , x , y ) : <EOL> result = [ ] <EOL> i , j = self . normalize ( x , y ) <EOL> for p in xrange ( i - <NUM_LIT:2> , i + <NUM_LIT:3> ) : <EOL> for q in xrange ( j - <NUM_LIT:2> , j + <NUM_LIT:3> ) : <EOL> if ( p , q ) in self . cells : <EOL> result . append ( self . cells [ ( p , q ) ] ) <EOL> return result <EOL> def insert ( self , x , y ) : <EOL> for bx , by in self . nearby ( x , y ) : <EOL> if hypot ( x - bx , y - by ) < self . r : <EOL> return False <EOL> i , j = self . normalize ( x , y ) <EOL> self . cells [ ( i , j ) ] = ( x , y ) <EOL> return True <EOL> def poisson_disc ( x1 , y1 , x2 , y2 , r , n ) : <EOL> x = x1 + ( x2 - x1 ) / <NUM_LIT> <EOL> y = y1 + ( y2 - y1 ) / <NUM_LIT> <EOL> active = [ ( x , y ) ] <EOL> grid = Grid ( r ) <EOL> grid . insert ( x , y ) <EOL> while active : <EOL> ax , ay = random . choice ( active ) <EOL> for i in xrange ( n ) : <EOL> a = random . random ( ) * <NUM_LIT:2> * pi <EOL> d = random . random ( ) * r + r <EOL> x = ax + cos ( a ) * d <EOL> y = ay + sin ( a ) * d <EOL> if x < x1 or y < y1 or x > x2 or y > y2 : <EOL> continue <EOL> if not grid . insert ( x , y ) : <EOL> continue <EOL> active . append ( ( x , y ) ) <EOL> break <EOL> else : <EOL> active . remove ( ( ax , ay ) ) <EOL> return grid . points ( ) </s>
