8

多くの boost::polgons を結合する必要がありますが、特に多数のポリゴン (>2000) では、私のアプローチはあまりパフォーマンスが良くないようです (>15 分)。

結合したいすべてのポリゴンをマルチポリゴンにプッシュしてから、マルチポリゴンに結合します。コードを参照してください。

BOOST_FOREACH(polygon, multipolygon)
{
  boost::geometry::clear(tmp_union); //tmp_union  is a multipolygon
  boost::geometry::union_(result, poly, tmp_union);
  result = tmp_union;
}

結合するポリゴンのほとんどが交差するため、結果にはおそらく非常に多くのポリゴンが含まれません。

ポリゴンを特定の順序で並べ替えたり、まったく異なる方法で並べ替えたりするなど、これをより効率的にする方法はありますか?

4

3 に答える 3

4

クラス property_merge http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/gtl_property_merge.htmによるユニオンの Boost.Polygon 実装を試すこともできます。

基本的に、自明な整数プロパティを持つ property_merge オブジェクトを作成します。

namespace bgp = boost::polygon;
typedef int property_type;
typedef int coordinate_type;
const property_type FAKE_PROPERTY = 99;

typedef std::map<std::vector<property_type>, bpg::polygon_set_data<coordinate_type> > merge_result;
//in fact, merge_map will have 1 element only

merge_map merger;
for (polygon: my_polygons) 
   merger.insert(polygon, FAKE_PROPERTY);

merge_result mresult;
merger.merge(mresult);

//now use the only element result should have 
assert( mresult.size()<=1);
if (mresult.empty())
{
   //use empty bpg::polygon_set_data()
}
else
{
   //use 
   const bpg::polygon_set_data & result = mresult.begin()->second;
   ...
}
于 2014-04-19T02:01:01.570 に答える
0

ポリゴンがどのように見えるかを確認せずに、根拠のあるアドバイスをすることは困難です。

ローカリティを改善し、干渉しそうなポリゴンをボトムアップでマージする必要があることを直感的に教えてくれました。

このために、ポリゴンの中心の横座標の中央値を見つけ、中央値の両側でそれらを分割します。半分ごとに、縦座標で繰り返します。などを再帰的に。これは、中心の kD ツリー ( http://en.wikipedia.org/wiki/Kd_tree )を構築するのと同じです。

2 つのポリゴンになったら、それらをマージします。次に、再帰ツリーを上って、ポリゴンをペアでマージします。

于 2014-04-17T15:28:34.693 に答える