search

stefankoegl / kdtree

A Python implementation of a kd-tree
ISC License
365 stars 118 forks source link

search_knn does not return the nearest neighbor #21

Closed dalippa closed 8 years ago

dalippa commented 10 years ago

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

stefankoegl commented 9 years ago

I have just released kdtree 0.10. Can you please verify if this is still reproducible?

dalippa commented 9 years ago

I'll take a look when I get into work next week.

dwinston commented 9 years ago

status? I'm interested in this implementation because http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html does not support adding/removing points.

dalippa commented 9 years ago

@stefankoegl I downloaded the latest copy and it looks like the results are better somewhat, but still not correct. I modified the script to run the comparable query with SciPy's KDTree (which is of interest to @dwinston), including the output.

#!/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 ""

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()

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

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

from scipy.spatial import KDTree
import numpy as np

points = [np.array(k.data) for k in K.inorder()]
kdtt = KDTree(points)
neighbors = kdtt.query_ball_point(CANDIDATE, r=DIST)
print "SciPy's KDTree found neighbors ({}) within {}: {}".format(
    len(neighbors), DIST, [points[n] for n in neighbors])

The output when run:

TREE SIZE:  716
Finding Neighbors for:  [30.702752, -97.740909]

BEFORE REBALANCE
Is the tree balanced? False
# neighbors before rebalance:  461
Values with in 0.2 distance 0

AFTER REBALANCE
Is the tree balanced? True
# neighbors after rebalance:  657
Values with in 0.2 distance [<KDNode - [30.338041, -97.686159]>]

OLD NODE
Is the tree balanced? False
# neighbors after rebalance using OLD node:  461
Values with in 1.2 distance 0

MANUAL REBALANCE
Is the tree balanced? True
# neighbors after rebalance using OLD node:  461
Values with in 0.2 distance 1

SciPy's KDTree found neighbors (16) within 0.2: [array([ 30.5314962, -97.8164518]), array([ 30.5309942, -97.7798201]), array([ 30.5154348, -97.7736222]), array([ 30.5154348, -97.7736222]), array([ 30.5154348, -97.7736222]), array([ 30.51417  , -97.6890133]), array([ 30.5297695, -97.6892388]), array([ 30.533322, -97.688764]), array([ 30.530249, -97.683544]), array([ 30.534579, -97.685338]), array([ 30.536196, -97.684685]), array([ 30.535836 , -97.6836129]), array([ 30.5184036, -97.6766357]), array([ 30.5426754, -97.6903244]), array([ 30.702752, -97.740909]), array([ 30.702752, -97.74091 ])]
dalippa commented 9 years ago

@stefankoegl Sorry it's taken me so long to get back to you on this; I ended up using the SciPy KDTree in my project. I had stripped out the native code and replaced necessary functions with pure-Python implementations.

stefankoegl commented 8 years ago

I have just released v0.13, which should fix this issue. If this is still relevant for you, and if the problem is still appearing, please reopen the issue. Thanks!