Repository: Toblerity/rtree

Issue:
nearest picking just first item
I ran into a case where my index had a large rectangle with a smaller rectangle inside. When I run `nearest` with `num_results=1` on a point inside the smaller rectangle, only 1 result is returned. Since the point is within both (verified by running `intersection`) I would expect that the distance to both items is 0, thus they are both equally near and are both returned. I also noticed that it's always the first one that was inserted into the index that is returned (I swapped the order of insertion and it did not change the result, if one were actually nearer, the result should change).

```python3
from rtree import index

point = (0, 0)
small_box = (-10, -10, 10, 10)
large_box = (-50, -50, 50, 50)

idx = index.Index()
idx.insert(0, small_box)
idx.insert(1, large_box)

print(list(idx.nearest(point, 2)))
print(list(idx.nearest(point, 1)))
print(list(idx.intersection(point)))
print("\n")

# swap order of insertion and index, this should change which one nearest returns
idx = index.Index()
idx.insert(0, large_box)
idx.insert(1, small_box)

print(list(idx.nearest(point, 2)))
print(list(idx.nearest(point, 1)))
print(list(idx.intersection(point)))
print("\n")
```
Output:
```
[0, 1]  # expected output for num_results=2
[0]      # should also be 0, 1
[0, 1]  # intersection confirms point is within both rectangles


[0, 1]  # expected output for num_results=2
[0]      # inconsistent with above result, swapping indexes should make this [1]
[0, 1]  # intersection confirms point is within both rectangles
```

Discussion:
adriangb: Welp not sure why the `Conda Win64 Python38` tester is failing with `OSError: could not find or load spatialindex_c-64.dll`.
adriangb: I suppose it's safe to ignore then.
sr-murthy: @adriangb I was able to checkout the PR (I was using the wrong remote) - all tests pass. That failure on Conda is an environment problem.
sr-murthy: The 64-bit Libspatialindex 1.9.3 lib. does appear to be installed in the Conda Win64 environment

https://dev.azure.com/hobuinc/Rtree/_build/results?buildId=1300&view=logs&j=c874c4c4-56b1-5d29-a8e3-464d971e2eca&t=fc265a19-c6b2-50d3-d5e9-a5b2f378d8f7&l=46

but the Rtree doesn't seem to be able to detect the corresponding DLL. The loading of the DLL involves these lines in `rtree/core.py`

https://github.com/sr-murthy/rtree/blob/master/rtree/core.py#L126

I think you'd need to work backwards to find out why that exception is triggered.
adriangb: > The 64-bit Libspatialindex 1.9.3 lib. does appear to be installed in the Conda Win64 environment
> 
> https://dev.azure.com/hobuinc/Rtree/_build/results?buildId=1300&view=logs&j=c874c4c4-56b1-5d29-a8e3-464d971e2eca&t=fc265a19-c6b2-50d3-d5e9-a5b2f378d8f7&l=46
> 
> but the Rtree doesn't seem to be able to detect the corresponding DLL. The loading of the DLL involves these lines in `rtree/core.py`
> 
> https://github.com/Toblerity/rtree/blob/master/rtree/core.py#L126
> 
> I think you'd need to work backwards to find out why that exception is triggered.

Ok will try to troubleshoot but since I don't have any management access to the Azure pipeline I'm going to be doing it by pushing code with more verbose logging and having the automated build trigger. Sorry if this causes notification bombardment.
hobu: It looks like a bum merge happened in libspatialindex's Conda feedstock that reverted the base library to 1.9.0!  https://github.com/conda-forge/libspatialindex-feedstock/blob/master/recipe/meta.yaml#L1

The DLL name was modified after that release I think. This can be merged. @ocefpaf and I'll will fix that issue.
adriangb: Cool, glad we uncovered that issue as well! It also saved me a lot of blind troubleshooting sweat and tears. Merge whenever you are ready.
adriangb: @hobu I don't mean to bother, but do you have a  schedule to merge / release? I'm trying to implement `nearest` in `geopandas`, it would be helpful to have this bug fixed. Thanks!
hobu: bouncing to see if CI is now cured with libspatialindex conda-forge refresh.
hobu: CI error is #142

Patch:
diff --git a/rtree/index.py b/rtree/index.py
index 69af61b..b90c88d 100644
--- a/rtree/index.py
+++ b/rtree/index.py
@@ -846,6 +846,12 @@ class Index(object):
             return self._nearest_obj(coordinates, num_results, objects)
         p_mins, p_maxs = self.get_coordinate_pointers(coordinates)
 
+        # p_num_results is an input and output for C++ lib
+        # as an input it says "get n closest neighbors"
+        # but if multiple neighbors are at the same distance, both will be returned
+        # so the number of returned neighbors may be > p_num_results
+        # thus p_num_results.contents.value gets set as an output by the C++ lib
+        #  to indicate the actual number of results for _get_ids to use
         p_num_results = ctypes.pointer(ctypes.c_uint64(num_results))
 
         it = ctypes.pointer(ctypes.c_int64())
@@ -857,7 +863,7 @@ class Index(object):
                                           ctypes.byref(it),
                                           p_num_results)
 
-        return self._get_ids(it, min(num_results, p_num_results.contents.value))
+        return self._get_ids(it, p_num_results.contents.value)
 
     def _nearestTP(self, coordinates, velocities, times, num_results=1, objects=False):
         p_mins, p_maxs = self.get_coordinate_pointers(coordinates)


Test patch:
diff --git a/tests/test_index.py b/tests/test_index.py
index 833bb3d..751c945 100644
--- a/tests/test_index.py
+++ b/tests/test_index.py
@@ -340,6 +340,38 @@ class IndexNearest(IndexTestCase):
             idx.add(i, (start, 1, stop, 1))
         hits = sorted(idx.nearest((13, 0, 20, 2), 3))
         self.assertEqual(hits, [3, 4, 5])
+    
+    def test_nearest_equidistant(self):
+        """Test that if records are equidistant, both are returned."""
+        point = (0, 0)
+        small_box = (-10, -10, 10, 10)
+        large_box = (-50, -50, 50, 50)
+
+        idx = index.Index()
+        idx.insert(0, small_box)
+        idx.insert(1, large_box)
+        self.assertEqual(list(idx.nearest(point, 2)), [0, 1])
+        self.assertEqual(list(idx.nearest(point, 1)), [0, 1])
+
+        idx.insert(2, (0, 0))
+        self.assertEqual(list(idx.nearest(point, 2)), [0, 1, 2])
+        self.assertEqual(list(idx.nearest(point, 1)), [0, 1, 2])
+
+        idx = index.Index()
+        idx.insert(0, small_box)
+        idx.insert(1, large_box)
+        idx.insert(2, (50, 50)) # point on top right vertex of large_box
+        point = (51, 51) # right outside of large_box
+        self.assertEqual(list(idx.nearest(point, 2)), [1, 2])
+        self.assertEqual(list(idx.nearest(point, 1)), [1, 2])
+
+        idx = index.Index()
+        idx.insert(0, small_box)
+        idx.insert(1, large_box)
+        idx.insert(2, (51, 51)) # point right outside on top right vertex of large_box
+        point = (51, 52) # shifted 1 unit up from the point above
+        self.assertEqual(list(idx.nearest(point, 2)), [2, 1])
+        self.assertEqual(list(idx.nearest(point, 1)), [2])
 
 
     def test_nearest_object(self):