stefankoegl / kdtree

A Python implementation of a kd-tree

A simple kd-tree in Python

The kdtree package can construct, modify and search kd-trees.

• Website: https://github.com/stefankoegl/kdtree
• Repository: https://github.com/stefankoegl/kdtree.git
• Documentation: https://python-kdtree.readthedocs.org/
• PyPI: https://pypi.python.org/pypi/kdtree
• Travis-CI: https://travis-ci.org/stefankoegl/kdtree
• Coveralls: https://coveralls.io/r/stefankoegl/kdtree

Usage

>>> import kdtree

# Create an empty tree by specifying the number of
# dimensions its points will have
>>> emptyTree = kdtree.create(dimensions=3)

# A kd-tree can contain different kinds of points, for example tuples
>>> point1 = (2, 3, 4)

# Lists can also be used as points
>>> point2 = [4, 5, 6]

# Other objects that support indexing can be used, too
>>> import collections
>>> Point = collections.namedtuple('Point', 'x y z')
>>> point3 = Point(5, 3, 2)

# A tree is created from a list of points
>>> tree = kdtree.create([point1, point2, point3])

# Each (sub)tree is represented by its root node
>>> tree
<KDNode - [4, 5, 6]>

# Adds a tuple to the tree
>>> tree.add( (5, 4, 3) )

# Removes the previously added point and returns the new root
>>> tree = tree.remove( (5, 4, 3) )

# Retrieving the Tree in inorder
>>> list(tree.inorder())
[<KDNode - (2, 3, 4)>, <KDNode - [4, 5, 6]>, <KDNode - Point(x=5, y=3, z=2)>]

# Retrieving the Tree in level order
>>> list(kdtree.level_order(tree))
[<KDNode - [4, 5, 6]>, <KDNode - (2, 3, 4)>, <KDNode - Point(x=5, y=3, z=2)>]

# Find the nearest node to the location (1, 2, 3)
>>> tree.search_nn( (1, 2, 3) )
<KDNode - (2, 3, 4)>

# Add a point to make the tree more interesting
>>> tree.add( (10, 2, 1) )

# Visualize the Tree
>>> kdtree.visualize(tree)


                     [4, 5, 6]

           (2, 3, 4)       Point(x=5, y=3, z=2)

                            (10, 2, 1)

# Take the right subtree of the root
>>> subtree = tree.right

# and detatch it
>>> tree.right = None
>>> kdtree.visualize(tree)

           [4, 5, 6]

      (2, 3, 4)

>>> kdtree.visualize(subtree)

      Point(x=5, y=3, z=2)

      (10, 2, 1)

# and re-attach it
>>> tree.right = subtree
>>> kdtree.visualize(tree)

                     [4, 5, 6]

           (2, 3, 4)       Point(x=5, y=3, z=2)

                            (10, 2, 1)

# Add a node to make the tree unbalanced
>>> tree.is_balanced
True
>>> tree.add( (6, 1, 5) )
>>> tree.is_balanced
False
>>> kdtree.visualize(tree)

                                   [4, 5, 6]

               (2, 3, 4)                           Point(x=5, y=3, z=2)
                                               (10, 2, 1)
                                                       (6, 1, 5)
# rebalance the tree
>>> tree = tree.rebalance()
>>> tree.is_balanced
True
>>> kdtree.visualize(tree)

                Point(x=5, y=3, z=2)

           [4, 5, 6]            (6, 1, 5)

      (2, 3, 4)

Adding a payload

Indexing a dict by a pair of floats is not a good idea, since there might be unexpected precision errors. Since KDTree expects a tuple-looking objects for nodes, you can make a class that looks like a tuple, but contains more data. This way you can store all your data in a kdtree, without using an additional indexed structure.

import kdtree

# This class emulates a tuple, but contains a useful payload
class Item(object):
    def __init__(self, x, y, data):
        self.coords = (x, y)
        self.data = data

    def __len__(self):
        return len(self.coords)

    def __getitem__(self, i):
        return self.coords[i]

    def __repr__(self):
        return 'Item({}, {}, {})'.format(self.coords[0], self.coords[1], self.data)

# Now we can add Items to the tree, which look like tuples to it
point1 = Item(2, 3, 'First')
point2 = Item(3, 4, 'Second')
point3 = Item(5, 2, ['some', 'list'])

# Again, from a list of points
tree = kdtree.create([point1, point2, point3])

#  The root node
print(tree)

# ...contains "data" field with an Item, which contains the payload in "data" field
print(tree.data.data)

# All functions work as intended, a payload is never lost
print(tree.search_nn([1, 2]))

Prints:

<KDNode - Item(3, 4, Second)>
Second
(<KDNode - Item(2, 3, First)>, 2.0)

kdtree's Issues

Preserve function docstrings

Some function docstrings are lost in runtime environment because of require_axis decorator. I think functools.wraps helper will solve this problem.

`KDNode.dist` returns squared distance while `search_nn_dist` requires euclidean distance

The two lines below, one requires dist to be euclidean distance, and the other requires it to be squared distance:
https://github.com/stefankoegl/kdtree/blob/master/kdtree.py#L501
https://github.com/stefankoegl/kdtree/blob/master/kdtree.py#L508

And the best argument is not used
https://github.com/stefankoegl/kdtree/blob/master/kdtree.py#L517

search_knn does not return the nearest neighbor

In the below script, I was looking for the nearest neighbor of [30.702752, -97.740909]. I cooked the values so that the nearest neighbor was [30.702752, -97.740910], but that is not what is returned.

Before rebalancing, I get this output:

BEFORE REBALANCE
Is the tree balanced? False

neighbors before rebalance: 14

Values with in 0.2 distance 0

AFTER REBALANCE
Is the tree balanced? True

neighbors after rebalance: 10

Values with in 0.2 distance [<KDNode - [30.338041, -97.686159]>]

!/usr/bin/python

import kdtree

K = kdtree.create(dimensions=2)

K.add([29.4962939, -98.3192556])
K.add([29.556351, -98.668806])
K.add([30.1963014, -98.1047004])
K.add([29.8630158, -97.958377])
K.add([29.8859993, -97.9248934])
K.add([30.0847352, -97.8413221])
K.add([30.1421844, -97.8330441])
K.add([30.1421844, -97.8330441])
K.add([30.13952999999999, -97.79455879999999])
K.add([30.1569819, -97.8505667])
K.add([30.191694, -98.0914158])
K.add([30.1915751, -98.0847111])
K.add([30.168498, -97.795821])
K.add([30.1722593, -97.8231656])
K.add([30.1756308, -97.7983583])
K.add([30.1918449, -98.0905549])
K.add([30.1588611, -97.7894608])
K.add([30.0991418, -97.7535879])
K.add([30.1735996, -97.7814624])
K.add([30.1929276, -98.0909338])
K.add([30.1962781, -98.1046721])
K.add([30.1929276, -98.0909338])
K.add([30.1996857, -97.7948885])
K.add([30.1996857, -97.7948885])
K.add([30.1997236, -97.7651063])
K.add([30.2032542, -97.7473678])
K.add([30.2032568, -97.7472838])
K.add([30.203676, -98.116154])
K.add([30.2037427, -97.7564172])
K.add([30.2087308, -97.8625561])
K.add([30.211423, -97.7482009])
K.add([30.2032568, -97.7472838])
K.add([30.210184, -97.740911])
K.add([30.2114799, -97.7427211])
K.add([30.210897, -97.74046])
K.add([26.17285, -97.671578])
K.add([27.6648274, -81.5157535])
K.add([28.5078787, -81.4671324])
K.add([29.6045466, -95.4483358])
K.add([30.208641, -97.7339949])
K.add([30.21033, -97.732893])
K.add([30.210698, -97.731771])
K.add([30.2115071, -97.731063])
K.add([30.196311, -97.730807])
K.add([29.7030809, -95.559595])
K.add([29.8818571, -81.2885924])
K.add([30.196311, -97.730807])
K.add([30.2093406, -97.7264432])
K.add([30.2110095, -97.7306804])
K.add([30.20067, -97.715243])
K.add([30.197932, -97.710452])
K.add([30.200169, -97.70627])
K.add([30.200169, -97.70627])
K.add([30.200169, -97.70627])
K.add([30.200169, -97.70627])
K.add([30.1993967, -97.7039363])
K.add([30.2069008, -97.6968357])
K.add([30.207107, -97.7006679])
K.add([30.2126016, -97.7358505])
K.add([30.212909, -97.771361])
K.add([30.24859, -97.865061])
K.add([30.2510727, -97.8631899])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.228876, -97.8622858])
K.add([30.2306687, -97.8172445])
K.add([30.2352925, -97.8469852])
K.add([30.2352925, -97.8469852])
K.add([30.2354494, -97.8416158])
K.add([30.2374432, -97.8401645])
K.add([30.2374432, -97.8401645])
K.add([30.2374432, -97.8401645])
K.add([30.2375909, -97.8353497])
K.add([30.238677, -97.839144])
K.add([30.2392625, -97.8340128])
K.add([30.244005, -97.845965])
K.add([30.232064, -97.82528])
K.add([30.267597, -97.817373])
K.add([30.2756701, -97.81712650000001])
K.add([30.2720257, -97.8165252])
K.add([30.2336623, -97.8111301])
K.add([30.2756701, -97.8171265])
K.add([30.2789396, -97.8120426])
K.add([30.2789946, -97.8192983])
K.add([30.2803158, -97.8085047])
K.add([30.281796, -97.8243188])
K.add([30.2829808, -97.8246638])
K.add([30.2860388, -97.8268933])
K.add([30.2844171, -97.8234802])
K.add([30.2840589, -97.8115775])
K.add([30.2824627, -97.8084894])
K.add([30.2459883, -97.806051])
K.add([30.2459883, -97.806051])
K.add([30.2322763, -97.8042611])
K.add([30.252533, -97.801075])
K.add([30.2744227, -97.8004698])
K.add([30.2860475, -97.8134141])
K.add([30.3050328, -97.9361325])
K.add([30.3022347, -97.8404462])
K.add([30.2886526, -97.8297436])
K.add([30.295638, -97.830817])
K.add([30.2998838, -97.8383356])
K.add([30.2901794, -97.8296949])
K.add([30.29506, -97.82945])
K.add([30.295968, -97.829499])
K.add([30.3041171, -97.8279225])
K.add([30.305511, -97.829696])
K.add([30.306098, -97.9523768])
K.add([30.306016, -97.827663])
K.add([30.2879602, -97.8263844])
K.add([30.2879633, -97.8159793])
K.add([30.2874749, -97.8150668])
K.add([30.2880873, -97.8161978])
K.add([30.301876, -97.8272593])
K.add([30.2534861, -97.8004452])
K.add([30.2237491, -97.7673746])
K.add([30.2237491, -97.7673746])
K.add([30.219243, -97.750714])
K.add([30.2248745, -97.7739802])
K.add([30.222261, -97.7496491])
K.add([30.2277138, -97.7599249])
K.add([30.2305389, -97.7986491])
K.add([30.2340552, -97.7996665])
K.add([30.2421074, -97.7999625])
K.add([30.2384769, -97.7966516])
K.add([30.2415244, -97.7842319])
K.add([30.2421236, -97.7844133])
K.add([30.2421034, -97.7827032])
K.add([30.228822, -97.775122])
K.add([30.242297, -97.781847])
K.add([30.242696, -97.798532])
K.add([30.2432, -97.800063])
K.add([30.2469462, -97.778053])
K.add([30.2504365, -97.800063])
K.add([30.2277138, -97.7599249])
K.add([30.2277138, -97.7599249])
K.add([30.2277138, -97.7599249])
K.add([30.2143366, -97.7474926])
K.add([30.213232, -97.746452])
K.add([30.213232, -97.746452])
K.add([30.259502, -97.74632899999999])
K.add([30.2595332, -97.7935163])
K.add([30.2603717, -97.7914689])
K.add([30.2609407, -97.7899593])
K.add([30.2617673, -97.7883138])
K.add([30.2633268, -97.786436])
K.add([30.2693276, -97.7861845])
K.add([30.2698133, -97.7947305])
K.add([30.2646345, -97.7822573])
K.add([30.2601066, -97.7478977])
K.add([30.262774, -97.758579])
K.add([30.2646345, -97.7822573])
K.add([30.2646345, -97.7822573])
K.add([30.2646345, -97.7822573])
K.add([30.2646345, -97.7822573])
K.add([30.264663, -97.7491153])
K.add([30.2656233, -97.7523567])
K.add([30.267637, -97.780544])
K.add([30.2692966, -97.753153])
K.add([30.2656233, -97.7523567])
K.add([30.2684497, -97.747698])
K.add([30.2692966, -97.753153])
K.add([30.2138124, -97.7463256])
K.add([30.264392, -97.746229])
K.add([30.2656526, -97.7451682])
K.add([30.268229, -97.745996])
K.add([30.2684085, -97.7450719])
K.add([30.2639916, -97.7448263])
K.add([30.2307513, -97.7435296])
K.add([30.263464, -97.743709])
K.add([30.2653441, -97.7435857])
K.add([30.267605, -97.743438])
K.add([30.2660708, -97.7433353])
K.add([30.217122, -97.7433205])
K.add([30.2680007, -97.743168])
K.add([30.2689848, -97.7456684])
K.add([30.2694602, -97.7435136])
K.add([30.2710733, -97.7879991])
K.add([30.2717238, -97.7966935])
K.add([30.271493, -97.755172])
K.add([30.275342, -97.765968])
K.add([30.2758212, -97.7654036])
K.add([30.302574, -97.78430399999999])
K.add([30.3026446, -97.7648555])
K.add([30.287105, -97.761945])
K.add([30.2756438, -97.75047880000001])
K.add([30.27385529999999, -97.7465857])
K.add([30.2982527, -97.7474804])
K.add([30.2761686, -97.7469942])
K.add([30.2979536, -97.7470835])
K.add([30.2740614, -97.7450042])
K.add([30.2762692, -97.7436704])
K.add([30.2762692, -97.7436704])
K.add([30.2781832, -97.7433606])
K.add([30.2858507, -97.7449514])
K.add([30.292365, -97.743826])
K.add([30.29984739999999, -97.7460435])
K.add([30.29984739999999, -97.7460435])
K.add([30.305035, -97.7440589])
K.add([30.3059661, -97.7430818])
K.add([30.2935109, -97.7430327])
K.add([30.2624607, -97.7429043])
K.add([30.26652, -97.7429367])
K.add([30.268573, -97.7429936])
K.add([30.26729, -97.742611])
K.add([30.267633, -97.7427743])
K.add([30.2680316, -97.7427523])
K.add([30.27033, -97.742436])
K.add([30.2700723, -97.7420755])
K.add([30.267859, -97.7410079])
K.add([30.269103, -97.741214])
K.add([30.269103, -97.741214])
K.add([30.269103, -97.741214])
K.add([30.269103, -97.741214])
K.add([30.269103, -97.741214])
K.add([30.269103, -97.741214])
K.add([30.270586, -97.7416363])
K.add([30.270586, -97.7416363])
K.add([30.2695463, -97.740794])
K.add([30.2126016, -97.7358505])
K.add([30.2126016, -97.7358505])
K.add([30.215855, -97.72061])
K.add([30.236987, -97.724017])
K.add([30.2382731, -97.7389412])
K.add([30.266603, -97.738612])
K.add([30.2431418, -97.7368007])
K.add([30.2452888, -97.7313])
K.add([30.2396148, -97.727879])
K.add([30.2621377, -97.7253257])
K.add([30.2134846, -97.7171964])
K.add([30.2134846, -97.7171964])
K.add([30.213875, -97.715079])
K.add([30.2151373, -97.7109173])
K.add([30.2667228, -97.7373688])
K.add([30.270257, -97.740241])
K.add([30.2667228, -97.7373688])
K.add([30.2667228, -97.7373688])
K.add([30.2667228, -97.7373688])
K.add([30.2667228, -97.7373688])
K.add([30.2667228, -97.7373688])
K.add([30.2709, -97.741294])
K.add([30.2799613, -97.7421168])
K.add([30.280717, -97.741386])
K.add([30.3020065, -97.742638])
K.add([30.2857791, -97.73795349999999])
K.add([30.2905183, -97.7226702])
K.add([30.2913432, -97.7227266])
K.add([30.2992334, -97.7195333])
K.add([30.2966983, -97.7186981])
K.add([30.306421, -97.750336])
K.add([30.3096402, -97.9420371])
K.add([30.3099242, -97.939545])
K.add([30.3306009, -97.9674021])
K.add([30.345706, -97.9761622])
K.add([30.3306009, -97.9674021])
K.add([30.334495, -97.966897])
K.add([30.340528, -97.967062])
K.add([30.3433409, -97.9668213])
K.add([30.3101523, -97.93941319999999])
K.add([30.3067256, -97.8266752])
K.add([30.311283, -97.882965])
K.add([30.3162281, -97.8748437])
K.add([30.315841, -97.8734476])
K.add([30.317523, -97.86883399999999])
K.add([30.3140839, -97.8563417])
K.add([30.3170119, -97.8612291])
K.add([30.3102007, -97.82636889999999])
K.add([30.3083865, -97.7599463])
K.add([30.3171472, -97.8244917])
K.add([30.3290096, -97.7829057])
K.add([30.3223062, -97.7560806])
K.add([30.334882, -97.75757759999999])
K.add([30.3349564, -97.8079909])
K.add([30.3349222, -97.8046028])
K.add([30.336973, -97.806704])
K.add([30.337862, -97.7592667])
K.add([30.3222137, -97.7557166])
K.add([30.308272, -97.751996])
K.add([30.306421, -97.750336])
K.add([30.306421, -97.750336])
K.add([30.306421, -97.750336])
K.add([30.306421, -97.750336])
K.add([30.306421, -97.750336])
K.add([30.3067455, -97.75019019999999])
K.add([30.3090134, -97.749964])
K.add([30.3222137, -97.7557166])
K.add([30.3222137, -97.7557166])
K.add([30.3381953, -97.7547418])
K.add([30.3421068, -97.77107470000001])
K.add([30.346837, -97.975769])
K.add([36.778261, -119.4179324])
K.add([34.0489281, -111.0937311])
K.add([30.3514639, -97.75220709999999])
K.add([30.3539473, -97.9624898])
K.add([30.355768, -97.8010011])
K.add([30.3724429, -97.8022287])
K.add([30.355768, -97.8010011])
K.add([30.355768, -97.8010011])
K.add([30.3534866, -97.79713459999999])
K.add([30.353728, -97.7968893])
K.add([30.3524701, -97.7498931])
K.add([30.3568671, -97.7910133])
K.add([30.3536307, -97.74881529999999])
K.add([30.3546435, -97.748601])
K.add([30.3560205, -97.7478497])
K.add([30.3581573, -97.7470475])
K.add([30.35970039999999, -97.747841])
K.add([30.361594, -97.747998])
K.add([30.3656464, -97.7901063])
K.add([30.3618497, -97.74958350000001])
K.add([30.3623083, -97.7486048])
K.add([30.362926, -97.750698])
K.add([30.3656464, -97.7901063])
K.add([30.371554, -97.75603])
K.add([30.3691265, -97.7558954])
K.add([30.3629946, -97.7495617])
K.add([30.3745464, -97.783668])
K.add([30.383169, -97.879667])
K.add([30.4042707, -97.9306967])
K.add([30.4042707, -97.9306967])
K.add([30.3989753, -97.85646179999999])
K.add([30.3745936, -97.7804411])
K.add([30.3752299, -97.7828474])
K.add([30.390716, -97.846895])
K.add([30.390716, -97.846895])
K.add([30.3936072, -97.8502464])
K.add([30.3936072, -97.8502464])
K.add([30.3936072, -97.8502464])
K.add([30.3936072, -97.8502464])
K.add([30.3936072, -97.8502464])
K.add([30.3936072, -97.8502464])
K.add([30.4045489, -97.8490266])
K.add([30.3752299, -97.7828474])
K.add([30.4465913, -97.7789816])
K.add([30.3764005, -97.7783066])
K.add([30.3764005, -97.7783066])
K.add([30.3766101, -97.7642134])
K.add([30.3870532, -97.7599324])
K.add([30.3890106, -97.7563073])
K.add([30.3890106, -97.7563073])
K.add([30.38978999999999, -97.7551766])
K.add([30.3953837, -97.7539663])
K.add([30.4224692, -97.75615429999999])
K.add([30.4312467, -97.7592981])
K.add([30.4364618, -97.7718411])
K.add([30.428971, -97.757775])
K.add([30.4289479, -97.7563477])
K.add([30.390484, -97.7524858])
K.add([30.4312156, -97.7515077])
K.add([30.4315059, -97.7517235])
K.add([30.4315059, -97.7517235])
K.add([30.4315059, -97.7517235])
K.add([30.4477415, -97.7907775])
K.add([30.4563352, -97.7937879])
K.add([30.4542464, -97.79248070000001])
K.add([30.45198049999999, -97.78792589999999])
K.add([30.454496, -97.7888852])
K.add([30.454496, -97.7888852])
K.add([30.454496, -97.7888852])
K.add([30.4563456, -97.7677654])
K.add([30.4564842, -97.7944448])
K.add([30.4748283, -97.8406878])
K.add([30.5184588, -97.835334])
K.add([30.4612804, -97.817084])
K.add([30.5314962, -97.8164518])
K.add([31.9685988, -99.9018131])
K.add([30.503286, -97.800109])
K.add([30.457294, -97.79507])
K.add([30.4568329, -97.79397])
K.add([30.4588131, -97.7913316])
K.add([30.4595268, -97.79429239999999])
K.add([30.4599662, -97.7511013])
K.add([30.503286, -97.800109])
K.add([30.4628337, -97.7894553])
K.add([30.4599662, -97.7511013])
K.add([30.4599662, -97.7511013])
K.add([30.4637134, -97.7956678])
K.add([30.4641957, -97.7942178])
K.add([30.470044, -97.774957])
K.add([30.4732468, -97.7983616])
K.add([30.4800233, -97.7736855])
K.add([30.5309942, -97.7798201])
K.add([30.5154348, -97.7736222])
K.add([30.5154348, -97.7736222])
K.add([30.5154348, -97.7736222])
K.add([30.471771, -97.771317])
K.add([30.471771, -97.771317])
K.add([30.471771, -97.771317])
K.add([30.471771, -97.771317])
K.add([30.471771, -97.771317])
K.add([30.471771, -97.771317])
K.add([30.4188402, -97.7509316])
K.add([30.4013863, -97.7501088])
K.add([30.3902789, -97.7485992])
K.add([30.4013863, -97.7501088])
K.add([30.4013863, -97.7501088])
K.add([30.4013863, -97.7501088])
K.add([30.410349, -97.748632])
K.add([30.428202, -97.748666])
K.add([30.428202, -97.748666])
K.add([30.36000259999999, -97.7467975])
K.add([30.4047284, -97.7464373])
K.add([30.4047284, -97.7464373])
K.add([30.383294, -97.7436589])
K.add([30.382363, -97.743264])
K.add([30.3919702, -97.7447265])
K.add([30.4047284, -97.7464373])
K.add([30.4015886, -97.7429825])
K.add([30.4047284, -97.7464373])
K.add([30.4270838, -97.7433443])
K.add([30.4276607, -97.7445278])
K.add([30.4276607, -97.7445278])
K.add([30.371119, -97.742917])
K.add([30.3617488, -97.7414634])
K.add([30.3276595, -97.7402651])
K.add([30.3308151, -97.740227])
K.add([30.3653414, -97.7396329])
K.add([30.329151, -97.739603])
K.add([30.330019, -97.739495])
K.add([30.3638722, -97.739031])
K.add([30.365853, -97.7383409])
K.add([30.3661852, -97.7395048])
K.add([30.369008, -97.74095])
K.add([30.3728136, -97.7407914])
K.add([30.3730177, -97.7415286])
K.add([30.3734857, -97.7396954])
K.add([30.3748076, -97.7386896])
K.add([30.341443, -97.738221])
K.add([30.3499895, -97.7346039])
K.add([30.3586379, -97.7349222])
K.add([30.373731, -97.736199])
K.add([30.3531337, -97.7337447])
K.add([30.3748792, -97.7357172])
K.add([30.3763501, -97.7348621])
K.add([30.3742325, -97.7324449])
K.add([30.3233254, -97.725397])
K.add([30.3288766, -97.7158329])
K.add([30.3064496, -97.71478669999999])
K.add([30.3134427, -97.71474119999999])
K.add([30.3193618, -97.7095331])
K.add([30.336751, -97.71691])
K.add([30.3756545, -97.7294744])
K.add([30.3768694, -97.7289675])
K.add([30.33877609999999, -97.7192972])
K.add([30.3385963, -97.7186918])
K.add([30.336751, -97.71691])
K.add([30.3449726, -97.713325])
K.add([30.375422, -97.72847])
K.add([30.376642, -97.72622299999999])
K.add([30.36849, -97.7201379])
K.add([30.3777582, -97.7157219])
K.add([30.378215, -97.729669])
K.add([30.3783692, -97.7286662])
K.add([30.379413, -97.727845])
K.add([30.379413, -97.727845])
K.add([30.379863, -97.727369])
K.add([30.3838331, -97.7239734])
K.add([30.3815664, -97.7232188])
K.add([30.3815664, -97.7232188])
K.add([30.3785773, -97.7226448])
K.add([30.379165, -97.71929])
K.add([30.380395, -97.718186])
K.add([30.3793564, -97.7166247])
K.add([30.380932, -97.712956])
K.add([30.3816118, -97.7172416])
K.add([30.3816584, -97.7179838])
K.add([30.38234, -97.711974])
K.add([30.382688, -97.7134279])
K.add([30.384629, -97.722796])
K.add([30.383641, -97.716572])
K.add([30.382926, -97.712733])
K.add([30.383825, -97.712232])
K.add([30.384391, -97.720472])
K.add([30.3845527, -97.7097889])
K.add([30.3847745, -97.7093538])
K.add([30.388946, -97.7415005])
K.add([30.398508, -97.737013])
K.add([30.4002756, -97.7360752])
K.add([30.4004367, -97.7349865])
K.add([30.3893737, -97.7346258])
K.add([30.3975997, -97.7295659])
K.add([30.3975997, -97.7295659])
K.add([30.4002693, -97.7326109])
K.add([30.3931648, -97.7211079])
K.add([30.39442, -97.720187])
K.add([30.3986365, -97.7201568])
K.add([30.394106, -97.719493])
K.add([30.387314, -97.712476])
K.add([30.3875722, -97.7121824])
K.add([30.3903731, -97.7115102])
K.add([30.3915809, -97.7180005])
K.add([30.3917017, -97.7149464])
K.add([30.4009726, -97.7199368])
K.add([30.4016136, -97.7415103])
K.add([30.434012, -97.7398879])
K.add([30.702752, -97.740909])
K.add([30.702752, -97.740910]) # this should be the nearest neighbor
K.add([30.432126, -97.73588799999999])
K.add([30.4017815, -97.723683])
K.add([30.40384629999999, -97.7236638])
K.add([30.432126, -97.73588799999999])
K.add([30.4309159, -97.730534])
K.add([30.4055649, -97.7247125])
K.add([30.4106521, -97.7301769])
K.add([30.4259605, -97.7179173])
K.add([30.3899398, -97.7104401])
K.add([30.393414, -97.70939])
K.add([30.3847745, -97.7093538])
K.add([30.3905724, -97.7093262])
K.add([30.397663, -97.709448])
K.add([30.42436, -97.7101918])
K.add([30.399124, -97.709805])
K.add([30.4129983, -97.7091724])
K.add([30.330879, -97.708519])
K.add([30.2868816, -97.7053068])
K.add([30.2905691, -97.6983944])
K.add([30.2972833, -97.702237])
K.add([30.2997783, -97.7040167])
K.add([30.2973114, -97.7011914])
K.add([30.289146, -97.6975269])
K.add([30.289146, -97.6975269])
K.add([30.3009625, -97.7079169])
K.add([30.3074685, -97.7064682])
K.add([30.319113, -97.700552])
K.add([30.3192396, -97.7004709])
K.add([30.3038975, -97.6990269])
K.add([30.3038975, -97.6990269])
K.add([30.3038975, -97.6990269])
K.add([30.3038975, -97.6990269])
K.add([30.215584, -97.691272])
K.add([30.215584, -97.691272])
K.add([30.322991, -97.697714])
K.add([30.326022, -97.702741])
K.add([30.337662, -97.692687])
K.add([30.3950637, -97.709135])
K.add([30.3950637, -97.709135])
K.add([30.3950637, -97.709135])
K.add([30.3966012, -97.7088071])
K.add([30.389496, -97.708709])
K.add([30.386738, -97.70825])
K.add([30.386738, -97.70825])
K.add([30.3873214, -97.7074622])
K.add([30.34109, -97.704544])
K.add([30.342637, -97.705108])
K.add([30.3873214, -97.7074622])
K.add([30.386734, -97.706288])
K.add([30.3879264, -97.7073449])
K.add([30.342637, -97.705108])
K.add([30.388924, -97.706813])
K.add([30.389938, -97.705615])
K.add([30.3910691, -97.7081319])
K.add([30.3966012, -97.7088071])
K.add([30.400828, -97.708674])
K.add([30.399479, -97.708293])
K.add([30.3934427, -97.7074709])
K.add([30.398797, -97.707356])
K.add([30.352858, -97.688558])
K.add([30.2254766, -97.6871091])
K.add([30.338498, -97.687886])
K.add([30.340242, -97.6876121])
K.add([30.340242, -97.6876121])
K.add([30.2254766, -97.6871091])
K.add([30.2254766, -97.6871091])
K.add([30.2254766, -97.6871091])
K.add([30.2254766, -97.6871091])
K.add([30.2254766, -97.6871091])
K.add([30.337223, -97.686387])
K.add([30.338041, -97.686159])
K.add([30.2167075, -97.6843572])
K.add([30.2167075, -97.6843572])
K.add([30.2167075, -97.6843572])
K.add([30.2554413, -97.6811977])
K.add([30.2748177, -97.6725369])
K.add([30.2748177, -97.6725369])
K.add([30.2764927, -97.6701098])
K.add([30.2975108, -97.6623867])
K.add([30.3337091, -97.6836871])
K.add([30.33654, -97.682822])
K.add([30.338496, -97.6838609])
K.add([30.338496, -97.6838609])
K.add([30.338496, -97.6838609])
K.add([30.338496, -97.6838609])
K.add([30.338496, -97.6838609])
K.add([30.333626, -97.6815834])
K.add([30.32919, -97.673156])
K.add([30.330054, -97.674299])
K.add([30.328859, -97.672502])
K.add([30.333626, -97.6815834])
K.add([30.333626, -97.6815834])
K.add([30.33702, -97.677096])
K.add([30.340507, -97.677699])
K.add([30.3401393, -97.6759802])
K.add([30.340447, -97.6729727])
K.add([30.340447, -97.6729727])
K.add([30.340521, -97.676111])
K.add([30.3403266, -97.6715942])
K.add([30.327751, -97.669922])
K.add([30.3097919, -97.6661263])
K.add([30.322824, -97.6628099])
K.add([30.323256, -97.663146])
K.add([30.330188, -97.6698687])
K.add([30.3312235, -97.6690333])
K.add([30.324674, -97.656585])
K.add([30.332809, -97.659808])
K.add([30.3294455, -97.6482957])
K.add([30.333418, -97.660963])
K.add([30.339539, -97.670213])
K.add([30.333418, -97.660963])
K.add([30.333418, -97.660963])
K.add([30.3379406, -97.6593615])
K.add([30.3374823, -97.6585628])
K.add([30.3407399, -97.6706302])
K.add([30.343254, -97.676913])
K.add([30.343254, -97.676913])
K.add([30.343254, -97.676913])
K.add([30.343254, -97.676913])
K.add([30.3449026, -97.6783794])
K.add([30.3470297, -97.6776131])
K.add([30.3479713, -97.6770407])
K.add([30.3529706, -97.672963])
K.add([30.3407399, -97.6706302])
K.add([30.3407399, -97.6706302])
K.add([30.349338, -97.6688549])
K.add([30.3529706, -97.672963])
K.add([30.3529706, -97.672963])
K.add([30.354197, -97.6720638])
K.add([30.3619857, -97.6863541])
K.add([30.3619857, -97.6863541])
K.add([30.3666148, -97.68184769999999])
K.add([30.354197, -97.6720638])
K.add([30.4044662, -97.6784832])
K.add([30.354197, -97.6720638])
K.add([30.354197, -97.6720638])
K.add([30.354197, -97.6720638])
K.add([30.354197, -97.6720638])
K.add([30.40537, -97.6717375])
K.add([30.3423144, -97.6683743])
K.add([30.3423144, -97.6683743])
K.add([30.3423144, -97.6683743])
K.add([30.3423144, -97.6683743])
K.add([30.3423144, -97.6683743])
K.add([30.3423144, -97.6683743])
K.add([30.400435, -97.65791])
K.add([30.3525184, -97.6453589])
K.add([30.400435, -97.65791])
K.add([30.4091361, -97.680189])
K.add([30.411556, -97.706421])
K.add([30.4096229, -97.7047244])
K.add([30.4127709, -97.7085606])
K.add([30.4130549, -97.7090534])
K.add([30.4151175, -97.704625])
K.add([30.4255898, -97.704251])
K.add([30.4440094, -97.6963055])
K.add([30.4378052, -97.690215])
K.add([30.4446317, -97.7076387])
K.add([30.4446317, -97.7076387])
K.add([30.4446317, -97.7076387])
K.add([30.4446317, -97.7076387])
K.add([30.4446317, -97.7076387])
K.add([30.4446317, -97.7076387])
K.add([30.5426754, -97.6903244])
K.add([30.5297695, -97.6892388])
K.add([30.4698917, -97.6882955])
K.add([30.4851728, -97.6872941])
K.add([30.51417, -97.6890133])
K.add([30.533322, -97.688764])
K.add([30.4840367, -97.6859723])
K.add([30.4464221, -97.6857698])
K.add([30.485833, -97.685573])
K.add([30.534579, -97.685338])
K.add([30.536196, -97.684685])
K.add([30.435961, -97.684008])
K.add([30.4117479, -97.6462326])
K.add([30.4351506, -97.674534])
K.add([30.4298542, -97.667952])
K.add([30.435961, -97.684008])
K.add([30.4150269, -97.6675606])
K.add([30.412991, -97.664699])
K.add([30.4117479, -97.6462326])
K.add([30.4117479, -97.6462326])
K.add([30.4117479, -97.6462326])
K.add([30.4117479, -97.6462326])
K.add([30.415374, -97.664264])
K.add([30.4251595, -97.6636505])
K.add([30.437526, -97.6111892])
K.add([30.440772, -97.6638099])
K.add([30.452455, -97.672896])
K.add([30.453394, -97.672113])
K.add([30.454487, -97.671355])
K.add([30.460008, -97.6706279])
K.add([30.4565735, -97.6595106])
K.add([30.4462101, -97.646699])
K.add([30.461855, -97.670407])
K.add([30.530249, -97.683544])
K.add([30.535836, -97.6836129])
K.add([30.475754, -97.6799319])
K.add([30.475754, -97.6799319])
K.add([30.4868417, -97.67917419999999])
K.add([30.470604, -97.67528999999999])
K.add([30.46655, -97.658018])
K.add([30.4841422, -97.6745827])
K.add([30.513866, -97.621936])
K.add([30.5184036, -97.6766357])
K.add([30.4987417, -97.6011722])
K.add([30.5405058, -97.5531191])
K.add([30.5464849, -97.5413389])
K.add([31.1551865, -97.3624598])
K.add([33.0320276, -96.8275621])
K.add([35.20105, -91.8318334])
K.add([35.5174913, -86.5804473])
K.add([40.927188, -74.172129])
K.add([49.56517700000001, 15.936183])

print "TREE SIZE: ", len([k for k in K.inorder()])

CANDIDATE = [30.702752, -97.740909]

DIST = 0.2
print "Finding Neighbors for: ", CANDIDATE
print ""
#100 neighbors before rebalance

print "BEFORE REBALANCE"
nbrb = K.search_knn(CANDIDATE, 1000)
print "Is the tree balanced?", K.is_balanced
print "# neighbors before rebalance: ", len(nbrb)
print "Values with in 0.2 distance", len(K.search_nn_dist(CANDIDATE, DIST))
print ""

krb = K.rebalance()

after rebalance

print "AFTER REBALANCE"
narb = krb.search_knn(CANDIDATE, 1000)
print "Is the tree balanced?", krb.is_balanced
print "# neighbors after rebalance: ", len(narb)
print "Values with in 0.2 distance", krb.search_nn_dist(CANDIDATE, DIST)
print ""

USE ORIGINAL NODE - SHOULD HAVE BAD RESULTS?

print "OLD NODE"
nbad = K.search_knn(CANDIDATE, 1000)
print "Is the tree balanced?", K.is_balanced
print "# neighbors after rebalance using OLD node: ", len(nbad)
print "Values with in 1.2 distance", len(K.search_nn_dist(CANDIDATE, DIST))
print ""

MANUAL REBALANCING

print "MANUAL REBALANCE"
M = kdtree.create([x.data for x in K.inorder()])
man = K.search_knn(CANDIDATE, 1000)
print "Is the tree balanced?", M.is_balanced
print "# neighbors after rebalance using OLD node: ", len(man)
print "Values with in 0.2 distance", len(M.search_nn_dist(CANDIDATE, DIST))
print ""

support for different distance measures

It could be useful if other distance measures such the L_1 norm (Manhattan distance), L_inf norm (Chebyshev distance) and the the p-norm (Holder norm, where the entries are raised to the power of p, instead to 2 as in the case of the Eucliden norm) are included.
[However, in the p-norm case, extreme values of p can lead to overflow/underflow problems]. A facility to include a user defined norm (or a semi norm) could be also desirable.

Maximum recursion depth exceeded when first removing point from a big kdtree

import random, functools, kdtree
r = functools.partial(random.randint, 1, 100)
points = [(r(), r()) for x in xrange(8000)]
tree = kdtree.create(points)
tree = tree.remove((3,4))

In Python3.5 on Ubuntu 16.04 tree.search_knn method failed with error

tree.search_knn((2,2), 3)
Traceback (most recent call last):
File "", line 1, in
File "/home/user/env/lib/python3.5/site-packages/kdtree.py", line 420, in search_knn
self._search_node(point, k, results, get_dist)
File "/home/user/env/lib/python3.5/site-packages/kdtree.py", line 449, in _search_node
self.left._search_node(point, k, results, get_dist)
File "/home/user/env/lib/python3.5/site-packages/kdtree.py", line 437, in _search_node
results.add((self, nodeDist))
File "/home/user/env/lib/python3.5/site-packages/bounded_priority_queue.py", line 103, in add
self.heap_append(obj)
File "/home/user/env/lib/python3.5/site-packages/bounded_priority_queue.py", line 108, in heap_append
self.propagate_up(len(self.heap) - 1) # Index value is 1 less than length
File "/home/user/env/lib/python3.5/site-packages/bounded_priority_queue.py", line 78, in propagate_up
while index != 0 and self.heap[self.parent(index)][DISTANCE_INDEX] < self.heap[index][DISTANCE_INDEX]:
TypeError: list indices must be integers or slices, not float

Package Distribution?

Could you provide a 'setup.py' so that it can be used as a package?

search_nn does not take "best" parameter into consideration

@require_axis
def search_nn(self, point, best=None):
    """
    Search the nearest node of the given point

    point must be a location, not a node. The nearest node to the point is
    returned. If a location of an actual node is used, the Node with this
    location will be retuend (not its neighbor) """

    return next(iter(self.search_knn(point, 1)), None)

The code for search_nn should probably pass "best" on to its call to search_knn

kdtree does not install cleanly from PyPI

In a clean Python virtualenv, kdtree does not install cleanly with pip install kdtree because bounded_priority_queue.py is missing from the uploaded package:

$ pip install kdtree
Collecting kdtree
  Downloading kdtree-0.14-py2.py3-none-any.whl
Installing collected packages: kdtree
Successfully installed kdtree-0.14

$ python
Python 2.7.10 (default, Sep  4 2015, 19:22:34)
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.51)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import kdtree
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/site-packages/kdtree.py", line 16, in <module>
    from bounded_priority_queue import BoundedPriorityQueue
ImportError: No module named bounded_priority_queue

'list' is unhashable

It seems that we cannot store lists in kdtree. See what i have, when i try to find a nearest neighbours in the kdtree with the list inside.

In [2]: tr = kdtree.create(dimensions=3)

In [3]: tr.add([1,2,3])

In [4]: tr.search_knn( [1,2,3] ,10)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-e685e1032c19> in <module>()
----> 1 tr.search_knn( [1,2,3] ,10)

/kdtree.py in search_knn(self, point, k)
    416 
    417         # the nodes do not keep a reference to their parents
--> 418         parents = {current: None}
    419 
    420         # go down the tree as we would for inserting

/kdtree.py in __hash__(self)
    187 
    188     def __hash__(self):
--> 189         return hash(self.data)
    190 
    191 

TypeError: unhashable type: 'list'

search_knn() is returning multiple values for k=1 also it is very slower than search_nn()

I have been trying to use it for RRT-star implementation, it has increased the time complexity. Also for search_knn(), it is not returning list of length k.

Benchmarks and capabilities

How does this implementation compare in benchmarks to scipy.spatial.cKDTree or sklearn.neighbors.KDTree and is it capable of querying all neighbors within a radius?

Help: TypeError: unsupported operand type(s) for -: 'str' and 'float'

I try to save about 4,700,000 points into the 'kdtree' and call search_nn_dist() but have such error :

Traceback (most recent call last): File "dataloader.py", line 226, in <module> createKdtree('/usr/data/lhw/lixg/eccv/xyz_irgb_label_cleared012.txt') File "dataloader.py", line 206, in createKdtree print(tree.search_nn_dist(p1,1)) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 197, in _wrapper return f(self, *args, **kwargs) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 529, in search_nn_dist self._search_nn_dist(point, distance, results, get_dist) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 499, in _search_nn_dist nodeDist = get_dist(self) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 527, in <lambda> get_dist = lambda n: n.dist(point) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 396, in dist return sum([self.axis_dist(point, i) for i in r]) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 396, in <listcomp> return sum([self.axis_dist(point, i) for i in r]) File "/usr/lhw/anaconda3/lib/python3.5/site-packages/kdtree.py", line 387, in axis_dist return math.pow(self.data[axis] - point[axis], 2) TypeError: unsupported operand type(s) for -: 'str' and 'float'

I am not sure whether the size of my data cause this error, THANKS!

Add persistency capability?

I think it would be extremely useful adding methods to save and load the kdtree to file.

Return None when remove the root node

Return None when remove the root node

distances from search_nn

Is it possible to get the minimum distance (squared) after search_nn without recalculating it?. For higher dimensional trees, distance recalculations could be expensive and should be avoided.

The same question for search_knn and search_nn_dist.

A question in _search_node()

When adding new a node to results(at line 480), why don't you pop the node that has the highest distance if the length of results is k?

v0.15 search_nn_dist does not return the expected point

Hi,

The point is at a distance less than 0.6 But the query result is empty.

Here the unit test:

    def test_search_nn_dist2(self):
        points = [[0.25, 0.25, 1.600000023841858], [0.75, 0.25, 1.600000023841858], [1.25, 0.25, 1.600000023841858],
               [1.75, 0.25, 1.600000023841858], [2.25, 0.25, 1.600000023841858], [2.75, 0.25, 1.600000023841858]]

        expected = [0.25, 0.25, 1.600000023841858]
        tree = kdtree.create(points)
        rmax = 1.0
        search_p = [0.42621034383773804, 0.18793821334838867, 1.44510018825531]
        results = tree.search_nn_dist(search_p, rmax)
        found = False
        for result in results:
            if result.data == expected:
                found = True
                break
        self.assertTrue(found)

Maybe I don't understand the distance parameter ?

Thanks for the help. You library is great !

search_knn appears to be wrong

p = [2, 3, 4, 5, 6]
B=[[1, 2, 3, 4, 5],[1.1, 2.1, 3.1, 4.1, 5.1],[1.2, 2.2, 3.2, 4.2, 5.2],[1.3, 2.3, 3.3, 4.3, 5.3],
[1.4, 2.4, 4.3, 4.4, 5.4], [1.5, 2.5, 3.5, 4.5, 5.5],[1.6, 2.6, 3.6, 4.6, 5.6],
[1.7, 2.7, 3.7, 4.7, 5.7],[1.8, 2.8, 3.8, 4.8, 5.8],[1.9, 2.9, 3.9, 4.9, 5.9]]
TB = kdtree.create(B)
print "The four nearest neighbours in B"
k4=TB.search_knn(p,4)
print "len(k4) = ", len(k4)
for i in range(len(k4)):
print k4[i].data

I get the ouput:

The four nearest neighbours in B
len(k4) = 3
[1.9, 2.9, 3.9, 4.9, 5.9]
[1.8, 2.8, 3.8, 4.8, 5.8]
[1.5, 2.5, 3.5, 4.5, 5.5]
[1.5, 2.5, 3.5, 4.5, 5.5]

More than one Nearest Neighbour

The library looks nice. I wonder if there are anyways to get the N nearest nodes of given node instead of the single node?.

Can't remove custom item with payload

What am I missing here? Looks like remove doesn't work properly for custom items. Using tree = tree.remove( [2, 3, 4], node = r ) for identity check doesn't work either.

import kdtree

class Item(object):
    def __init__(self, x, y, z, data):
        self.coords = (x, y, z)
        self.data = data

    def __len__(self):
        return len(self.coords)

    def __getitem__(self, i):
        return self.coords[i]

    def __repr__(self):
        return 'Item({}, {}, {})'.format(self.coords[0], self.coords[1], self.coords[2], self.data)


tree = kdtree.create(dimensions=3)

tree.add ( Item(2, 3, 4, 'First') )

tree.add ( Item(3, 4, 5, 'Second') )


r = tree.search_nn( [1, 2, 3] )

print(r) # (<KDNode - Item(2, 3, 4)>, 3.0)

tree = tree.remove( [2, 3, 4] )

r = tree.search_nn( [1, 2, 3] )

print(r) # (<KDNode - Item(2, 3, 4)>, 3.0)

search_nn seems to hang (kdtree version 0.8)

import kdtree
A=[(5.1,3.5,1.4,0.2),
(4.9,3.0,1.4,0.2), (4.7,3.2,1.3,0.2), (4.6,3.1,1.5,0.2), (5.0,3.6,1.4,0.2),
(5.4,3.9,1.7,0.4), (4.6,3.4,1.4,0.3), (5.0,3.4,1.5,0.2), (4.4,2.9,1.4,0.2),
(4.9,3.1,1.5,0.1), (5.4,3.7,1.5,0.2), (4.8,3.4,1.6,0.2), (4.8,3.0,1.4,0.1),
(4.3,3.0,1.1,0.1), (5.8,4.0,1.2,0.2), (5.7,4.4,1.5,0.4), (5.4,3.9,1.3,0.4),
(5.1,3.5,1.4,0.3), (5.7,3.8,1.7,0.3), (5.1,3.8,1.5,0.3), (5.4,3.4,1.7,0.2),
(5.1,3.7,1.5,0.4), (4.6,3.6,1.0,0.2), (5.1,3.3,1.7,0.5), (4.8,3.4,1.9,0.2),
(5.0,3.0,1.6,0.2), (5.0,3.4,1.6,0.4), (5.2,3.5,1.5,0.2), (5.2,3.4,1.4,0.2),
(4.7,3.2,1.6,0.2), (4.8,3.1,1.6,0.2), (5.4,3.4,1.5,0.4), (5.2,4.1,1.5,0.1),
(5.5,4.2,1.4,0.2), (4.9,3.1,1.5,0.1), (5.0,3.2,1.2,0.2), (5.5,3.5,1.3,0.2),
(4.9,3.1,1.5,0.1), (4.4,3.0,1.3,0.2), (5.1,3.4,1.5,0.2), (5.0,3.5,1.3,0.3),
(4.5,2.3,1.3,0.3), (4.4,3.2,1.3,0.2), (5.0,3.5,1.6,0.6), (5.1,3.8,1.9,0.4),
(4.8,3.0,1.4,0.3), (5.1,3.8,1.6,0.2), (4.6,3.2,1.4,0.2), (5.3,3.7,1.5,0.2),
(5.0,3.3,1.4,0.2)]

p is the 12th element of A

p = ( 4.8,3.0,1.4,0.1)
T=kdtree.create(A)
print T
nn=T.search_nn(p)
~

How do I keep track of data alongside my points?

Sorry, this is a bit of a question rather than an issue. However....

I'd like to use the namedtuple example to store my points in the tree, but would also like to store some data alongside the points. Is there an easy way to do this? Can it be added to the examples?

I've tried the following:

Point = collections.namedtuple('Point', 'x y name')
point2 = Point(lat, lng, name)
tree.add(point2)

But running this code fails:

ValueError: All Points in the point_list must have the same dimensionality

I guess I could make my own object which 'supports indexing' but as I don't yet know how to do that it seems like a bit of a faff.

search_nn seems to fail

the array is 119x11

there are duplicate rows

when columns are permuted (which changes the tree) the program seems to work

import kdtree
A=[[7.3000, 0.6500, 0.0000, 1.2000, 0.0650, 15.0000, 21.0000, 0.9946, 3.3900, 0.4700, 10.0000] ,
[7.8000, 0.5800, 0.0200, 2.0000, 0.0730, 9.0000, 18.0000, 0.9968, 3.3600, 0.5700, 9.5000] ,
[8.5000, 0.2800, 0.5600, 1.8000, 0.0920, 35.0000, 103.0000, 0.9969, 3.3000, 0.7500, 10.5000] ,
[8.1000, 0.3800, 0.2800, 2.1000, 0.0660, 13.0000, 30.0000, 0.9968, 3.2300, 0.7300, 9.7000] ,
[7.5000, 0.5200, 0.1600, 1.9000, 0.0850, 12.0000, 35.0000, 0.9968, 3.3800, 0.6200, 9.5000] ,
[8.0000, 0.5900, 0.1600, 1.8000, 0.0650, 3.0000, 16.0000, 0.9962, 3.4200, 0.9200, 10.5000] ,
[5.4000, 0.8350, 0.0800, 1.2000, 0.0460, 13.0000, 93.0000, 0.9924, 3.5700, 0.8500, 13.0000] ,
[9.6000, 0.3200, 0.4700, 1.4000, 0.0560, 9.0000, 24.0000, 0.9970, 3.2200, 0.8200, 10.3000] ,
[12.8000, 0.3000, 0.7400, 2.6000, 0.0950, 9.0000, 28.0000, 0.9994, 3.2000, 0.7700, 10.8000] ,
[12.8000, 0.3000, 0.7400, 2.6000, 0.0950, 9.0000, 28.0000, 0.9994, 3.2000, 0.7700, 10.8000] ,
[11.0000, 0.3000, 0.5800, 2.1000, 0.0540, 7.0000, 19.0000, 0.9980, 3.3100, 0.8800, 10.5000] ,
[5.2000, 0.4800, 0.0400, 1.6000, 0.0540, 19.0000, 106.0000, 0.9927, 3.5400, 0.6200, 12.2000] ,
[15.0000, 0.2100, 0.4400, 2.2000, 0.0750, 10.0000, 24.0000, 1.0001, 3.0700, 0.8400, 9.2000] ,
[15.0000, 0.2100, 0.4400, 2.2000, 0.0750, 10.0000, 24.0000, 1.0001, 3.0700, 0.8400, 9.2000] ,
[10.0000, 0.3100, 0.4700, 2.6000, 0.0850, 14.0000, 33.0000, 0.9997, 3.3600, 0.8000, 10.5000] ,
[11.8000, 0.2600, 0.5200, 1.8000, 0.0710, 6.0000, 10.0000, 0.9968, 3.2000, 0.7200, 10.2000] ,
[8.9000, 0.4000, 0.3200, 5.6000, 0.0870, 10.0000, 47.0000, 0.9991, 3.3800, 0.7700, 10.5000] ,
[7.7000, 0.2700, 0.6800, 3.5000, 0.3580, 5.0000, 10.0000, 0.9972, 3.2500, 1.0800, 9.9000] ,
[8.9000, 0.4000, 0.3200, 5.6000, 0.0870, 10.0000, 47.0000, 0.9991, 3.3800, 0.7700, 10.5000] ,
[8.7000, 0.5200, 0.0900, 2.5000, 0.0910, 20.0000, 49.0000, 0.9976, 3.3400, 0.8600, 10.6000] ,
[8.7000, 0.5200, 0.0900, 2.5000, 0.0910, 20.0000, 49.0000, 0.9976, 3.3400, 0.8600, 10.6000] ,
[9.8000, 0.6600, 0.3900, 3.2000, 0.0830, 21.0000, 59.0000, 0.9989, 3.3700, 0.7100, 11.5000] ,
[9.8000, 0.6600, 0.3900, 3.2000, 0.0830, 21.0000, 59.0000, 0.9989, 3.3700, 0.7100, 11.5000] ,
[11.6000, 0.5300, 0.6600, 3.6500, 0.1210, 6.0000, 14.0000, 0.9978, 3.0500, 0.7400, 11.5000] ,
[7.9000, 0.6500, 0.0100, 2.5000, 0.0780, 17.0000, 38.0000, 0.9963, 3.3400, 0.7400, 11.7000] ,
[11.9000, 0.6950, 0.5300, 3.4000, 0.1280, 7.0000, 21.0000, 0.9992, 3.1700, 0.8400, 12.2000] ,
[12.5000, 0.2800, 0.5400, 2.3000, 0.0820, 12.0000, 29.0000, 0.9997, 3.1100, 1.3600, 9.8000] ,
[6.6000, 0.8150, 0.0200, 2.7000, 0.0720, 17.0000, 34.0000, 0.9955, 3.5800, 0.8900, 12.3000] ,
[10.5000, 0.4200, 0.6600, 2.9500, 0.1160, 12.0000, 29.0000, 0.9970, 3.2400, 0.7500, 11.7000] ,
[11.9000, 0.4300, 0.6600, 3.1000, 0.1090, 10.0000, 23.0000, 1.0000, 3.1500, 0.8500, 10.4000] ,
[12.8000, 0.6150, 0.6600, 5.8000, 0.0830, 7.0000, 42.0000, 1.0022, 3.0700, 0.7300, 10.0000] ,
[12.8000, 0.6150, 0.6600, 5.8000, 0.0830, 7.0000, 42.0000, 1.0022, 3.0700, 0.7300, 10.0000] ,
[9.4000, 0.2700, 0.5300, 2.4000, 0.0740, 6.0000, 18.0000, 0.9962, 3.2000, 1.1300, 12.0000] ,
[11.5000, 0.5400, 0.7100, 4.4000, 0.1240, 6.0000, 15.0000, 0.9984, 3.0100, 0.8300, 11.8000] ,
[9.4000, 0.2700, 0.5300, 2.4000, 0.0740, 6.0000, 18.0000, 0.9962, 3.2000, 1.1300, 12.0000] ,
[9.6000, 0.3800, 0.3100, 2.5000, 0.0960, 16.0000, 49.0000, 0.9982, 3.1900, 0.7000, 10.0000] ,
[12.0000, 0.3700, 0.7600, 4.2000, 0.0660, 7.0000, 38.0000, 1.0004, 3.2200, 0.6000, 13.0000] ,
[12.0000, 0.3900, 0.6600, 3.0000, 0.0930, 12.0000, 30.0000, 0.9996, 3.1800, 0.6300, 10.8000] ,
[9.9000, 0.4000, 0.5300, 6.7000, 0.0970, 6.0000, 19.0000, 0.9986, 3.2700, 0.8200, 11.7000] ,
[9.5000, 0.5600, 0.3300, 2.4000, 0.0890, 35.0000, 67.0000, 0.9972, 3.2800, 0.7300, 11.8000] ,
[6.6000, 0.8400, 0.0300, 2.3000, 0.0590, 32.0000, 48.0000, 0.9952, 3.5200, 0.5600, 12.3000] ,
[10.5000, 0.2400, 0.4700, 2.1000, 0.0660, 6.0000, 24.0000, 0.9978, 3.1500, 0.9000, 11.0000] ,
[6.6000, 0.8400, 0.0300, 2.3000, 0.0590, 32.0000, 48.0000, 0.9952, 3.5200, 0.5600, 12.3000] ,
[10.5000, 0.2400, 0.4700, 2.1000, 0.0660, 6.0000, 24.0000, 0.9978, 3.1500, 0.9000, 11.0000] ,
[15.6000, 0.6850, 0.7600, 3.7000, 0.1000, 6.0000, 43.0000, 1.0032, 2.9500, 0.6800, 11.2000] ,
[10.0000, 0.4400, 0.4900, 2.7000, 0.0770, 11.0000, 19.0000, 0.9963, 3.2300, 0.6300, 11.6000] ,
[5.3000, 0.5700, 0.0100, 1.7000, 0.0540, 5.0000, 27.0000, 0.9934, 3.5700, 0.8400, 12.5000] ,
[10.4000, 0.3300, 0.6300, 2.8000, 0.0840, 5.0000, 22.0000, 0.9998, 3.2600, 0.7400, 11.2000] ,
[10.4000, 0.3300, 0.6300, 2.8000, 0.0840, 5.0000, 22.0000, 0.9998, 3.2600, 0.7400, 11.2000] ,
[11.6000, 0.3200, 0.5500, 2.8000, 0.0810, 35.0000, 67.0000, 1.0002, 3.3200, 0.9200, 10.8000] ,
[9.2000, 0.4100, 0.5000, 2.5000, 0.0550, 12.0000, 25.0000, 0.9952, 3.3400, 0.7900, 13.3000] ,
[8.9000, 0.4000, 0.5100, 2.6000, 0.0520, 13.0000, 27.0000, 0.9950, 3.3200, 0.9000, 13.4000] ,
[10.4000, 0.4400, 0.7300, 6.5500, 0.0740, 38.0000, 76.0000, 0.9990, 3.1700, 0.8500, 12.0000] ,
[10.4000, 0.4400, 0.7300, 6.5500, 0.0740, 38.0000, 76.0000, 0.9990, 3.1700, 0.8500, 12.0000] ,
[10.5000, 0.2600, 0.4700, 1.9000, 0.0780, 6.0000, 24.0000, 0.9976, 3.1800, 1.0400, 10.9000] ,
[10.5000, 0.2400, 0.4200, 1.8000, 0.0770, 6.0000, 22.0000, 0.9976, 3.2100, 1.0500, 10.8000] ,
[10.2000, 0.4900, 0.6300, 2.9000, 0.0720, 10.0000, 26.0000, 0.9968, 3.1600, 0.7800, 12.5000] ,
[10.4000, 0.2400, 0.4600, 1.8000, 0.0750, 6.0000, 21.0000, 0.9976, 3.2500, 1.0200, 10.8000] ,
[13.3000, 0.2900, 0.7500, 2.8000, 0.0840, 23.0000, 43.0000, 0.9986, 3.0400, 0.6800, 11.4000] ,
[10.5000, 0.5100, 0.6400, 2.4000, 0.1070, 6.0000, 15.0000, 0.9973, 3.0900, 0.6600, 11.8000] ,
[10.5000, 0.5100, 0.6400, 2.4000, 0.1070, 6.0000, 15.0000, 0.9973, 3.0900, 0.6600, 11.8000] ,
[12.9000, 0.3500, 0.4900, 5.8000, 0.0660, 5.0000, 35.0000, 1.0014, 3.2000, 0.6600, 12.0000] ,
[12.0000, 0.2800, 0.4900, 1.9000, 0.0740, 10.0000, 21.0000, 0.9976, 2.9800, 0.6600, 9.9000] ,
[11.8000, 0.3300, 0.4900, 3.4000, 0.0930, 54.0000, 80.0000, 1.0002, 3.3000, 0.7600, 10.7000] ,
[11.1000, 0.3100, 0.4900, 2.7000, 0.0940, 16.0000, 47.0000, 0.9986, 3.1200, 1.0200, 10.6000] ,
[10.2000, 0.2900, 0.4900, 2.6000, 0.0590, 5.0000, 13.0000, 0.9976, 3.0500, 0.7400, 10.5000] ,
[9.4000, 0.4100, 0.4800, 4.6000, 0.0720, 10.0000, 20.0000, 0.9973, 3.3400, 0.7900, 12.2000] ,
[7.7000, 0.9150, 0.1200, 2.2000, 0.1430, 7.0000, 23.0000, 0.9964, 3.3500, 0.6500, 10.2000] ,
[7.8000, 0.6400, 0.1000, 6.0000, 0.1150, 5.0000, 11.0000, 0.9984, 3.3700, 0.6900, 10.1000] ,
[8.7000, 0.4800, 0.3000, 2.8000, 0.0660, 10.0000, 28.0000, 0.9964, 3.3300, 0.6700, 11.2000] ,
[12.0000, 0.5000, 0.5900, 1.4000, 0.0730, 23.0000, 42.0000, 0.9980, 2.9200, 0.6800, 10.5000] ,
[9.3000, 0.3700, 0.4400, 1.6000, 0.0380, 21.0000, 42.0000, 0.9953, 3.2400, 0.8100, 10.8000] ,
[5.1000, 0.5850, 0.0000, 1.7000, 0.0440, 14.0000, 86.0000, 0.9926, 3.5600, 0.9400, 12.9000] ,
[8.2000, 0.2800, 0.4000, 2.4000, 0.0520, 4.0000, 10.0000, 0.9936, 3.3300, 0.7000, 12.8000] ,
[8.4000, 0.2500, 0.3900, 2.0000, 0.0410, 4.0000, 10.0000, 0.9939, 3.2700, 0.7100, 12.5000] ,
[8.2000, 0.2800, 0.4000, 2.4000, 0.0520, 4.0000, 10.0000, 0.9936, 3.3300, 0.7000, 12.8000] ,
[4.9000, 0.4200, 0.0000, 2.1000, 0.0480, 16.0000, 42.0000, 0.9915, 3.7100, 0.7400, 14.0000] ,
[7.5000, 0.2700, 0.3400, 2.3000, 0.0500, 4.0000, 8.0000, 0.9951, 3.4000, 0.6400, 11.0000] ,
[6.7000, 0.2800, 0.2800, 2.4000, 0.0120, 36.0000, 100.0000, 0.9906, 3.2600, 0.3900, 11.7000] ,
[6.7000, 0.2800, 0.2800, 2.4000, 0.0120, 36.0000, 100.0000, 0.9906, 3.2600, 0.3900, 11.7000] ,
[10.1000, 0.3100, 0.3500, 1.6000, 0.0750, 9.0000, 28.0000, 0.9967, 3.2400, 0.8300, 11.2000] ,
[11.1000, 0.4200, 0.4700, 2.6500, 0.0850, 9.0000, 34.0000, 0.9974, 3.2400, 0.7700, 12.1000] ,
[7.6000, 0.7350, 0.0200, 2.5000, 0.0710, 10.0000, 14.0000, 0.9954, 3.5100, 0.7100, 11.7000] ,
[8.2000, 0.2600, 0.3400, 2.5000, 0.0730, 16.0000, 47.0000, 0.9959, 3.4000, 0.7800, 11.3000] ,
[11.7000, 0.2800, 0.4700, 1.7000, 0.0540, 17.0000, 32.0000, 0.9969, 3.1500, 0.6700, 10.6000] ,
[9.1000, 0.2100, 0.3700, 1.6000, 0.0670, 6.0000, 10.0000, 0.9955, 3.2300, 0.5800, 11.1000] ,
[10.4000, 0.3800, 0.4600, 2.1000, 0.1040, 6.0000, 10.0000, 0.9966, 3.1200, 0.6500, 11.8000] ,
[8.8000, 0.3100, 0.4000, 2.8000, 0.1090, 7.0000, 16.0000, 0.9961, 3.3100, 0.7900, 11.8000] ,
[10.7000, 0.5200, 0.3800, 2.6000, 0.0660, 29.0000, 56.0000, 0.9958, 3.1500, 0.7900, 12.1000] ,
[8.3000, 0.3100, 0.3900, 2.4000, 0.0780, 17.0000, 43.0000, 0.9944, 3.3100, 0.7700, 12.5000] ,
[8.3000, 0.3100, 0.3900, 2.4000, 0.0780, 17.0000, 43.0000, 0.9944, 3.3100, 0.7700, 12.5000] ,
[7.4000, 0.6350, 0.1000, 2.4000, 0.0800, 16.0000, 33.0000, 0.9974, 3.5800, 0.6900, 10.8000] ,
[7.4000, 0.6350, 0.1000, 2.4000, 0.0800, 16.0000, 33.0000, 0.9974, 3.5800, 0.6900, 10.8000] ,
[6.8000, 0.5900, 0.0600, 6.0000, 0.0600, 11.0000, 18.0000, 0.9962, 3.4100, 0.5900, 10.8000] ,
[6.8000, 0.5900, 0.0600, 6.0000, 0.0600, 11.0000, 18.0000, 0.9962, 3.4100, 0.5900, 10.8000] ,
[9.4000, 0.3950, 0.4600, 4.6000, 0.0940, 3.0000, 10.0000, 0.9964, 3.2700, 0.6400, 12.2000] ,
[8.6000, 0.2200, 0.3600, 1.9000, 0.0640, 53.0000, 77.0000, 0.9960, 3.4700, 0.8700, 11.0000] ,
[8.7000, 0.3300, 0.3800, 3.3000, 0.0630, 10.0000, 19.0000, 0.9947, 3.3000, 0.7300, 12.0000] ,
[7.2000, 0.3800, 0.3800, 2.8000, 0.0680, 23.0000, 42.0000, 0.9936, 3.3400, 0.7200, 12.9000] ,
[9.6000, 0.3300, 0.5200, 2.2000, 0.0740, 13.0000, 25.0000, 0.9951, 3.3600, 0.7600, 12.4000] ,
[9.9000, 0.2700, 0.4900, 5.0000, 0.0820, 9.0000, 17.0000, 0.9948, 3.1900, 0.5200, 12.5000] ,
[10.1000, 0.4300, 0.4000, 2.6000, 0.0920, 13.0000, 52.0000, 0.9983, 3.2200, 0.6400, 10.0000] ,
[9.8000, 0.5000, 0.3400, 2.3000, 0.0940, 10.0000, 45.0000, 0.9986, 3.2400, 0.6000, 9.7000] ,
[8.3000, 0.3000, 0.4900, 3.8000, 0.0900, 11.0000, 24.0000, 0.9950, 3.2700, 0.6400, 12.1000] ,
[10.2000, 0.4400, 0.4200, 2.0000, 0.0710, 7.0000, 20.0000, 0.9957, 3.1400, 0.7900, 11.1000] ,
[10.2000, 0.4400, 0.5800, 4.1000, 0.0920, 11.0000, 24.0000, 0.9974, 3.2900, 0.9900, 12.0000] ,
[8.3000, 0.2800, 0.4800, 2.1000, 0.0930, 6.0000, 12.0000, 0.9941, 3.2600, 0.6200, 12.4000] ,
[8.9000, 0.1200, 0.4500, 1.8000, 0.0750, 10.0000, 21.0000, 0.9955, 3.4100, 0.7600, 11.9000] ,
[8.9000, 0.1200, 0.4500, 1.8000, 0.0750, 10.0000, 21.0000, 0.9955, 3.4100, 0.7600, 11.9000] ,
[8.9000, 0.1200, 0.4500, 1.8000, 0.0750, 10.0000, 21.0000, 0.9955, 3.4100, 0.7600, 11.9000] ,
[8.3000, 0.2800, 0.4800, 2.1000, 0.0930, 6.0000, 12.0000, 0.9941, 3.2600, 0.6200, 12.4000] ,
[8.2000, 0.3100, 0.4000, 2.2000, 0.0580, 6.0000, 10.0000, 0.9954, 3.3100, 0.6800, 11.2000] ,
[10.2000, 0.3400, 0.4800, 2.1000, 0.0520, 5.0000, 9.0000, 0.9946, 3.2000, 0.6900, 12.1000] ,
[6.4000, 0.5700, 0.1200, 2.3000, 0.1200, 25.0000, 36.0000, 0.9952, 3.4700, 0.7100, 11.3000] ,
[9.0000, 0.3800, 0.4100, 2.4000, 0.1030, 6.0000, 10.0000, 0.9960, 3.1300, 0.5800, 11.9000] ,
[10.1000, 0.3800, 0.5000, 2.4000, 0.1040, 6.0000, 13.0000, 0.9964, 3.2200, 0.6500, 11.6000] ,
[8.8000, 0.3300, 0.4100, 5.9000, 0.0730, 7.0000, 13.0000, 0.9966, 3.3000, 0.6200, 12.1000] ,
[7.0000, 0.4000, 0.3200, 3.6000, 0.0610, 9.0000, 29.0000, 0.9942, 3.2800, 0.4900, 11.3000] ,
[9.8000, 0.3400, 0.3900, 1.4000, 0.0660, 3.0000, 7.0000, 0.9947, 3.1900, 0.5500, 11.4000] ,
[5.6000, 0.6600, 0.0000, 2.2000, 0.0870, 3.0000, 11.0000, 0.9938, 3.7100, 0.6300, 12.8000] ,
[5.6000, 0.6600, 0.0000, 2.2000, 0.0870, 3.0000, 11.0000, 0.9938, 3.7100, 0.6300, 12.8000] ,
[7.5000, 0.4300, 0.3000, 2.2000, 0.0620, 6.0000, 12.0000, 0.9950, 3.4400, 0.7200, 11.5000] ,
[9.9000, 0.3500, 0.3800, 1.5000, 0.0580, 31.0000, 47.0000, 0.9968, 3.2600, 0.8200, 10.6000] ,
[9.1000, 0.2900, 0.3300, 2.0500, 0.0630, 13.0000, 27.0000, 0.9952, 3.2600, 0.8400, 11.7000] ,
[6.8000, 0.3600, 0.3200, 1.8000, 0.0670, 4.0000, 8.0000, 0.9928, 3.3600, 0.5500, 12.8000] ,
[6.8000, 0.3600, 0.3200, 1.8000, 0.0670, 4.0000, 8.0000, 0.9928, 3.3600, 0.5500, 12.8000] ,
[9.1000, 0.2900, 0.3300, 2.0500, 0.0630, 13.0000, 27.0000, 0.9952, 3.2600, 0.8400, 11.7000] ,
[9.1000, 0.3000, 0.3400, 2.0000, 0.0640, 12.0000, 25.0000, 0.9952, 3.2600, 0.8400, 11.7000] ,
[8.9000, 0.3500, 0.4000, 3.6000, 0.1100, 12.0000, 24.0000, 0.9955, 3.2300, 0.7000, 12.0000] ,
[8.9000, 0.2800, 0.4500, 1.7000, 0.0670, 7.0000, 12.0000, 0.9935, 3.2500, 0.5500, 12.3000] ,
[8.9000, 0.3800, 0.4000, 2.2000, 0.0680, 12.0000, 28.0000, 0.9949, 3.2700, 0.7500, 12.6000] ,
[7.7000, 0.5800, 0.0100, 1.8000, 0.0880, 12.0000, 18.0000, 0.9957, 3.3200, 0.5600, 10.5000] ,
[7.7000, 0.5800, 0.0100, 1.8000, 0.0880, 12.0000, 18.0000, 0.9957, 3.3200, 0.5600, 10.5000] ,
[7.1000, 0.5900, 0.0000, 2.1000, 0.0910, 9.0000, 14.0000, 0.9949, 3.4200, 0.5500, 11.5000] ,
[7.3000, 0.5500, 0.0100, 1.8000, 0.0930, 9.0000, 15.0000, 0.9951, 3.3500, 0.5800, 11.0000] ,
[10.1000, 0.3700, 0.3400, 2.4000, 0.0850, 5.0000, 17.0000, 0.9968, 3.1700, 0.6500, 10.6000] ,
[7.6000, 0.3100, 0.3400, 2.5000, 0.0820, 26.0000, 35.0000, 0.9936, 3.2200, 0.5900, 12.5000] ,
[8.7000, 0.4100, 0.4100, 6.2000, 0.0780, 25.0000, 42.0000, 0.9953, 3.2400, 0.7700, 12.6000] ,
[9.5000, 0.3900, 0.4100, 8.9000, 0.0690, 18.0000, 39.0000, 0.9986, 3.2900, 0.8100, 10.9000] ,
[8.3000, 0.3300, 0.4200, 2.3000, 0.0700, 9.0000, 20.0000, 0.9943, 3.3800, 0.7700, 12.7000] ,
[8.9000, 0.4800, 0.5300, 4.0000, 0.1010, 3.0000, 10.0000, 0.9959, 3.2100, 0.5900, 12.1000] ,
[9.9000, 0.5300, 0.5700, 2.4000, 0.0930, 30.0000, 52.0000, 0.9971, 3.1900, 0.7600, 11.6000] ,
[8.9000, 0.4800, 0.5300, 4.0000, 0.1010, 3.0000, 10.0000, 0.9959, 3.2100, 0.5900, 12.1000] ,
[6.6000, 0.5200, 0.0800, 2.4000, 0.0700, 13.0000, 26.0000, 0.9936, 3.4000, 0.7200, 12.5000] ,
[11.1000, 0.3100, 0.5300, 2.2000, 0.0600, 3.0000, 10.0000, 0.9957, 3.0200, 0.8300, 10.9000] ,
[11.1000, 0.3100, 0.5300, 2.2000, 0.0600, 3.0000, 10.0000, 0.9957, 3.0200, 0.8300, 10.9000] ,
[9.3000, 0.3300, 0.4500, 1.5000, 0.0570, 19.0000, 37.0000, 0.9950, 3.1800, 0.8900, 11.1000] ,
[9.1000, 0.2500, 0.3400, 2.0000, 0.0710, 45.0000, 67.0000, 0.9977, 3.4400, 0.8600, 10.2000] ,
[7.9000, 0.3000, 0.6800, 8.3000, 0.0500, 37.5000, 278.0000, 0.9932, 3.0100, 0.5100, 12.3000] ,
[7.9000, 0.3000, 0.6800, 8.3000, 0.0500, 37.5000, 289.0000, 0.9932, 3.0100, 0.5100, 12.3000] ,
[8.5000, 0.3400, 0.4000, 4.7000, 0.0550, 3.0000, 9.0000, 0.9974, 3.3800, 0.6600, 11.6000] ,
[11.6000, 0.4100, 0.5400, 1.5000, 0.0950, 22.0000, 41.0000, 0.9973, 3.0200, 0.7600, 9.9000] ,
[11.6000, 0.4100, 0.5400, 1.5000, 0.0950, 22.0000, 41.0000, 0.9973, 3.0200, 0.7600, 9.9000] ,
[9.2000, 0.3100, 0.3600, 2.2000, 0.0790, 11.0000, 31.0000, 0.9961, 3.3300, 0.8600, 12.0000] ,
[8.0000, 0.3100, 0.4500, 2.1000, 0.2160, 5.0000, 16.0000, 0.9936, 3.1500, 0.8100, 12.5000] ,
[9.1000, 0.3000, 0.4100, 2.0000, 0.0680, 10.0000, 24.0000, 0.9952, 3.2700, 0.8500, 11.7000] ,
[5.4000, 0.4200, 0.2700, 2.0000, 0.0920, 23.0000, 55.0000, 0.9947, 3.7800, 0.6400, 12.3000] ,
[8.8000, 0.2400, 0.3500, 1.7000, 0.0550, 13.0000, 27.0000, 0.9939, 3.1400, 0.5900, 11.3000] ,
[7.4000, 0.3600, 0.3400, 1.8000, 0.0750, 18.0000, 38.0000, 0.9933, 3.3800, 0.8800, 13.6000] ,
[7.2000, 0.4800, 0.0700, 5.5000, 0.0890, 10.0000, 18.0000, 0.9968, 3.3700, 0.6800, 11.2000] ,
[8.5000, 0.2800, 0.3500, 1.7000, 0.0610, 6.0000, 15.0000, 0.9952, 3.3000, 0.7400, 11.8000] ,
[10.0000, 0.4100, 0.4500, 6.2000, 0.0710, 6.0000, 14.0000, 0.9970, 3.2100, 0.4900, 11.8000] ,
[8.2000, 0.3300, 0.3200, 2.8000, 0.0670, 4.0000, 12.0000, 0.9947, 3.3000, 0.7600, 12.8000] ,
[8.5000, 0.1800, 0.5100, 1.7500, 0.0710, 45.0000, 88.0000, 0.9952, 3.3300, 0.7600, 11.8000] ,
[5.1000, 0.5100, 0.1800, 2.1000, 0.0420, 16.0000, 101.0000, 0.9924, 3.4600, 0.8700, 12.9000] ,
[10.6000, 0.3600, 0.5700, 2.3000, 0.0870, 6.0000, 20.0000, 0.9968, 3.1400, 0.7200, 11.1000] ,
[8.5000, 0.3200, 0.4200, 2.3000, 0.0750, 12.0000, 19.0000, 0.9943, 3.1400, 0.7100, 11.8000] ,
[8.2000, 0.3300, 0.3900, 2.5000, 0.0740, 29.0000, 48.0000, 0.9953, 3.3200, 0.8800, 12.4000] ,
[7.1000, 0.6600, 0.0000, 2.4000, 0.0520, 6.0000, 11.0000, 0.9932, 3.3500, 0.6600, 12.7000] ,
[7.2000, 0.2500, 0.3700, 2.5000, 0.0630, 11.0000, 41.0000, 0.9944, 3.5200, 0.8000, 12.4000] ,
[7.9000, 0.3400, 0.3600, 1.9000, 0.0650, 5.0000, 10.0000, 0.9942, 3.2700, 0.5400, 11.2000] ,
[7.2000, 0.3600, 0.4600, 2.1000, 0.0740, 24.0000, 44.0000, 0.9953, 3.4000, 0.8500, 11.0000] ,
[7.2000, 0.3600, 0.4600, 2.1000, 0.0740, 24.0000, 44.0000, 0.9953, 3.4000, 0.8500, 11.0000] ,
[7.2000, 0.3600, 0.4600, 2.1000, 0.0740, 24.0000, 44.0000, 0.9953, 3.4000, 0.8500, 11.0000] ,
[7.2000, 0.3600, 0.4600, 2.1000, 0.0740, 24.0000, 44.0000, 0.9953, 3.4000, 0.8500, 11.0000] ,
[6.2000, 0.3900, 0.4300, 2.0000, 0.0710, 14.0000, 24.0000, 0.9943, 3.4500, 0.8700, 11.2000] ,
[5.1000, 0.4200, 0.0000, 1.8000, 0.0440, 18.0000, 88.0000, 0.9916, 3.6800, 0.7300, 13.6000] ,
[9.8000, 0.3000, 0.3900, 1.7000, 0.0620, 3.0000, 9.0000, 0.9948, 3.1400, 0.5700, 11.5000] ,
[9.1000, 0.3600, 0.3900, 1.8000, 0.0600, 21.0000, 55.0000, 0.9950, 3.1800, 0.8200, 11.0000] ,
[7.0000, 0.6000, 0.1200, 2.2000, 0.0830, 13.0000, 28.0000, 0.9966, 3.5200, 0.6200, 10.2000] ,
[7.7000, 0.2800, 0.3000, 2.0000, 0.0620, 18.0000, 34.0000, 0.9952, 3.2800, 0.9000, 11.3000] ,
[8.1000, 0.2900, 0.3600, 2.2000, 0.0480, 35.0000, 53.0000, 0.9950, 3.2700, 1.0100, 12.4000] ,
[7.3000, 0.3400, 0.3300, 2.5000, 0.0640, 21.0000, 37.0000, 0.9952, 3.3500, 0.7700, 12.1000] ,
[6.1000, 0.4000, 0.1600, 1.8000, 0.0690, 11.0000, 25.0000, 0.9955, 3.4200, 0.7400, 10.1000] ,
[7.2000, 0.3700, 0.3200, 2.0000, 0.0620, 15.0000, 28.0000, 0.9947, 3.2300, 0.7300, 11.3000] ,
[7.2000, 0.3700, 0.3200, 2.0000, 0.0620, 15.0000, 28.0000, 0.9947, 3.2300, 0.7300, 11.3000] ,
[7.8000, 0.3200, 0.4400, 2.7000, 0.1040, 8.0000, 17.0000, 0.9973, 3.3300, 0.7800, 11.0000] ,
[6.6000, 0.5800, 0.0200, 2.0000, 0.0620, 37.0000, 53.0000, 0.9937, 3.3500, 0.7600, 11.6000] ,
[7.9000, 0.2000, 0.3500, 1.7000, 0.0540, 7.0000, 15.0000, 0.9946, 3.3200, 0.8000, 11.9000] ,
[7.3000, 0.4800, 0.3200, 2.1000, 0.0620, 31.0000, 54.0000, 0.9973, 3.3000, 0.6500, 10.0000] ,
[7.3000, 0.4800, 0.3200, 2.1000, 0.0620, 31.0000, 54.0000, 0.9973, 3.3000, 0.6500, 10.0000] ,
[5.3000, 0.4700, 0.1100, 2.2000, 0.0480, 16.0000, 89.0000, 0.9918, 3.5400, 0.8800, 13.5667] ,
[5.3000, 0.4700, 0.1100, 2.2000, 0.0480, 16.0000, 89.0000, 0.9918, 3.5400, 0.8800, 13.6000] ,
[6.4000, 0.3100, 0.0900, 1.4000, 0.0660, 15.0000, 28.0000, 0.9946, 3.4200, 0.7000, 10.0000] ,
[6.6000, 0.5600, 0.1400, 2.4000, 0.0640, 13.0000, 29.0000, 0.9940, 3.4200, 0.6200, 11.7000] ,
[7.4000, 0.2500, 0.2900, 2.2000, 0.0540, 19.0000, 49.0000, 0.9967, 3.4000, 0.7600, 10.9000] ,
[8.4000, 0.3700, 0.4300, 2.3000, 0.0630, 12.0000, 19.0000, 0.9955, 3.1700, 0.8100, 11.2000] ,
[7.0000, 0.5600, 0.1700, 1.7000, 0.0650, 15.0000, 24.0000, 0.9951, 3.4400, 0.6800, 10.5500] ,
[6.7000, 0.3200, 0.4400, 2.4000, 0.0610, 24.0000, 34.0000, 0.9948, 3.2900, 0.8000, 11.6000] ]
print "size of A = ",len(A), "X", len(A[0])
tree = kdtree.create(A)
point = A[85]
print "point = ",point
nn = tree.search_nn(point)

point and nn.data should be identical

print "nn.data = ",nn.data

a bug in search_nn_dist

import kdtree
points = [(x,y) for x in xrange(10) for y in xrange(10)]
tree = kdtree.create(points)
nn = tree.search_nn_dist((5,5), 2.5)
assert nn == [kdtree.KDNode((5, 5))]
d = kdtree.KDNode((5,5)).dist((6,6))
assert d == 2.0

That means, even though the distance between (5,5) and (6,6) is less than 2.5, tree.search_nn_dist((5,5), 2.5) can't get (6,6) in its result.

Wrong nearest-neighbor result

The following bug was reported by email.

When constructing a kdtree for

points= [(1,2,3),(5,1,2),(9,3,4),(3,9,1),(4,8,3),(9,1,1),(5,0,0),(1,1,1),(7,2,2),(5,9,1),(1,1,9),(9,8,7),(2,3,4),(4,5,4.01)]

the nearest-neighbor for some point is wrong

tree.search_nn((2,5,6))

returns (2,3,4) which has a squared distance of 8. It should, however, return (4,5,4.01) with a distance of 7.9601.

Inconsistency between API docs and API implementations

In search_knn and search_nn, the APIs have an arg named dist, and the API docs say

dist is a distance function, expecting two points and returning distance value. Distance values can be any comparable type.

But in the implementations of the two APIs, only squared Euclidean distance is considered.

actual distances

Is it possible to get the minimum distance (squared) after search_nn without recalculating it?. For higher dimensional trees, distance recalculations could be expensive and should be avoided.

The same question for search_knn and search_nn_dist.

Is it possible to update the node payload?

Is it possible to update the node payload? my goal is to use it like some sort of a database.

bucket kd-trees

Hi,

Thanks for your repo.

I'm wondering it is possible to add bucket kd-trees ? I found Matlab code of it. However, I need it in python.

Thanks.