Насколько хороша любая из этих библиотек квад-деревьев? - PullRequest
Новая
       17

Насколько хороша любая из этих библиотек квад-деревьев?

15 голосов
/ 19 февраля 2010

Похоже, что мой проект потребует использования квад-деревьев, с чем я никогда раньше не работал. Из того, что я прочитал, они должны позволить существенно повысить производительность, чем попытка грубой силы решить эту проблему. Любой из этих модулей Python хорош?

  • Quadtree 0.1.2 <= <strong>Нет: невозможно выполнить в Python 3.1
  • QuadTree <= <strong>Да: просто при работе с прямоугольниками
  • quadtree.py <= <strong>Нет: нет поддержки для необходимых операций

РЕДАКТИРОВАТЬ 1: Кто-нибудь знает о лучшей реализации, чем та, которая представлена ​​в Pygame Wiki?

РЕДАКТИРОВАТЬ 2: Вот несколько ресурсов, которые другие могут найти полезными для методов поиска пути в Python.

Ответы [ 4 ]

11 голосов
/ 13 ноября 2012

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

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

4 голосов
/ 26 мая 2014

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

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

#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])
1 голос
/ 19 марта 2010

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

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

1 голос
/ 19 февраля 2010

Иногда не ясно, как реализовать структуры данных, такие как деревья, в 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 - это больше, чем просто некоторые данные; это набор правил о том, как вставлять и удалять узлы. Если это не вопрос курсовой работы, то Quadtree 0.1.2 , вероятно, будет хорошей идеей.

...