Хороша ли какая-нибудь из этих библиотек quad-tree?

В этот комментарий, joferkington относится к текущему вопросу и говорит:

Как бы то ни было, scipy.spatial.KDTree (и/или scipy.spatial.cKDTree, написанный на C из соображений производительности) — гораздо более надежный выбор, чем перечисленные варианты.

Еще одна библиотека, которую стоит проверить, это PyQuadTree, чистый индекс дерева квадрантов Python, который также работает на Python 3x. Все, что вам нужно, чтобы добавить элемент, — это его ограничивающая рамка в виде последовательности из 4 длин, поэтому ее можно использовать для различных целей и даже в отрицательных системах координат.

Хотя я и являюсь автором, я просто взял чужую структуру/код дерева квадрантов и сделал его более удобным для пользователя, добавил поддержку прямоугольных квадроциклов и добавил документацию. Простой пример того, как его использовать:

#SETUP
import pyqtree
spindex = pyqtree.Index(bbox=[0,0,1000,500])

#ADD SOME ITEMS
for item in items:
    spindex.insert(item=item, bbox=item.bbox)

#RETRIEVE ITEMS FROM A REGION
result = spindex.intersect(bbox=[233,121,356,242])

Индекс пакета python создает 2 другие библиотеки при поиске quadtree: http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search

отказ от ответственности: никогда не использовал quadtrees или любую из этих библиотек.

Иногда не очевидно, как реализовать такие структуры данных, как деревья, в Python.

Например,

      D 
    /   \
   B     F
  / \   / \
 A   C E   G

представляет собой простую структуру бинарного дерева. В Python вы бы представили это так:

[D,B,F] — это узел с левым и правым поддеревьями. Чтобы представить полное дерево, у вас будет:

[D,[[B,A,C],[F,E,G]]] 

Это простой список вложенных списков, где любой узел может быть значением, например D или C, и любой узел может быть поддеревом, которое рекурсивно представляет собой список вложенных списков. Вы можете сделать что-то подобное со словарем словарей. Эти типы реализации немного быстрые и грязные и могут быть неприемлемы в задании, где инструктор ожидает класс Node с указателями на другие узлы, но в реальном мире, как правило, лучше использовать оптимизированные реализации списков/словарей Python. первый. Только если результат каким-то образом неадекватен, перепишите его так, чтобы он был больше похож на то, что вы написали бы на C или Java.

Помимо этого, конечно, вам нужно реализовать различные алгоритмы для управления вашими деревьями, потому что дерево квадрантов — это больше, чем просто некоторые данные; это набор правил о том, как вставлять и удалять узлы. Если это не вопрос курсовой работы, то Quadtree 0.1.2, вероятно, будет хорошая идея.