split_interval_map用法，高效查找与一个点相交的所有间隔 [英] split_interval_map usage, efficient find all interval intersecting a point

问题描述

#include <iostream>
#include <boost/icl/split_interval_map.hpp>

using namespace std;
using namespace boost::icl;

int main()
{
    split_interval_map<double, int> intervals;

    intervals.add(make_pair(interval<double>::closed(0.,1.),0));
    intervals.add(make_pair(interval<double>::closed(1.,2.),1));
    intervals.add(make_pair(interval<double>::closed(3.,4.),2));
    intervals.add(make_pair(interval<double>::closed(2.,4.),3));
    intervals.add(make_pair(interval<double>::closed(1.5,3.5),4));

    std::vector<double> probes = { 0.23, 1., 1.33 , 1.57, 3.49, 3.51 };

    for(auto probe : probes)
    {
        std::cout << std::endl<< "probe " << probe << std::endl;
        auto lower = intervals.lower_bound(interval<double>::closed(probe, probe));
        auto upper = intervals.upper_bound(interval<double>::closed(probe, probe));
        while(lower != upper)
        {
            std::cout << lower->second << " ";
            ++lower;
        }
    }
}

1. 我得到的是加起来的指数.但是我正在寻找包含探针"的间隔的所有值(int s). (路口?)
2. 我可以使用std::set<int>作为值来实现这一点，但是在文档中指出，这对性能有巨大的影响.好像split_interval_map包含该信息，但我不知道如何检索它.
3. 我只需要一个高效的查找(如本例中所示).我不再需要相交的间隔范围. boost icl太重了吗?

1. What i get are the indices added up. But i'm looking for all the values (ints) of the interval containing 'probe'. (intersection?)
2. I could achieve this with std::set<int> as value, but in the documentation it is stated, that this has a huge impact on performance. Seems like split_interval_map contains that information but i don't know how to retrieve it it.
3. I need only a highly efficient lookup like in this example. I don't need the intersecting interval ranges anymore. Is boost icl too heavy for this?

推荐答案

1. 我得到的是加起来的指数.但是我正在寻找包含探针"的间隔的所有值(整数). (路口?)

您可以使用选择的合并器获得所有的值(共域值)合并的.对于算术类型，这意味着求和.

You get all the values (the co-domain values) combined using the combiner of your choosing. For an arithmetic type, that implies summation.

如果您的共同域是一个索引，那么显然求和对合并器没有意义，您应该选择其他选项.

If your co-domain is an index, clearly summation is not meaningful combiner, and you should choose something else.

我可以使用std::set<int>作为值来实现，但是在文档中指出，这对性能有很大的影响.

I could achieve this with std::set<int> as value, but in the documentation it is stated, that this has a huge impact on performance.

一如既往，正确是表现的先决条件.如果您需要它，那就是您需要的.

As always, correct goes before performance. If it's what you need, it's what you need.

好像split_interval_map包含该信息，但我不知道如何检索它.

Seems like split_interval_map contains that information but i don't know how to retrieve it it.

不具有所选的共同域:如果间隔重叠(并且您使用add，而不是set)，则合并器将丢失原始信息.

Not with the chosen co-domain: the combiner loses the original information if intervals overlap (and you use add, not set).

我只需要一个高效的查找(如本例中所示).我不再需要相交的间隔范围. boost icl太重了吗?

I need only a highly efficient lookup like in this example. I don't need the intersecting interval ranges anymore. Is boost icl too heavy for this?

您可以使用equal_range代替lower_bound/upper_bound:

在Coliru上直播

for (auto probe : { 0.23, 1., 1.33, 1.57, 3.49, 3.51 }) {
    std::cout << "\nprobe " << probe << ": ";

    for (auto& p : boost::make_iterator_range(m.equal_range(Ival::closed(probe, probe)))) {
        std::cout << p.second << " ";
    }
}

打印

probe 0.23: 
probe 1: 1 
probe 1.33: 1 
probe 1.57: 4 
probe 3.49: 4 
probe 3.51: 3 

观察:

m.add({Ival::closed(0., 1.), 0});
m.add({Ival::closed(1., 2.), 1});
m.add({Ival::closed(3., 4.), 2});

这些间隔巧妙地重叠. [0, 1]和[1, 2]共有[1,1].你真的是说left_open吗? ([0, 1)和[1, 2)没有重叠).

These intervals subtly overlap. [0, 1] and [1, 2] have [1,1] in common. Did you really mean left_open? ([0, 1) and [1, 2) have no overlap).

m.add({Ival::closed(2., 4.), 3});
m.add({Ival::closed(1.5, 3.5), 4});

如果您对这样的事实感到惊讶，那就是它合并了重叠区间中已经存在的值，您是要替换它们吗?

If you were surprised by the fact that this combines the values already in the overlapping interval(s), did you mean to replace them?

m.set({Ival::closed(2., 4.), 3});
m.set({Ival::closed(1.5, 3.5), 4});

替代方案，想法:

1. 您可以立即与一组探针进行相交:

1. You could do the intersection with the set of probes at once:

在Coliru上直播

Set probes;
probes.insert(0.23);
probes.insert(1.);
probes.insert(1.33);
probes.insert(1.57);
probes.insert(3.49);
probes.insert(3.51);
std::cout << std::endl << "all: " << (m & probes) << "\n";

打印:

all: {([1,1]->1)([1.33,1.33]->1)([1.57,1.57]->4)([3.49,3.49]->4)([3.51,3.51]->3)}

要(也许?)对其进行一些优化:

To (maybe?) optimize that a little:

在Coliru上直播

using Map  = icl::split_interval_map<double, boost::container::flat_set<int> >;

如果集合将很小，请考虑为该flat_set的序列类型指定small_vector:

If the sets are going to be small, consider specifying small_vector for that flat_set's sequence type:

icl::split_interval_map<double,
    boost::container::flat_set<int, std::less<int>, 
        boost::container::small_vector<int, 4>
    > >;

其他所有方法仍然有效: 在Coliru上直播

All else just still works: Live On Coliru

完全开箱即用:您正在对几何区域建模吗?像时间线上的间隔一样?还是仅在轴上设置线段?在这种情况下，请考虑boost::geometry::index::rtree<>

Completely OUT-OF-THE-BOX: are you modeling geometric regions? Like intervals on a timeline? Or just line-segments on an axis? In that case, consider boost::geometry::index::rtree<>

这篇关于split_interval_map用法，高效查找与一个点相交的所有间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！