#### Is there a KDTree that provides an iterator in Python3?

A KDTree is a tree indexed by N-D position in space. If I have an item with coordinate `[1,2,3]` and another item with coordinate `[1.0001,2,3]`, then a `KDTree` would return this nearest neighbor in a single `O(logN)` operation.

I have an algorithmic approach where I would like to sort the whole set of items in the KDTree by distance from the incident object.

``````incident_obj_coords = coords(incident_obj)
sorting = myKDTree.query(incident_obj_coords, count=len(myKdTree))
``````

Then, I proceed along my sorting to find the best item:

``````score_threshold = 0.95
best_score = -inf
best_item = None
for item in sorting:
score = similarity(item, incident_obj)
if score > best_score:
best_item = item
best_score = score
if score > score_threshold:
break
``````

Well, the above situation has complexity `O(N*log(N))`; what I would like is an `O(log(N))` amortized runtime.

In order to get an `O(log(N))` amortized runtime during the query, I need a `KDTree.query_iterator` that only gets the next item in the query when I need it (lazily):

``````score_threshold = 0.95
best_score = -inf
best_item = None
kd_it = myKDTree.query_iterator(incident_obj_coords)
while True:
nxt = next(kd_it,None)

if nxt is None:
break

score = similarity(item, incident_obj)

if score > best_score:
best_item = item
best_score = score

if score > score_threshold:
break
``````

Is there a `KDTree` in the python3 toolkit that can provide this sort of incremental search?

Source: Python-3x Questions