[Scipy-svn] r4794 - in branches/spatial/scipy/spatial: . tests

scipy-svn@scip... scipy-svn@scip...
Sun Oct 12 08:07:12 CDT 2008


Author: peridot
Date: 2008-10-12 08:06:54 -0500 (Sun, 12 Oct 2008)
New Revision: 4794

Modified:
   branches/spatial/scipy/spatial/kdtree.py
   branches/spatial/scipy/spatial/tests/test_kdtree.py
Log:
Found and fixed a bug when the initial point is outside the tree's bounding box; renamed the dimension of the tree to m  to reduce confusion.


Modified: branches/spatial/scipy/spatial/kdtree.py
===================================================================
--- branches/spatial/scipy/spatial/kdtree.py	2008-10-11 10:36:17 UTC (rev 4793)
+++ branches/spatial/scipy/spatial/kdtree.py	2008-10-12 13:06:54 UTC (rev 4794)
@@ -37,7 +37,7 @@
         """Construct a hyperrectangle."""
         self.maxes = np.maximum(maxes,mins).astype(np.float)
         self.mins = np.minimum(maxes,mins).astype(np.float)
-        self.k, = self.maxes.shape
+        self.m, = self.maxes.shape
 
     def __repr__(self):
         return "<Rectangle %s>" % zip(self.mins, self.maxes)
@@ -124,7 +124,7 @@
             brute-force.
         """
         self.data = np.asarray(data)
-        self.n, self.k = np.shape(self.data)
+        self.n, self.m = np.shape(self.data)
         self.leafsize = int(leafsize)
         if self.leafsize<1:
             raise ValueError("leafsize must be at least 1")
@@ -192,13 +192,19 @@
 
     def __query(self, x, k=1, eps=0, p=2, distance_upper_bound=np.inf):
         
-        side_distances = [max(0,x[i]-self.maxes[i],self.mins[i]-x[i]) for i in range(self.k)]
+        side_distances = np.maximum(0,np.maximum(x-self.maxes,self.mins-x))
+        if p!=np.inf:
+            side_distances**=p
+            min_distance = np.sum(side_distances)
+        else:
+            min_distance = np.amax(side_distances)
+
         # priority queue for chasing nodes
         # entries are:
         #  minimum distance between the cell and the target
         #  distances between the nearest side of the cell and the target
         #  the head node of the cell
-        q = [(distance_p(np.array(side_distances),0),
+        q = [(min_distance,
               tuple(side_distances),                   
               self.tree)]
         # priority queue for the nearest neighbors
@@ -221,13 +227,7 @@
             if isinstance(node, KDTree.leafnode):
                 # brute-force
                 data = self.data[node.idx]
-                a = np.abs(data-x[np.newaxis,:])
-                if p==np.inf:
-                    ds = np.amax(a,axis=1)
-                elif p==1:
-                    ds = np.sum(a,axis=1)
-                else:
-                    ds = np.sum(a**p,axis=1)
+                ds = distance_p(data,x[np.newaxis,:],p)
                 for i in range(len(ds)):
                     if ds[i]<distance_upper_bound:
                         if len(neighbors)==k:
@@ -278,7 +278,7 @@
         Parameters:
         ===========
 
-        x : array-like, last dimension self.k
+        x : array-like, last dimension self.m
             An array of points to query.
         k : integer
             The number of nearest neighbors to return.
@@ -302,7 +302,7 @@
         
         d : array of floats
             The distances to the nearest neighbors. 
-            If x has shape tuple+(self.k,), then d has shape tuple if 
+            If x has shape tuple+(self.m,), then d has shape tuple if 
             k is one, or tuple+(k,) if k is larger than one.  Missing 
             neighbors are indicated with infinite distances.  If k is None, 
             then d is an object array of shape tuple, containing lists 
@@ -313,8 +313,8 @@
             shape as d.
         """
         x = np.asarray(x)
-        if np.shape(x)[-1] != self.k:
-            raise ValueError("x must consist of vectors of length %d but has shape %s" % (self.k, np.shape(x)))
+        if np.shape(x)[-1] != self.m:
+            raise ValueError("x must consist of vectors of length %d but has shape %s" % (self.m, np.shape(x)))
         if p<1:
             raise ValueError("Only p-norms with 1<=p<=infinity permitted")
         retshape = np.shape(x)[:-1]
@@ -399,7 +399,7 @@
         Parameters
         ==========
 
-        x : array_like, shape tuple + (self.k,)
+        x : array_like, shape tuple + (self.m,)
             The point or points to search for neighbors of
         r : positive float
             The radius of points to return
@@ -423,8 +423,8 @@
         substantial amounts of time by putting them in a KDTree and using query_ball_tree.
         """
         x = np.asarray(x)
-        if x.shape[-1]!=self.k:
-            raise ValueError("Searching for a %d-dimensional point in a %d-dimensional KDTree" % (x.shape[-1],self.k))
+        if x.shape[-1]!=self.m:
+            raise ValueError("Searching for a %d-dimensional point in a %d-dimensional KDTree" % (x.shape[-1],self.m))
         if len(x.shape)==1:
             return self.__query_ball_point(x,r,p,eps)
         else:

Modified: branches/spatial/scipy/spatial/tests/test_kdtree.py
===================================================================
--- branches/spatial/scipy/spatial/tests/test_kdtree.py	2008-10-11 10:36:17 UTC (rev 4793)
+++ branches/spatial/scipy/spatial/tests/test_kdtree.py	2008-10-12 13:06:54 UTC (rev 4794)
@@ -66,23 +66,28 @@
 
     def test_approx(self):
         x = self.x
-        m = self.m
+        k = self.k
         eps = 0.1
-        d_real, i_real = self.kdtree.query(x, m)
-        d, i = self.kdtree.query(x, m, eps=eps)
+        d_real, i_real = self.kdtree.query(x, k)
+        d, i = self.kdtree.query(x, k, eps=eps)
         assert np.all(d<=d_real*(1+eps))
 
     
 class test_random(ConsistencyTests):
     def setUp(self):
         self.n = 100
-        self.k = 4
-        self.data = np.random.randn(self.n, self.k)
+        self.m = 4
+        self.data = np.random.randn(self.n, self.m)
         self.kdtree = KDTree(self.data,leafsize=2)
-        self.x = np.random.randn(self.k)
+        self.x = np.random.randn(self.m)
         self.d = 0.2
-        self.m = 10
+        self.k = 10
 
+class test_random_far(test_random):
+    def setUp(self):
+        test_random.setUp(self)
+        self.x = np.random.randn(self.m)+10
+
 class test_small(ConsistencyTests):
     def setUp(self):
         self.data = np.array([[0,0,0],
@@ -95,10 +100,10 @@
                               [1,1,1]])
         self.kdtree = KDTree(self.data)
         self.n = self.kdtree.n
-        self.k = self.kdtree.k
+        self.m = self.kdtree.m
         self.x = np.random.randn(3)
         self.d = 0.5
-        self.m = 4
+        self.k = 4
 
     def test_nearest(self):
         assert_array_equal(
@@ -120,10 +125,10 @@
                               [1,1,1]])
         self.kdtree = KDTree(self.data,leafsize=1)
         self.n = self.kdtree.n
-        self.k = self.kdtree.k
-        self.x = np.random.randn(3)
+        self.m = self.kdtree.m
+        self.x = np.random.randn(self.m)
         self.d = 0.5
-        self.m = 4
+        self.k = 4
 
 
 class test_vectorization:
@@ -193,10 +198,10 @@
 
     def setUp(self):
         n = 100
-        k = 4
-        self.data = np.random.randn(n,k)
+        m = 4
+        self.data = np.random.randn(n,m)
         self.T = KDTree(self.data,leafsize=2)
-        self.x = np.random.randn(k)
+        self.x = np.random.randn(m)
         self.p = 2.
         self.eps = 0
         self.d = 0.2
@@ -228,10 +233,10 @@
 def test_random_ball_vectorized():
 
     n = 20
-    k = 5
-    T = KDTree(np.random.randn(n,k))
+    m = 5
+    T = KDTree(np.random.randn(n,m))
     
-    r = T.query_ball_point(np.random.randn(2,3,k),1)
+    r = T.query_ball_point(np.random.randn(2,3,m),1)
     assert_equal(r.shape,(2,3))
     assert isinstance(r[0,0],list)
 
@@ -253,10 +258,10 @@
 
     def setUp(self):
         n = 50
-        k = 4
-        self.data1 = np.random.randn(n,k)
+        m = 4
+        self.data1 = np.random.randn(n,m)
         self.T1 = KDTree(self.data1,leafsize=2)
-        self.data2 = np.random.randn(n,k)
+        self.data2 = np.random.randn(n,m)
         self.T2 = KDTree(self.data2,leafsize=2)
         self.p = 2.
         self.eps = 0
@@ -316,9 +321,9 @@
 
     def setUp(self):
         n = 50
-        k = 2
-        self.T1 = KDTree(np.random.randn(n,k),leafsize=2)
-        self.T2 = KDTree(np.random.randn(n,k),leafsize=2)
+        m = 2
+        self.T1 = KDTree(np.random.randn(n,m),leafsize=2)
+        self.T2 = KDTree(np.random.randn(n,m),leafsize=2)
         
     def test_one_radius(self):
         r = 0.2
@@ -340,9 +345,9 @@
 class test_sparse_distance_matrix:
     def setUp(self):
         n = 50
-        k = 4
-        self.T1 = KDTree(np.random.randn(n,k),leafsize=2)
-        self.T2 = KDTree(np.random.randn(n,k),leafsize=2)
+        m = 4
+        self.T1 = KDTree(np.random.randn(n,m),leafsize=2)
+        self.T2 = KDTree(np.random.randn(n,m),leafsize=2)
         self.r = 0.3
 
     def test_consistency_with_neighbors(self):



More information about the Scipy-svn mailing list