CODEWITHSUNDEEP
pythonkdtreescipy-spatial
horsemeat
horsemeat

Reputation: 21

How to find points in scipy KDTree between two radii of a position

I have a set of locations in a KDTree object and I need to efficiently find the points that are more than r1 but less than r2 distance away

Is there a better way than:

idx_1 = kd_tree.query_ball_point(pos, r1)
idx_2 = kd_tree.query_ball_point(pos, r2)
# ...
idx_n = kd_tree.query_ball_point(pos, rn)

and then iterating over all the lists and popping out the indices or iterating through each point and checking for range?

KDTree.query()

Will provide indices and their distances but you have to specify the number of points to return which is not predictable.

Edit: I think I found an easy way to partition out indices via this solution: Get difference between two lists with Unique Entries

but it still requires running KDTree.query_ball_point() multiple times

Upvotes: 1

Views: 92

Answers (1)

J_H
J_H

Reputation: 20435

You didn't describe any aspects of the Business Domain that are motivating your use case.

WLOG let's consider some 2-D bullseyes. Given r1=40 and r2=50, we seek an unknown number of matching points in an annulus of width ten.

Drop a circle onto the X axis, centered on (45, 0). Choose some convenient radius, greater than five. Theta is zero, that is, pointing along the X axis. Increase theta so we can drop another such circle, completely covering the next portion of the annulus. Continue dropping circular search regions until we have returned to our starting point. Issue .query_ball_point() queries for each of them, and filter by r1 < r < r2 to obtain the final results.

In higher dimensional spaces this can lead to an annoyingly large number of queries, which possibly is balanced by sparse volumes that offer zero result points. Based on just the assumptions outlined in OP, it's unclear whether this approach would be winning, compared to simple difference of a pair of result sets.

A single query for r2 suffices. Then examine each result point, filtering them against the r1 criterion.

This may run faster than issuing a pair of queries.

Upvotes: 0

Related Questions