4

私はボロノイ テッセレーション アルゴリズム (フォーチュンのアルゴリズム; それ自体が非常に重要なタスクだと思います) のバイナリ検索ツリーを探しているので、もちろん、Boost を調べてみようと思いました。

Boost にはIntrusiveヘッダー ファイルがあり、そこには豊富な BST (AVL、Splay ツリー、Scapegoat ツリーなど) が含まれているようで、一見しただけで必要なもののように見えました。 .

1:何か足りないのでしょうか、それともツリーのルート ノードに直接アクセスする方法がありませんか?

2: AVL ツリーは Fortune アルゴリズムのビーチライン構造に適していますか?

くそー、これは簡単だと思った。

更新:おそらく、私が達成しようとしていることを述べたほうがよいでしょう: Fortune アルゴリズムの一部である放物線検索を実装したいと思います。これは、新しいサイトが検出され、放物線を真上で見つける必要がある部分です。正しい円弧を見つけるために、ルートからツリーをたどろうと思いました。

4

4 に答える 4

1

最後に、独自の AVL ツリーを実装しました。ボロノイ アルゴリズムの複雑さはそれを要求しているように見え、とにかく、Boost バージョンはノードにアクセスできませんでした (私が間違っている場合は、指摘してください。Boost のあいまいさを考えると、それは可能です)。

AVL ツリーは完璧に機能しているようです。

于 2013-05-29T08:39:11.237 に答える
0

Boost.Intrusive ツリーのようなコンテナーには、ルート ノードに反復子を返す root() メンバー、またはルート ノードがない場合は end() があります。これらの関数はずっと前にコミットされました。次のコミット:

https://github.com/boostorg/intrusive/commit/6d38384e369697894bb71fb81132ad60b796c70c

それらの機能を文書化したので、それらは現在公式です。次のコードは、その使用方法を示しています。

#include <boost/intrusive/set.hpp>
#include <cassert>

using namespace boost::intrusive;

struct MyClass : public set_base_hook<>
{
   friend bool operator<(const MyClass&, const MyClass&)
   {  return true;   }
};

int main()
{
   set<MyClass> set;
   //end() is returned when the tree is empty
   assert(set.root()  == set.end() );

   //insert myobject, must be root
   MyClass myobject;
   set.insert(myobject);
   assert(&*set.root() == &myobject);

   //erase and check root is again end()
   set.erase(set.root());
   assert(set.croot() == set.cend());

   return 0;   
}
于 2016-09-03T11:51:17.853 に答える