В поисках эффективной структуры данных для хранения и извлечения томов прямоугольников. Я дам несколько графических диаграмм, чтобы лучше объяснить мою проблему.
Давайте просто предположим, что у нас есть простой двумерный случай, когда у нас есть выровненные по оси прямоугольники. Теперь, если я хочу разделить прямоугольники влево и вправо (как на диаграмме ниже), тогда мой левый объем будет частью прямоугольников, которые падают слева от вертикальной линии, а правый объем будет частью прямоугольников, которые падают справа от вертикальной линии. Вертикальная линия может делить пополам один или несколько прямоугольников. Мы должны рассчитать объемы пополам прямоугольников и посмотреть, где они падают (слева или справа). Аналогично, мы можем иметь горизонтальные линии или несколько вертикальных и горизонтальных линий вместе (как показано ниже). введите описание изображения здесь 
Моя цель - построить эффективную древовидную структуру данных, которая может хранить эту информацию, а также может выполнять эффективный поиск. Как и в случае 2d, когда я задаю диапазон (x_min, x_max) и (y_min, y_max), дерево должно возвращать объем прямоугольников, попадающих в этот диапазон. Это должно хорошо работать и для больших размеров.
Что я сделал
Я подумал о 2 различных древовидных структурах данных. кД дерево, р-дерево. Проблема с деревом KD состоит в том, что он произвольно режет ось, и мне нужно хранить информацию для каждой оси. R-Tree не учитывает пополам часть прямоугольников. Я слышал о Range Range, но я не уверен, как оно работает, а также не нашел хорошей реализации в python. Существует ли какая-либо древовидная структура данных, реализованная в python, которую я могу использовать для решения своей задачи.
Спасибо за помощь.