1

I have the position data for particles in 3D space. The particles are in random positions in the 3D box and I am trying to find the position of the maximum number density. Is there a simple algorithm to do this efficiently (I have a few million particles)? I have tried to use a similar idea to the centre of mass of the system (code is below). This gives me the centre of mass..is there a similar approach to find the position of the maximum number density? I was thinking of making some 3d cube and separating it out into smaller cubes to the the number of particles within each cube....but that will take very long for many particles.

import numpy as np

X_data = np.random.random(100000) # x coordinates
Y_data = np.random.random(100000) # y-coordinates
Z_data = np.random.random(100000) # z-coordinates
#Assume all points are weighted equally

com_x = np.mean(X_data)
com_y = np.mean(Y_data)
com_z = np.mean(Z_data)
#Now have the centre of mass position
Warrenmovic
  • 111
  • 3
  • Something with [histogramdd](https://numpy.org/doc/stable/reference/generated/numpy.histogramdd.html) – Quang Hoang Jun 05 '20 at 19:48
  • @QuangHoang thanks for that, I have not used this before. Do you know how this works? – Warrenmovic Jun 05 '20 at 19:50
  • Well in statistics you have ways to measure the center of a distribution, usually with mean, median, and mode. And what you are looking for is a way to measure the dispersion, some methods of doing that include "range and quartiles of the data-set, and measures of spread such as the variance and standard deviation" - [Wikipedia](https://en.wikipedia.org/wiki/Descriptive_statistics#Univariate_analysis). What I am trying to say is: try to implement or find a function that does a standard deviation or quartiles of the dataset. – Yonlif Jun 05 '20 at 19:55
  • I'm pretty sure the "position of maximum density" doesn't make sense when all you have are points. Or rather, it would be any or all of those points. What would make sense is a volume (probably a ball) of maximum density, given a radius. Another possibility is that your particles are not just points, but instead are spread out in a volume (probably a ball as well), with some density function of the distance from their position. – Nelfeal Jun 05 '20 at 20:52
  • see [Finding holes in 2d point sets?](https://stackoverflow.com/a/21884021/2521214) So create a density map `O(n)` select the grid cell with highest density and recursively subdivide the density map ... It can be done along with spatial ordering of the points (in the same step) resulting in `~O(n.log(n))` – Spektre Jun 06 '20 at 08:27
  • @Spektre is there an example of a code that does this in Python – Warrenmovic Jun 07 '20 at 09:59
  • @Nelfeal Yes your are right, I guess as I am in 3D I would be looking for the largest number density in a enclosing sphere – Warrenmovic Jun 07 '20 at 10:00
  • @Warrenmovic I do not code in python but I assume you could find any octree spatial subdivision example for python ... its basically almost the same thing .. – Spektre Jun 07 '20 at 10:03
  • @Spektre thanks for that, is there a code example you could point me to...I have not used an octree algorithm before – Warrenmovic Jun 07 '20 at 10:18
  • 1
    @Warrenmovic type `octree python point cloud` into google another option s to look for BVH (Bounding Volume Hierarchy) – Spektre Jun 07 '20 at 10:20
  • 1
    @Warrenmovic You still need to specify a radius for the ball, or some sort of density function to weigh particles depending on their distance to the ball's center. – Nelfeal Jun 07 '20 at 10:45
  • @Nelfeal yes that is a good point. Is there any recommended way of doing this? – Warrenmovic Jun 07 '20 at 10:47
  • @Warrenmovic I have no idea. I would say it really depends on you and what you need. Imagine the problem in 2D, with two groups of points. One group contains fewer points than the other but they are also closer to each other than in the other group. Which group do you think is the most dense? It all depends on how you weigh the points. If you pick a specific radius, that's equivalent to picking distribution where points weigh 1 until they are too far, and then they weigh 0. If the distribution you pick favors the center a lot more, you would choose the first group (depending on the scale). – Nelfeal Jun 07 '20 at 10:56

0 Answers0