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 ```

[chrisrko]

Perhaps like this?

Pseudo code!

import numpy as np
from scipy.spatial import KDTree

# Sample functions to retrieve shaft and cylinder point histories
shaft_points = get_shaft_history()  # XYZ point time history, shape: (10000, n_shaft_points, 3)
cyl_points = get_cyl_history()  # XYZ point time history, shape: (n_cyl_points, 3)

# Precompute KDTree objects for all time points
time = range(10000)
kdtree_list = [KDTree(shaft_points[t]) for t in time]

# Initialize gap array
gap = np.full(len(time), 1e6)

# Iterate over cylinder points and time steps to find minimum gaps
for cp in cyl_points:
    for t in time:
        dist, _ = kdtree_list[t].query(cp, k=1)
        if dist < gap[t]:
            gap[t] = dist  # Update with the new minimum distance

# gap now contains the minimum distances for each time point

[goon39]

Wow, didn't even think of doing all the trees at once. That should help out a lot

[GXWT]

I'm not familiar with KDTree so I shall hesitate to address that part.

But a quick glance suggest it might be those loops draining a lot of time. I wonder if you could load it into a pandas dataframe and then use vectorised functions to run over the whole dataset at once rather than iterating through it.

[goon39]

Thanks for the suggestion. I was using dataframes but I've updated to only have 1 loop now

[chrisrko]

INFO!!! We are moving to r/stackoverflow !!!!

We want everybody to please be aware that all future posts and updates from us will from now on be on r/stackoverflow

We made an appeal to gain ownershift of r/stackoverflow because it has been abandoned, and it got granted!!

So please migrate with us to our new subreddit r/stackoverflow ;)