One way to solve the problem with trees
A simplified look at binary trees
the rectangles are static
[the rectangles] should never overlap
As such we can build a simple tree.
Before looking at 2d points we can look at a solution for 1d points.
Say we have the following line segments. Beginnings are inclusive ends are not.
- A: 0 - 2
- B: 2 - 3
- C: 3 - 4
- D: 4 - 8
We could describe the values as a really simple binary tree.
With the example I gave we can reduce the amount of leaf nodes to just 4.
We do need to assign multiple leaves to the same node at times.
For example if we had the following line segments:
An algorithm for the above
As such we can just use a simple binary tree.
With two major changes:
- We need to make the intermediary nodes when building the leaves.
- We may need to add multiple leaf nodes to account for the end of the rect.
As such we can build a simple algorithm:
When building the nodes we need to know the index of the node.
Each node has a range for the values the children can be.
In our above 8 leaf node tree, the the values for node 4 can range from 0-8.
Where the 2 node's range is 0-4 and the 5 node's range is 4-6.
If the range of the line segment is greater than the range of the node we can stop recursing.
Otherwise we need to recursively append to the left or right child node. (Can be both.)
- If the start of the line segment's range is less than the node's index we recurse left.
- If the end of the line segment's range is greater than the node's index we recurse right.
Before recursing:
Build the child node if one doesn't exist.
The index will be:
Left: (node's index + node's start) // 2
Right: (node's index + node's end) // 2
We also need to adjust one of the start or end of the child node's range.
Left: The end of the child node's range is the current node's index.
Right: The start of the child node's range is the current node's index.
We then recurse into the children.
Here is an example implementation of such a binary tree in Python:
from __future__ import annotations
import dataclasses
import textwrap
from typing import Iterator, Optional, TypeVar, Generic
T = TypeVar("T")
@dataclasses.dataclass
class Node(Generic[T]):
index: int
left: Optional[Node[T]] = None
right: Optional[Node[T]] = None
value: Optional[T] = None
def get_point(self, point: int) -> Optional[T]:
if self.value is not None:
return self.value
child = self.left if point < self.index else self.right
return child.get_point(point)
def add_range(
self,
value: T,
range_start: int,
range_end: int,
node_start: int,
node_end: int,
) -> None:
if range_start <= node_start and node_end <= range_end:
self.value = value
return
if range_start < self.index:
if self.left is None:
self.left = Node((self.index + node_start) // 2)
self.left.add_range(value, range_start, range_end, node_start, self.index)
if self.index < range_end:
if self.right is None:
self.right = Node((self.index + node_end) // 2)
self.right.add_range(value, range_start, range_end, self.index, node_end)
# So I can show the code works
def tree_format(self, join="──", top=" ", bottom=" ") -> Iterator[str]:
if self.left is not None:
for value in self.left.tree_format("┌─", bottom="│ "):
yield top + value
if self.value is None:
yield f"{join}{self.index}"
else:
yield f"{join}{self.value}"
if self.right is not None:
for value in self.right.tree_format("└─", top="│ "):
yield bottom + value
class Tree(Generic[T]):
_size: int
_root: Node
def __init__(self, size: int) -> None:
self._size = size
self._root = Node(size // 2)
def __str__(self) -> None:
return "\n".join(self._root.tree_format())
def add_range(self, value: T, start: int, stop: int):
self._root.add_range(value, start, stop, 0, self._size)
def get_point(self, point: int) -> Optional[T]:
try:
return self._root.get_point(point)
except AttributeError:
return None
if __name__ == "__main__":
print("Tree1:")
tree_1 = Tree(8)
tree_1.add_range("A", 0, 2)
tree_1.add_range("B", 2, 3)
tree_1.add_range("C", 3, 4)
tree_1.add_range("D", 4, 8)
print(tree_1)
print(3, "==", tree_1.get_point(3))
print("\nTree2:")
tree_2 = Tree(8)
tree_2.add_range("A", 0, 3)
tree_2.add_range("B", 3, 8)
print(tree_2)
print(3, "==", tree_2.get_point(3))
print("\nTree3:")
tree_3 = Tree(8)
tree_3.add_range("A", 0, 3)
tree_3.add_range("B", 4, 8)
print(tree_3)
print(3, "==", tree_3.get_point(3))
Tree1:
┌─A
┌─2
│ │ ┌─B
│ └─3
│ └─C
──4
└─D
3 == C
Tree2:
┌─A
┌─2
│ │ ┌─A
│ └─3
│ └─B
──4
└─B
3 == B
Tree3:
┌─A
┌─2
│ │ ┌─A
│ └─3
──4
└─B
3 == None
We can abstract the binary tree (1D) to a quad tree (2D) and perform the same algorithm.
The quad tree will have a top-left, top-right, bottom-left and bottom-right but otherwise would work the same way.
Problems
The above solution isn't just rainbows and sunshine
The tree's size must never change.
If the tree ever needs to resize you must build one from scratch again.
Currently the tree cannot have overlapping boxes.
Adding the capability doesn't seem impossible however.
- You would need to change
Node.value to a list and append to the list in Node.add_range.
- Adjust
Node.get_point to not eagerly exit and return the children's values (if applicable) along with the current node's values.
Your tree can have lots of cruft leaf nodes because of bad index selection.
(node_end + self.index) // 2
Say you want to put 9 equally sized squares into a 3x3 grid, you won't have a nice 9 leaf nodes.
You'd have 36 leaf nodes.
We see a less severe version of the problem in "Tree2".
Had we selected 3 to be the first index to split on, rather than 4, we'd only have 2 nodes not 4.
┌─A
──3
└─B
To solve the issue I'd move the index generation code out into a separate binary or quad tree.
For example we could abstract the index generation as:
class IndexNode:
def __init__(self, index, start, end):
self.index = index
self.start = start
self.end = end
def left(self):
start, end = self.start, self.index
return Node((start + end) // 2, start, end)
def right(self):
start, end = self.index, self.end
return Node((start + end) // 2, start, end)
We can now easily change the index generation for the 3x3 grid without having to mangle the other tree.
We could also manually define the tree.
But you'd have to manually build the entire tree.
Or have a hybrid where you define the top nodes and let the class generate the rest.
Maintainability
I'm aiming for maintainability over performance
As you can probably see using a tree can get you better performance.
Since the tree could find the rects in \$O(\log(n))\$ time.
To improve the performance and to get good memory usage may require more thought; depending on the intricate patterns you use.
However do you really get much from building an intricate quad-tree?
Even my simple binary tree is double your line count.
If you have come on CR without caring about speed then I can't imagine your current solution is performing poorly.
As such the cost to maintainability doesn't really seem worth the gain in speed at the moment.
