Repository: kip-hart/AABBTree

Issue:
Getting boundaries of the overlaps
Hi! Is there any method to actually get the boundaries or of the overlapping boxes inside a tree?
Now I can use the "does_overlap(aabb_obj)" method of the AABBTree to check for overlaps but it says nothing about the exact box which overlaps given aabb_obj, only "yes/no" answer.

Or maybe return the AABBTree object with an overlapping box as a root of subtree would be a nice solution.

Thanks.



Discussion:

Patch:
diff --git a/LICENSE.rst b/LICENSE.rst
index 758b79b..4f5d74e 100644
--- a/LICENSE.rst
+++ b/LICENSE.rst
@@ -1,6 +1,6 @@
 MIT License
 
-Copyright (c) 2019 Georgia Tech Research Corporation
+Copyright (c) 2020 Georgia Tech Research Corporation
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
diff --git a/MANIFEST.in b/MANIFEST.in
index d000627..d8346a3 100644
--- a/MANIFEST.in
+++ b/MANIFEST.in
@@ -1,7 +1,7 @@
 graft docs
 graft tests
 
-include aabb.py
+include aabbtree.py
 
 include .bumpversion.cfg
 include .coveragerc
@@ -15,6 +15,7 @@ include tox.ini
 prune docs/source/_static
 prune docs/build
 
+exclude CONTRIBUTING.rst
 exclude plot_incremental.py
 
 global-exclude *.py[cod] __pycache__ *.so *.dylib .DS_Store *.log Icon*
diff --git a/README.rst b/README.rst
index 2e3be81..40d0a7e 100644
--- a/README.rst
+++ b/README.rst
@@ -103,7 +103,7 @@ create a pull request, and submit issues.
 License and Copyright Notice
 ============================
 
-Copyright |copy| 2019, Georgia Tech Research Corporation
+Copyright |copy| 2020, Georgia Tech Research Corporation
 
 AABBTree is open source and freely available under the terms of
 the MIT license.
diff --git a/aabbtree.py b/aabbtree.py
index dc6bd09..90445ed 100644
--- a/aabbtree.py
+++ b/aabbtree.py
@@ -1,4 +1,5 @@
 import copy
+from collections import deque
 
 __all__ = ['AABB', 'AABBTree']
 __author__ = 'Kenneth (Kip) Hart'
@@ -66,10 +67,10 @@ class AABB(object):
             return True
         if (self.limits is None) or (aabb.limits is None):
             return False
-        if len(self) != len(aabb):
+        if len(self.limits) != len(aabb.limits):
             return False
 
-        for i, lims1 in enumerate(self):
+        for i, lims1 in enumerate(self.limits):
             lims2 = aabb[i]
             if (lims1[0] != lims2[0]) or (lims1[1] != lims2[1]):
                 return False
@@ -98,18 +99,12 @@ class AABB(object):
         if aabb2.limits is None:
             return cls(aabb1.limits)
 
-        if len(aabb1) != len(aabb2):
+        if len(aabb1.limits) != len(aabb2.limits):
             e_str = 'AABBs of different dimensions: ' + str(len(aabb1))
             e_str += ' and ' + str(len(aabb2))
             raise ValueError(e_str)
 
-        merged_limits = []
-        n = len(aabb1)
-        for i in range(n):
-            lower = min(aabb1[i][0], aabb2[i][0])
-            upper = max(aabb1[i][1], aabb2[i][1])
-            merged_limits.append((lower, upper))
-        return cls(merged_limits)
+        return cls([_merge(*lims) for lims in zip(aabb1.limits, aabb2.limits)])
 
     @property
     def perimeter(self):
@@ -126,11 +121,11 @@ class AABB(object):
             p_n &= 2 \sum_{i=1}^n \prod_{j=1\neq i}^n l_j
 
         """
-        if len(self) == 1:
+        if len(self.limits) == 1:
             return 0
 
         perim = 0
-        side_lens = [ub - lb for lb, ub in self]
+        side_lens = [ub - lb for lb, ub in self.limits]
         n_dim = len(side_lens)
         for i in range(n_dim):
             p_edge = 1
@@ -156,7 +151,7 @@ class AABB(object):
 
         """
         vol = 1
-        for lb, ub in self:
+        for lb, ub in self.limits:
             vol *= ub - lb
         return vol
 
@@ -187,12 +182,10 @@ class AABB(object):
         if (self.limits is None) or (aabb.limits is None):
             return False
 
-        for lims1, lims2 in zip(self, aabb):
-            min1, max1 = lims1
-            min2, max2 = lims2
-
-            overlaps = (max1 >= min2) and (min1 <= max2)
-            if not overlaps:
+        for (min1, max1), (min2, max2) in zip(self.limits, aabb.limits):
+            if min1 >= max2:
+                return False
+            if min2 >= max1:
                 return False
         return True
 
@@ -219,10 +212,7 @@ class AABB(object):
         """  # NOQA: E501
 
         volume = 1
-        for lims1, lims2 in zip(self, aabb):
-            min1, max1 = lims1
-            min2, max2 = lims2
-
+        for (min1, max1), (min2, max2) in zip(self.limits, aabb.limits):
             overlap_min = max(min1, min2)
             overlap_max = min(max1, max2)
             if overlap_min >= overlap_max:
@@ -435,7 +425,7 @@ class AABBTree(object):
                 self.right.add(aabb, value)
             self.aabb = AABB.merge(self.left.aabb, self.right.aabb)
 
-    def does_overlap(self, aabb):
+    def does_overlap(self, aabb, method='DFS'):
         """Check for overlap
 
         This function checks if the limits overlap any leaf nodes in the tree.
@@ -443,42 +433,133 @@ class AABBTree(object):
 
         Args:
             aabb (AABB): The AABB to check.
+            method (str): {'DFS'|'BFS'} Method for traversing the tree.
+                Setting 'DFS' performs a depth-first search and 'BFS' performs
+                a breadth-first search. Defaults to 'DFS'.
 
         Returns:
             bool: True if overlaps with a leaf node of tree.
         """
-        if self.is_leaf:
-            return self.aabb.overlaps(aabb)
+        if method == 'DFS':
+            if self.is_leaf:
+                return self.aabb.overlaps(aabb)
 
-        left_aabb_over = self.left.aabb.overlaps(aabb)
-        right_aabb_over = self.right.aabb.overlaps(aabb)
+            left_aabb_over = self.left.aabb.overlaps(aabb)
+            right_aabb_over = self.right.aabb.overlaps(aabb)
 
-        if left_aabb_over and self.left.does_overlap(aabb):
-            return True
-        if right_aabb_over and self.right.does_overlap(aabb):
-            return True
-        return False
+            if left_aabb_over and self.left.does_overlap(aabb):
+                return True
+            if right_aabb_over and self.right.does_overlap(aabb):
+                return True
+            return False
+
+        if method == 'BFS':
+            q = deque()
+            q.append(self)
+            while len(q) > 0:
+                node = q.popleft()
+                overlaps = node.aabb.overlaps(aabb)
+                if overlaps and node.is_leaf:
+                    return True
+                if overlaps:
+                    q.append(node.left)
+                    q.append(node.right)
+            return False
+
+        e_str = "method should be 'DFS' or 'BFS', not " + str(method)
+        raise ValueError(e_str)
+
+    def overlap_aabbs(self, aabb, method='DFS'):
+        """Get overlapping AABBs
+
+        This function gets each overlapping AABB.
+
+        Args:
+            aabb (AABB): The AABB to check.
+            method (str): {'DFS'|'BFS'} Method for traversing the tree.
+                Setting 'DFS' performs a depth-first search and 'BFS' performs
+                a breadth-first search. Defaults to 'DFS'.
 
-    def overlap_values(self, aabb):
+        Returns:
+            list: AABB objects in AABBTree that overlap with the input.
+        """
+        aabbs = []
+
+        if method == 'DFS':
+            is_leaf = self.is_leaf
+            if is_leaf and self.does_overlap(aabb):
+                aabbs.append(self.aabb)
+            elif is_leaf:
+                pass
+            else:
+                if self.left.aabb.overlaps(aabb):
+                    aabbs.extend(self.left.overlap_aabbs(aabb))
+
+                if self.right.aabb.overlaps(aabb):
+                    aabbs.extend(self.right.overlap_aabbs(aabb))
+        elif method == 'BFS':
+            q = deque()
+            q.append(self)
+            while len(q) > 0:
+                node = q.popleft()
+                if node.aabb.overlaps(aabb):
+                    if node.is_leaf:
+                        aabbs.append(node.aabb)
+                    else:
+                        q.append(node.left)
+                        q.append(node.right)
+        else:
+            e_str = "method should be 'DFS' or 'BFS', not " + str(method)
+            raise ValueError(e_str)
+        return aabbs
+
+    def overlap_values(self, aabb, method='DFS'):
         """Get values of overlapping AABBs
 
         This function gets the value field of each overlapping AABB.
 
         Args:
             aabb (AABB): The AABB to check.
+            method (str): {'DFS'|'BFS'} Method for traversing the tree.
+                Setting 'DFS' performs a depth-first search and 'BFS' performs
+                a breadth-first search. Defaults to 'DFS'.
 
         Returns:
             list: Value fields of each node that overlaps.
         """
         values = []
-        if self.is_leaf and self.does_overlap(aabb):
-            values.append(self.value)
-        elif self.is_leaf:
-            pass
-        else:
-            if self.left.aabb.overlaps(aabb):
-                values.extend(self.left.overlap_values(aabb))
 
-            if self.right.aabb.overlaps(aabb):
-                values.extend(self.right.overlap_values(aabb))
+        if method == 'DFS':
+            is_leaf = self.is_leaf
+            if is_leaf and self.does_overlap(aabb):
+                values.append(self.value)
+            elif is_leaf:
+                pass
+            else:
+                if self.left.aabb.overlaps(aabb):
+                    values.extend(self.left.overlap_values(aabb))
+
+                if self.right.aabb.overlaps(aabb):
+                    values.extend(self.right.overlap_values(aabb))
+        elif method == 'BFS':
+            q = deque()
+            q.append(self)
+            while len(q) > 0:
+                node = q.popleft()
+                if node.aabb.overlaps(aabb):
+                    if node.is_leaf:
+                        values.append(node.value)
+                    else:
+                        q.append(node.left)
+                        q.append(node.right)
+        else:
+            e_str = "method should be 'DFS' or 'BFS', not " + str(method)
+            raise ValueError(e_str)
         return values
+
+
+def _merge(lims1, lims2):
+    lb = min(lims1[0], lims2[0])
+    ub = max(lims1[1], lims2[1])
+
+    return (lb, ub)
diff --git a/docs/source/conf.py b/docs/source/conf.py
index e75c26f..355f93f 100644
--- a/docs/source/conf.py
+++ b/docs/source/conf.py
@@ -20,13 +20,13 @@ sys.path.insert(0, os.path.abspath('../../'))
 # -- Project information -----------------------------------------------------
 
 project = 'AABBTree'
-copyright = '2019, Georgia Tech Research Corporation'
+copyright = '2020, Georgia Tech Research Corporation'
 author = 'Kenneth Hart'
 
 # The short X.Y version
-version = '2.4'
+version = '2.5'
 # The full version, including alpha/beta/rc tags
-release = '2.4.0'
+release = '2.5.0'
 
 
 # -- General configuration ---------------------------------------------------
diff --git a/setup.py b/setup.py
index f241561..96a28fc 100644
--- a/setup.py
+++ b/setup.py
@@ -15,7 +15,7 @@ def read(fname):
 
 setup(
     name='aabbtree',
-    version='2.4.0',
+    version='2.5.0',
     license='MIT',
     description='Pure Python implementation of d-dimensional AABB tree.',
     long_description=read('README.rst'),
diff --git a/tox.ini b/tox.ini
index 6b4d635..819c5a7 100644
--- a/tox.ini
+++ b/tox.ini
@@ -30,7 +30,7 @@ commands =
        python setup.py sdist check --strict --metadata
        python -m doctest README.rst
        check-manifest {toxinidir}
-       flake8 src tests setup.py
+       flake8 aabbtree.py tests setup.py
        isort --verbose --check-only --diff --recursive aabbtree.py tests setup.py
 
 


Test patch:
diff --git a/tests/test_aabb.py b/tests/test_aabb.py
index a4cbe0e..4e484e5 100644
--- a/tests/test_aabb.py
+++ b/tests/test_aabb.py
@@ -106,3 +106,21 @@ def test_overlaps():
     assert aabb2.overlaps(aabb1)
     assert not aabb3.overlaps(aabb2)
     assert not aabb2.overlaps(aabb3)
+
+
+def test_corners():
+    lims = [(0, 10), (5, 10)]
+    aabb_corners = [
+        [lims[0][0], lims[1][0]],
+        [lims[0][1], lims[1][0]],
+        [lims[0][0], lims[1][1]],
+        [lims[0][1], lims[1][1]]
+    ]
+
+    out_corners = AABB(lims).corners
+    for c in aabb_corners:
+        assert c in out_corners
+
+    for c in out_corners:
+        assert c in aabb_corners
+
diff --git a/tests/test_aabbtree.py b/tests/test_aabbtree.py
index 6c701cd..d740db7 100644
--- a/tests/test_aabbtree.py
+++ b/tests/test_aabbtree.py
@@ -116,7 +116,8 @@ def test_does_overlap():
     aabb7 = AABB([(6.5, 6.5), (5.5, 5.5)])
 
     for aabb in (aabb5, aabb6, aabb7):
-        assert not AABBTree().does_overlap(aabb)
+        for m in ('DFS', 'BFS'):
+            assert not AABBTree().does_overlap(aabb, method=m)
 
     aabbs = standard_aabbs()
     for indices in itertools.permutations(range(4)):
@@ -124,9 +125,36 @@ def test_does_overlap():
         for i in indices:
             tree.add(aabbs[i])
 
-        assert tree.does_overlap(aabb5)
-        assert not tree.does_overlap(aabb6)
-        assert not tree.does_overlap(aabb7)
+        for m in ('DFS', 'BFS'):
+            assert tree.does_overlap(aabb5, method=m)
+            assert not tree.does_overlap(aabb6, method=m)
+            assert not tree.does_overlap(aabb7, method=m)
+
+
+def test_overlap_aabbs():
+    aabbs = standard_aabbs()
+    values = ['value 1', 3.14, None, None]
+
+    aabb5 = AABB([(-3, 3.1), (-3, 3)])
+    aabb6 = AABB([(0, 1), (5, 6)])
+    aabb7 = AABB([(6.5, 6.5), (5.5, 5.5)])
+
+    for indices in itertools.permutations(range(4)):
+        tree = AABBTree()
+        for i in indices:
+            tree.add(aabbs[i], values[i])
+
+        for m in ('DFS', 'BFS'):
+            aabbs5 = tree.overlap_aabbs(aabb5, method=m)
+            assert len(aabbs5) == 2
+            for aabb in aabbs5:
+                assert aabb in aabbs[:2]
+
+            assert tree.overlap_aabbs(aabb6) == []
+            assert tree.overlap_aabbs(aabb7) == []
+
+    for m in ('DFS', 'BFS'):
+        assert AABBTree(aabb5).overlap_aabbs(aabb7, method=m) == []
 
 
 def test_overlap_values():
@@ -142,15 +170,17 @@ def test_overlap_values():
         for i in indices:
             tree.add(aabbs[i], values[i])
 
-        vals5 = tree.overlap_values(aabb5)
-        assert len(vals5) == 2
-        for val in ('value 1', 3.14):
-            assert val in vals5
+        for m in ('DFS', 'BFS'):
+            vals5 = tree.overlap_values(aabb5, method=m)
+            assert len(vals5) == 2
+            for val in ('value 1', 3.14):
+                assert val in vals5
 
-        assert tree.overlap_values(aabb6) == []
-        assert tree.overlap_values(aabb7) == []
+            assert tree.overlap_values(aabb6) == []
+            assert tree.overlap_values(aabb7) == []
 
-    assert AABBTree(aabb5).overlap_values(aabb7) == []
+    for m in ('DFS', 'BFS'):
+        assert AABBTree(aabb5).overlap_values(aabb7, method=m) == []
 
 
 def standard_aabbs():