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最近算法搜索。