18

私の特定のプロジェクトでは、これまで使用したことのない四分木を使用する必要があるようです。私が読んだことから、問題に対するブルートフォース攻撃がもたらすよりも大幅なパフォーマンスの向上が可能になるはずです。これらのPythonモジュールのいずれかが良いですか？

  • Quadtree 0.1.2 <=いいえ： Python3.1で実行できません
  • QuadTree <=はい：長方形での作業中は簡単
  • quadtree.py <=いいえ：必要な操作はサポートされていません

編集1： pygame wikiで提示されているものよりも優れた実装を知っている人はいますか？

編集2： Pythonでのパスファインディング手法に他の人が役立つと思われるリソースをいくつか示します。

4

4 に答える 4

17

このコメントでは、joferkingtonは現在の質問を参照し、次のように述べています。

価値があるものは何でもscipy.spatial.KDTree（および/またはパフォーマンス上の理由からCで記述されているscipy.spatial.cKDTree）は、リストされているオプションよりもはるかに堅牢な選択肢です。

于 2012-11-13T14:08:25.213 に答える
6

チェックアウトする別のライブラリはPyQuadTreeです。これは、Python 3x でも動作する純粋な Python 四分木インデックスです。アイテムを追加するために必要なのは、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])
于 2014-05-25T20:37:55.340 に答える
1

pythonパッケージインデックスは、quadtreeを検索するときに他の2つのライブラリを生成します：http：//pypi.python.org/pypi ？％3Aaction = search＆term = quadtree＆submit = search

免責事項：クワッドツリーまたはこれらのライブラリを使用したことはありません。

于 2010-03-19T09:18:53.000 に答える
1

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を使用することをお勧めします。

于 2010-02-19T20:54:44.443 に答える