00001
00002
00003
00004
00005 from math import log
00006 from math import sin
00007 from math import cos
00008 from math import sqrt
00009 from math import floor
00010 from math import ceil
00011 from math import pi
00012
00013 from random import random
00014 from random import randint
00015 from random import uniform
00016
00017 from datastructures import RandomQueue
00018 from enhanced_grid import int_point_2d
00019 from enhanced_grid import int_point_3d
00020 from enhanced_grid import Grid2D
00021 from enhanced_grid import Grid3D
00022 from enhanced_grid import ListGrid2D
00023 from enhanced_grid import ListGrid3D
00024
00025
00026
00027 def rand(n):
00028 return randint(0, n - 1)
00029
00030
00031 def sqr_dist((x0, y0), (x1, y1)):
00032 return (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0)
00033
00034
00035 def sqr_dist_3d((x0, y0, z0), (x1, y1, z1)):
00036 return (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0) + (z1 - z0)*(z1 - z0)
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 def sample_poisson_uniform(width, height, r, k):
00060
00061
00062 def grid_coordinates((x, y)):
00063 return (int(x*inv_cell_size), int(y*inv_cell_size))
00064
00065
00066 def put_point(p):
00067 process_list.push(p)
00068 sample_points.append(p)
00069 grid[grid_coordinates(p)] = p
00070
00071
00072
00073 def generate_random_around((x, y), r):
00074 rr = uniform(r, 2*r)
00075 rt = uniform(0, 2*pi)
00076
00077 return rr*sin(rt) + x, rr*cos(rt) + y
00078
00079
00080 def in_rectangle((x, y)):
00081 return 0 <= x < width and 0 <= y < height
00082
00083 def in_neighbourhood(p):
00084 gp = gx, gy = grid_coordinates(p)
00085
00086 if grid[gp]: return True
00087
00088 for cell in grid.square_iter(gp, 2):
00089 if cell and sqr_dist(cell, p) <= r_sqr:
00090 return True
00091 return False
00092
00093
00094 cell_size = r/sqrt(2)
00095 inv_cell_size = 1 / cell_size
00096 r_sqr = r*r
00097
00098 grid = Grid2D((int(ceil(width/cell_size)),
00099 int(ceil(height/cell_size))))
00100
00101 process_list = RandomQueue()
00102 sample_points = []
00103
00104
00105 put_point((rand(width), rand(height)))
00106
00107
00108 while not process_list.empty():
00109 p = process_list.pop()
00110
00111 for i in xrange(k):
00112 q = generate_random_around(p, r)
00113 if in_rectangle(q) and not in_neighbourhood(q):
00114 put_point(q)
00115
00116 return sample_points
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137 def sample_poisson(width, height, r_grid, k):
00138
00139
00140 def grid_coordinates((x, y)):
00141 return (int(x*inv_cell_size), int(y*inv_cell_size))
00142
00143
00144 def put_point(p):
00145 process_list.push(p)
00146 sample_points.append(p)
00147 grid[grid_coordinates(p)].append(p)
00148
00149
00150
00151 def generate_random_around((x, y), r):
00152 rr = uniform(r, 2*r)
00153 rt = uniform(0, 2*pi)
00154
00155 return rr*sin(rt) + x, rr*cos(rt) + y
00156
00157
00158 def in_rectangle((x, y)):
00159 return 0 <= x < width and 0 <= y < height
00160
00161 def in_neighbourhood(p, r):
00162 gp = grid_coordinates(p)
00163 r_sqr = r*r
00164
00165 for cell in grid.square_iter(gp, 2):
00166 for q in cell:
00167 if sqr_dist(q, p) <= r_sqr:
00168 return True
00169 return False
00170
00171 r_min, r_max = r_grid.min_max()
00172
00173
00174 cell_size = r_max/sqrt(2)
00175 inv_cell_size = 1 / cell_size
00176 r_max_sqr = r_max*r_max
00177
00178 grid = ListGrid2D(int_point_2d((ceil(width/cell_size),
00179 ceil(height/cell_size))))
00180
00181 process_list = RandomQueue()
00182 sample_points = []
00183
00184
00185 put_point((rand(width), rand(height)))
00186
00187
00188 while not process_list.empty():
00189 p = process_list.pop()
00190 r = r_grid[int_point_2d(p)]
00191
00192 for i in xrange(k):
00193 q = generate_random_around(p, r)
00194 if in_rectangle(q) and not in_neighbourhood(q, r):
00195 put_point(q)
00196
00197 return sample_points
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220 def sample_poisson_3d(width, height, depth, r_grid, k):
00221
00222
00223 def grid_coordinates((x, y, z)):
00224 return int_point_3d((x*inv_cell_size, y*inv_cell_size, z*inv_cell_size))
00225
00226
00227 def put_point(p):
00228 process_list.push(p)
00229 sample_points.append(p)
00230 grid[grid_coordinates(p)].append(p)
00231
00232
00233
00234 def generate_random_around((x, y, z), r):
00235 rr = uniform(r, 2*r)
00236 rs = uniform(0, 2*pi)
00237 rt = uniform(0, 2*pi)
00238
00239 return rr*sin(rs)*cos(rt) + x, rr*sin(rs)*sin(rt) + y, rr*cos(rs) + z
00240
00241
00242 def in_rectangle((x, y, z)):
00243 return 0 <= x < width and 0 <= y < height and 0 <= z < depth
00244
00245 def in_neighbourhood(p, r):
00246 gp = grid_coordinates(p)
00247 r_sqr = r*r
00248
00249 for cell in grid.square_iter(gp, 2):
00250 for q in cell:
00251 if sqr_dist_3d(q, p) <= r_sqr:
00252 return True
00253 return False
00254
00255 r_min, r_max = r_grid.min_max()
00256
00257
00258 cell_size = r_max/sqrt(2)
00259 inv_cell_size = 1 / cell_size
00260 r_max_sqr = r_max*r_max
00261
00262 grid = ListGrid3D((
00263 int(ceil(width/cell_size)),
00264 int(ceil(height/cell_size)),
00265 int(ceil(depth/cell_size))))
00266
00267 process_list = RandomQueue()
00268 sample_points = []
00269
00270
00271 put_point((rand(width), rand(height), rand(depth)))
00272
00273
00274 while not process_list.empty():
00275 p = process_list.pop()
00276 r = r_grid[int_point_3d(p)]
00277
00278 for i in xrange(k):
00279 q = generate_random_around(p, r)
00280 if in_rectangle(q) and not in_neighbourhood(q, r):
00281 put_point(q)
00282
00283 return sample_points