interval_map升壓庫

Question

響應於問題：Previous Answer: rectangle overlap

我使用的interval_map如下： 我有一組由R = [int start, int end, (int Top, int bottom,string id)] NB定義矩形的：矩形被投射到x軸==>線段

• 我想這些線段在inverval_map結構
• 存儲查詢線段我想找到所有的線segme與之重疊NTS

---

的源代碼：

#include "boost/icl/interval.hpp" 
#include "boost/icl/interval_map.hpp" 
#include <set> 
using namespace std; 

struct Position{ 
    int top; 
    int bottom; 
    string id; 
}; 

int main(int argc, char* argv[]) 
{ 
    std::set<Position> ids1; 
    ids1.insert({10,10,"line1"}); 
    std::set<Position> ids2; 
    ids2.insert({200,10,"line2"}); 
    boost::icl::interval_map<int, std::set<Position>> mymap; 
    auto i1 = boost::icl::interval<int>::closed(2, 7); 
    auto i2 = boost::icl::interval<int>::closed(3, 8); 
    mymap += make_pair(i1, ids1); 
    mymap += make_pair(i2, ids2); 

    return 0; 
} 

---

另一個庫，以及一個解決方案，但由於不使用ICL Boost庫

我發現下面的庫它與icl boost庫一樣工作，但必須更簡單： 下載站點：Interval Tree

#include <iostream> 
#include <fstream> 
#include "IntervalTree.h" 

using namespace std; 

struct Position 
{ 
    int x; 
    int y; 
    string id; 
}; 

int main() 
{ 
    vector<Interval<Position>> intervals; 
    intervals.push_back(Interval<Position>(4,10,{1,2,"r1"})); 
    intervals.push_back(Interval<Position>(6,10,{-6,-3,"r2"})); 
    intervals.push_back(Interval<Position>(8,10,{5,6,"r3"})); 

    vector<Interval<Position> > results; 
    vector<string> value; 
    int start = 4; 
    int stop = 10; 

    IntervalTree<Position> tree(intervals); 
    // tree.findContained(start, stop, results); 
    tree.findOverlapping(start, stop, results); 
    cout << "found " << results.size() << " overlapping intervals" << endl; 
} 

---

例

• 開始= 4;
• Stop = 10;
• structure {1,2，「rc1」};

intervals.push_back（Interval（4,1​​0，{1,2，「r1」}））;

Answer 1

我認爲你正在嘗試使用inverval庫來設計一些不太適合的東西。

你看過Boost Geometry的rtree實現嗎？

http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html

query該方法支持數量的空間謂詞：

• covered_by()
• covers()
• disjoint()
• intersects()
• overlaps()
• within()

其中大部分也可以使用negated。額外的標準被支持。由於可以使用特殊標準boost::geometry::index::nearest()，其導致k最近算法搜索。