Speed up fast poisson disk sampling generator in Python The 2019 Stack Overflow Developer...
What do the Banks children have against barley water?
Pokemon Turn Based battle (Python)
What does "fetching by region is not available for SAM files" means?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
Is "plugging out" electronic devices an American expression?
Should I use my personal e-mail address, or my workplace one, when registering to external websites for work purposes?
What is the accessibility of a package's `Private` context variables?
What did it mean to "align" a radio?
Which Sci-Fi work first showed weapon of galactic-scale mass destruction?
Building a conditional check constraint
What is the most effective way of iterating a std::vector and why?
What are the motivations for publishing new editions of an existing textbook, beyond new discoveries in a field?
Who coined the term "madman theory"?
Deal with toxic manager when you can't quit
One word riddle: Vowel in the middle
Landlord wants to switch my lease to a "Land contract" to "get back at the city"
What do hard-Brexiteers want with respect to the Irish border?
Geography at the pixel level
Are there incongruent pythagorean triangles with the same perimeter and same area?
How come people say “Would of”?
Why hard-Brexiteers don't insist on a hard border to prevent illegal immigration after Brexit?
Is a "Democratic" Feudal System Possible?
Write faster on AT24C32
If I score a critical hit on an 18 or higher, what are my chances of getting a critical hit if I roll 3d20?
Speed up fast poisson disk sampling generator in Python
The 2019 Stack Overflow Developer Survey Results Are In
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
0
$begingroup$
I wrote a generator class which implements Fast Poisson Disk Sampling algorithm in Python. I did some optimizations like, x ** 2 -> x * x, using unpacking instead of indexing, move unpacking outside of loops and precalculating of constants (like 2 * pi), but still not very pleased with results. Is it possible to speed up it even more?
Code:
import math
import random
class PoissonDiskGenerator(object):
def __init__(self, field, r, k=30):
self.field_x, self.field_y = field
self.cell_size = math.ceil(r / math.sqrt(2))
self.grid_size_x, self.grid_size_y = math.ceil(field[0] / self.cell_size), math.ceil(field[1] / self.cell_size)
self.samples_grid = [
[None for y in range(math.ceil(self.field_x / self.cell_size))]
for x in range(math.ceil(self.field_y / self.cell_size))
]
x = random.uniform(0, field[0]), random.uniform(0, field[1])
self.points = [x]
self.active_indices = [0]
self.active_iter = 1
self.tries = k
self.radius = r
self.radius2 = 2 * r
self.pi2 = 2 * math.pi
def __iter__(self):
return self
def __next__(self):
if self.active_indices:
point = self.try_place_new_point()
while not point and self.active_indices:
point = self.try_place_new_point()
if not point:
raise StopIteration
return point
else:
raise StopIteration
def try_place_new_point(self):
ref_ind = random.choice(self.active_indices)
for i in range(self.tries):
point_x, point_y = self.pick_point(self.points[ref_ind])
grid_x, grid_y = math.floor(point_x / self.cell_size), math.floor(point_y / self.cell_size)
neighbor_list = self.neighbors(grid_x, grid_y)
point_ok = True
if neighbor_list:
for neighbor in neighbor_list:
nb_x, nb_y = neighbor
if (point_x - nb_x) * (point_x - nb_x) + (point_y - nb_y) * (point_y - nb_y) < self.radius * self.radius:
point_ok = False
if point_ok:
self.points.append((point_x, point_y))
self.active_indices.append(self.active_iter)
self.samples_grid[grid_x][grid_y] = self.active_iter
self.active_iter += 1
return point_x, point_y
self.active_indices.remove(ref_ind)
return None
def pick_point(self, ref_point):
ref_x, ref_y = ref_point
while True:
rho, theta = random.uniform(self.radius, self.radius2), random.uniform(0, self.pi2)
pick_x, pick_y = ref_x + rho * math.cos(theta), ref_y + rho * math.sin(theta)
if 0 < pick_x < self.field_x and 0 < pick_y < self.field_y:
return pick_x, pick_y
def grid_to_point(self, grid_x, grid_y):
try:
return self.samples_grid[grid_x][grid_y]
except IndexError:
return None
def neighbors(self, grid_x, grid_y):
neighbors_list = (
self.grid_to_point(grid_x, grid_y),
self.grid_to_point(grid_x, grid_y - 1),
self.grid_to_point(grid_x, grid_y + 1),
self.grid_to_point(grid_x - 1, grid_y),
self.grid_to_point(grid_x - 1, grid_y - 1),
self.grid_to_point(grid_x - 1, grid_y + 1),
self.grid_to_point(grid_x + 1, grid_y),
self.grid_to_point(grid_x + 1, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y),
self.grid_to_point(grid_x + 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 2),
self.grid_to_point(grid_x, grid_y + 2),
self.grid_to_point(grid_x - 1, grid_y + 2),
self.grid_to_point(grid_x - 2, grid_y + 1),
self.grid_to_point(grid_x - 2, grid_y),
self.grid_to_point(grid_x - 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y - 2),
self.grid_to_point(grid_x, grid_y - 2),
self.grid_to_point(grid_x - 1, grid_y - 2)
)
return (self.points[ngb] for ngb in neighbors_list if ngb is not None)
python performance generator
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
$begingroup$
I wrote a generator class which implements Fast Poisson Disk Sampling algorithm in Python. I did some optimizations like, x ** 2 -> x * x, using unpacking instead of indexing, move unpacking outside of loops and precalculating of constants (like 2 * pi), but still not very pleased with results. Is it possible to speed up it even more?
Code:
import math
import random
class PoissonDiskGenerator(object):
def __init__(self, field, r, k=30):
self.field_x, self.field_y = field
self.cell_size = math.ceil(r / math.sqrt(2))
self.grid_size_x, self.grid_size_y = math.ceil(field[0] / self.cell_size), math.ceil(field[1] / self.cell_size)
self.samples_grid = [
[None for y in range(math.ceil(self.field_x / self.cell_size))]
for x in range(math.ceil(self.field_y / self.cell_size))
]
x = random.uniform(0, field[0]), random.uniform(0, field[1])
self.points = [x]
self.active_indices = [0]
self.active_iter = 1
self.tries = k
self.radius = r
self.radius2 = 2 * r
self.pi2 = 2 * math.pi
def __iter__(self):
return self
def __next__(self):
if self.active_indices:
point = self.try_place_new_point()
while not point and self.active_indices:
point = self.try_place_new_point()
if not point:
raise StopIteration
return point
else:
raise StopIteration
def try_place_new_point(self):
ref_ind = random.choice(self.active_indices)
for i in range(self.tries):
point_x, point_y = self.pick_point(self.points[ref_ind])
grid_x, grid_y = math.floor(point_x / self.cell_size), math.floor(point_y / self.cell_size)
neighbor_list = self.neighbors(grid_x, grid_y)
point_ok = True
if neighbor_list:
for neighbor in neighbor_list:
nb_x, nb_y = neighbor
if (point_x - nb_x) * (point_x - nb_x) + (point_y - nb_y) * (point_y - nb_y) < self.radius * self.radius:
point_ok = False
if point_ok:
self.points.append((point_x, point_y))
self.active_indices.append(self.active_iter)
self.samples_grid[grid_x][grid_y] = self.active_iter
self.active_iter += 1
return point_x, point_y
self.active_indices.remove(ref_ind)
return None
def pick_point(self, ref_point):
ref_x, ref_y = ref_point
while True:
rho, theta = random.uniform(self.radius, self.radius2), random.uniform(0, self.pi2)
pick_x, pick_y = ref_x + rho * math.cos(theta), ref_y + rho * math.sin(theta)
if 0 < pick_x < self.field_x and 0 < pick_y < self.field_y:
return pick_x, pick_y
def grid_to_point(self, grid_x, grid_y):
try:
return self.samples_grid[grid_x][grid_y]
except IndexError:
return None
def neighbors(self, grid_x, grid_y):
neighbors_list = (
self.grid_to_point(grid_x, grid_y),
self.grid_to_point(grid_x, grid_y - 1),
self.grid_to_point(grid_x, grid_y + 1),
self.grid_to_point(grid_x - 1, grid_y),
self.grid_to_point(grid_x - 1, grid_y - 1),
self.grid_to_point(grid_x - 1, grid_y + 1),
self.grid_to_point(grid_x + 1, grid_y),
self.grid_to_point(grid_x + 1, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y),
self.grid_to_point(grid_x + 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 2),
self.grid_to_point(grid_x, grid_y + 2),
self.grid_to_point(grid_x - 1, grid_y + 2),
self.grid_to_point(grid_x - 2, grid_y + 1),
self.grid_to_point(grid_x - 2, grid_y),
self.grid_to_point(grid_x - 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y - 2),
self.grid_to_point(grid_x, grid_y - 2),
self.grid_to_point(grid_x - 1, grid_y - 2)
)
return (self.points[ngb] for ngb in neighbors_list if ngb is not None)
python performance generator
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
0
0
$begingroup$
I wrote a generator class which implements Fast Poisson Disk Sampling algorithm in Python. I did some optimizations like, x ** 2 -> x * x, using unpacking instead of indexing, move unpacking outside of loops and precalculating of constants (like 2 * pi), but still not very pleased with results. Is it possible to speed up it even more?
Code:
import math
import random
class PoissonDiskGenerator(object):
def __init__(self, field, r, k=30):
self.field_x, self.field_y = field
self.cell_size = math.ceil(r / math.sqrt(2))
self.grid_size_x, self.grid_size_y = math.ceil(field[0] / self.cell_size), math.ceil(field[1] / self.cell_size)
self.samples_grid = [
[None for y in range(math.ceil(self.field_x / self.cell_size))]
for x in range(math.ceil(self.field_y / self.cell_size))
]
x = random.uniform(0, field[0]), random.uniform(0, field[1])
self.points = [x]
self.active_indices = [0]
self.active_iter = 1
self.tries = k
self.radius = r
self.radius2 = 2 * r
self.pi2 = 2 * math.pi
def __iter__(self):
return self
def __next__(self):
if self.active_indices:
point = self.try_place_new_point()
while not point and self.active_indices:
point = self.try_place_new_point()
if not point:
raise StopIteration
return point
else:
raise StopIteration
def try_place_new_point(self):
ref_ind = random.choice(self.active_indices)
for i in range(self.tries):
point_x, point_y = self.pick_point(self.points[ref_ind])
grid_x, grid_y = math.floor(point_x / self.cell_size), math.floor(point_y / self.cell_size)
neighbor_list = self.neighbors(grid_x, grid_y)
point_ok = True
if neighbor_list:
for neighbor in neighbor_list:
nb_x, nb_y = neighbor
if (point_x - nb_x) * (point_x - nb_x) + (point_y - nb_y) * (point_y - nb_y) < self.radius * self.radius:
point_ok = False
if point_ok:
self.points.append((point_x, point_y))
self.active_indices.append(self.active_iter)
self.samples_grid[grid_x][grid_y] = self.active_iter
self.active_iter += 1
return point_x, point_y
self.active_indices.remove(ref_ind)
return None
def pick_point(self, ref_point):
ref_x, ref_y = ref_point
while True:
rho, theta = random.uniform(self.radius, self.radius2), random.uniform(0, self.pi2)
pick_x, pick_y = ref_x + rho * math.cos(theta), ref_y + rho * math.sin(theta)
if 0 < pick_x < self.field_x and 0 < pick_y < self.field_y:
return pick_x, pick_y
def grid_to_point(self, grid_x, grid_y):
try:
return self.samples_grid[grid_x][grid_y]
except IndexError:
return None
def neighbors(self, grid_x, grid_y):
neighbors_list = (
self.grid_to_point(grid_x, grid_y),
self.grid_to_point(grid_x, grid_y - 1),
self.grid_to_point(grid_x, grid_y + 1),
self.grid_to_point(grid_x - 1, grid_y),
self.grid_to_point(grid_x - 1, grid_y - 1),
self.grid_to_point(grid_x - 1, grid_y + 1),
self.grid_to_point(grid_x + 1, grid_y),
self.grid_to_point(grid_x + 1, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y),
self.grid_to_point(grid_x + 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 2),
self.grid_to_point(grid_x, grid_y + 2),
self.grid_to_point(grid_x - 1, grid_y + 2),
self.grid_to_point(grid_x - 2, grid_y + 1),
self.grid_to_point(grid_x - 2, grid_y),
self.grid_to_point(grid_x - 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y - 2),
self.grid_to_point(grid_x, grid_y - 2),
self.grid_to_point(grid_x - 1, grid_y - 2)
)
return (self.points[ngb] for ngb in neighbors_list if ngb is not None)
python performance generator
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I wrote a generator class which implements Fast Poisson Disk Sampling algorithm in Python. I did some optimizations like, x ** 2 -> x * x, using unpacking instead of indexing, move unpacking outside of loops and precalculating of constants (like 2 * pi), but still not very pleased with results. Is it possible to speed up it even more?
Code:
import math
import random
class PoissonDiskGenerator(object):
def __init__(self, field, r, k=30):
self.field_x, self.field_y = field
self.cell_size = math.ceil(r / math.sqrt(2))
self.grid_size_x, self.grid_size_y = math.ceil(field[0] / self.cell_size), math.ceil(field[1] / self.cell_size)
self.samples_grid = [
[None for y in range(math.ceil(self.field_x / self.cell_size))]
for x in range(math.ceil(self.field_y / self.cell_size))
]
x = random.uniform(0, field[0]), random.uniform(0, field[1])
self.points = [x]
self.active_indices = [0]
self.active_iter = 1
self.tries = k
self.radius = r
self.radius2 = 2 * r
self.pi2 = 2 * math.pi
def __iter__(self):
return self
def __next__(self):
if self.active_indices:
point = self.try_place_new_point()
while not point and self.active_indices:
point = self.try_place_new_point()
if not point:
raise StopIteration
return point
else:
raise StopIteration
def try_place_new_point(self):
ref_ind = random.choice(self.active_indices)
for i in range(self.tries):
point_x, point_y = self.pick_point(self.points[ref_ind])
grid_x, grid_y = math.floor(point_x / self.cell_size), math.floor(point_y / self.cell_size)
neighbor_list = self.neighbors(grid_x, grid_y)
point_ok = True
if neighbor_list:
for neighbor in neighbor_list:
nb_x, nb_y = neighbor
if (point_x - nb_x) * (point_x - nb_x) + (point_y - nb_y) * (point_y - nb_y) < self.radius * self.radius:
point_ok = False
if point_ok:
self.points.append((point_x, point_y))
self.active_indices.append(self.active_iter)
self.samples_grid[grid_x][grid_y] = self.active_iter
self.active_iter += 1
return point_x, point_y
self.active_indices.remove(ref_ind)
return None
def pick_point(self, ref_point):
ref_x, ref_y = ref_point
while True:
rho, theta = random.uniform(self.radius, self.radius2), random.uniform(0, self.pi2)
pick_x, pick_y = ref_x + rho * math.cos(theta), ref_y + rho * math.sin(theta)
if 0 < pick_x < self.field_x and 0 < pick_y < self.field_y:
return pick_x, pick_y
def grid_to_point(self, grid_x, grid_y):
try:
return self.samples_grid[grid_x][grid_y]
except IndexError:
return None
def neighbors(self, grid_x, grid_y):
neighbors_list = (
self.grid_to_point(grid_x, grid_y),
self.grid_to_point(grid_x, grid_y - 1),
self.grid_to_point(grid_x, grid_y + 1),
self.grid_to_point(grid_x - 1, grid_y),
self.grid_to_point(grid_x - 1, grid_y - 1),
self.grid_to_point(grid_x - 1, grid_y + 1),
self.grid_to_point(grid_x + 1, grid_y),
self.grid_to_point(grid_x + 1, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y + 1),
self.grid_to_point(grid_x + 2, grid_y),
self.grid_to_point(grid_x + 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y + 2),
self.grid_to_point(grid_x, grid_y + 2),
self.grid_to_point(grid_x - 1, grid_y + 2),
self.grid_to_point(grid_x - 2, grid_y + 1),
self.grid_to_point(grid_x - 2, grid_y),
self.grid_to_point(grid_x - 2, grid_y - 1),
self.grid_to_point(grid_x + 1, grid_y - 2),
self.grid_to_point(grid_x, grid_y - 2),
self.grid_to_point(grid_x - 1, grid_y - 2)
)
return (self.points[ngb] for ngb in neighbors_list if ngb is not None)
python performance generator
python performance generator
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 43 secs ago
HadwigHadwig
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 43 secs ago
HadwigHadwig
1
asked 43 secs ago
HadwigHadwig
1
1
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hadwig is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Hadwig is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217231%2fspeed-up-fast-poisson-disk-sampling-generator-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Hadwig is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Hadwig is a new contributor. Be nice, and check out our Code of Conduct.
Hadwig is a new contributor. Be nice, and check out our Code of Conduct.
Hadwig is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217231%2fspeed-up-fast-poisson-disk-sampling-generator-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
