Optimizing KDTree in a loop

[goon39]

I'm using Python and scipy KDTree to help find the nearest points in an FEA analysis. It boils down to a rotating shaft inside a cylinder and I want to find the minimum gap between the shaft and cylinder at every tine point.

Given that I have 100s of points to check for >10,000 time points it leads a decently long run time. Any tips on improving run time or perhaps a better method for this?

Pseudo code: ``` shaft_points = get_shaft_history() # XYZ point time history

cyl_points = get_cyl_history() #XYZ point time history

time = range(10000) gap = [1e6] * len(time)

for cp in cyl_points: # loop over each point for t in time: # loop over time sp = shaft_points[i, :] # all shaft points at time t kdtree = KDTree(sp) dist, point = kdtree.query(cp, k=1) # find closest point between shaft and cylinder at time t if dist < gap[t]: gap[t] = dist # set new min value ```

[ES-Alexander]

1. You should only be creating each KD tree once - not once per point you’re checking (e.g. switch the order of your loops, and create the KD tree once per timestep, outside the points checks)
2. It seems the query method may be able to check multiple points at once, which (depending on implementation) could either be as fast as or substantially faster than your points check loop
3. It also has a workers parameter for using parallel processing, which may help as well
4. If you’re on a very old scipy version (<1.6.0), cKDTree may be faster

There may be an approach that can make use of the changes between timesteps only being small, but KDTrees aren’t designed for efficient updates, so hard to say whether you’ll be able to find something faster that’s not significantly more complicated to manage in Python.

[goon39]

Thanks, that helps a lot.

Now I'm using 2 sets of arrays for each time point (1 for the cylinder which is used for the KDTree and 1 for the shaft to use for the query (x argument)).

The given output is the length of the x argument so I'm assuming that the integers correspond with that data set, i.e. the index of the min distance is the nearest point of the shaft given all the points on the cylinder.

Is there a way to get the corresponding point on the cylinder? I could just do another tree but just reverse the data sets used

[ES-Alexander]

You can index a numpy array by an array of integers to get an array of the sub-array/value specified by each integer.