Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve performance on generate_unit_locations #3419

Open
3 tasks
h-mayorquin opened this issue Sep 16, 2024 · 0 comments
Open
3 tasks

Improve performance on generate_unit_locations #3419

h-mayorquin opened this issue Sep 16, 2024 · 0 comments
Labels
performance Performance issues/improvements

Comments

@h-mayorquin
Copy link
Collaborator

Currently the generate_unic_locations enforces the unit constrain with a simple rejection sampling algorithm that is non-deterministic:

if minimum_distance is not None:
solution_found = False
renew_inds = None
for i in range(max_iteration):
distances = np.linalg.norm(units_locations[:, np.newaxis] - units_locations[np.newaxis, :], axis=2)
inds0, inds1 = np.nonzero(distances < minimum_distance)
mask = inds0 != inds1
inds0 = inds0[mask]
inds1 = inds1[mask]
if inds0.size > 0:
if renew_inds is None:
renew_inds = np.unique(inds0)
else:
# random only bad ones in the previous set
renew_inds = renew_inds[np.isin(renew_inds, np.unique(inds0))]
units_locations[:, 0][renew_inds] = rng.uniform(minimum_x, maximum_x, size=renew_inds.size)
units_locations[:, 1][renew_inds] = rng.uniform(minimum_y, maximum_y, size=renew_inds.size)
units_locations[:, 2][renew_inds] = rng.uniform(minimum_z, maximum_z, size=renew_inds.size)
else:
solution_found = True
break

But I think this is a clear use case for the Bridson's algorithm for sampling on a poison disk with is log(N)

https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

  • Time the current implementation for some channel locations
  • Implement Bridson algorithm in Python
  • Profile it.

This is a good first issue.

@h-mayorquin h-mayorquin added the performance Performance issues/improvements label Sep 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Performance issues/improvements
Projects
None yet
Development

No branches or pull requests

1 participant