c++ - 从 boost::geometry::index::rtree 中删除点的问题

Question

我在 OS X 上使用 boost 1.56，通过自制软件安装。

我遇到了一个编译问题——具体来说，我似乎无法从 boost::geometry::index::rtree 中删除值。

这是我到目前为止想出的代码:

#include <iostream>
#include <vector>
#include <string>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgm = bg::model;
namespace bgi = bg::index;

typedef bgm::point<float, 2, bg::cs::spherical_equatorial<bg::degree> > Point;
typedef bgm::box<Point> Box;
typedef std::pair<Box, int> BoxIdPair;

int main(int argc, char** argv) {
  bgi::rtree<BoxIdPair, bgi::rstar<16>> tree;
  // Some tree filling code excised from here for the sake of a minimal example.
  BoxIdPair b1 = std::make_pair(Box(Point(24, 19), Point(35, 26)), 100);
  BoxIdPair b2 = std::make_pair(Box(Point(41, 112), Point(54, 148)), 150);
  BoxIdPair b3 = std::make_pair(Box(Point(34, 24), Point(36, 100)), 92);
  BoxIdPair b4 = std::make_pair(Box(Point(21, 8), Point(43, 15)), 8);
  tree.insert(b1);
  tree.insert(b2);
  tree.insert(b3);
  tree.insert(b4);
  while (!tree.empty()) {
    std::cout << "Tree contains " << tree.size() << "box-id values." << std::endl;
    // 1. Choose arbitrary BoxIdPair to be the leader of a new canopy.
    //    Remove it from the tree. Insert it into the canopy map, with its corresponding id.
    Point origin(0.0, 0.0);
    std::vector<BoxIdPair> result_set;
    tree.query(bgi::nearest(origin, 1), std::back_inserter(result_set));
    Box b = result_set[0].first;
    int id = result_set[0].second;
    tree.remove(result_set[0]); // This is the line that is giving me difficulty, I think.

    // Additional code cut for minimal example
  }
}

这段代码无法编译!具体来说，这是调用:

clang++ -g -std=c++11 -L/usr/local/Cellar/boost/1.56.0/lib -I/usr/local/Cellar/boost/1.56.0/include 测试。 cc -o 测试

下面是编译器发出的错误(为简洁起见链接到 pastebin): http://pastebin.com/d7E0A4Ee

三个相关错误是:

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
      boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>, boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/geometry/strategies/concepts/within_concept.hpp:183:21: note: candidate template ignored: couldn't infer template argument 'ApplyMethod'
    static void apply(ApplyMethod const&)

^

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>, boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/mpl/assert.hpp:83:5: note: candidate function [with C = false] not viable: no known conversion from 'boost::mpl::failed
  ************(boost::geometry::nyi::not_implemented_error<boost::geometry::info::BOX, boost::geometry::info::BOX, void>::THIS_OPERATION_IS_NOT_OR_NOT_YET_IMPLEMENTED::************)(types<boost::geometry::info::BOX,
  boost::geometry::info::BOX, void>)' to 'typename assert<false>::type' (aka 'mpl_::assert<false>') for 1st argument
int assertion_failed( typename assert<C>::type );

^

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>,   boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
  boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
  std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/geometry/algorithms/detail/relate/relate.hpp:282:1: note: candidate template ignored: substitution failure [with MatrixOrMask =
  boost::mpl::vector<boost::geometry::detail::relate::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'>, boost::geometry::detail::relate::static_mask<'*', 'T', 'F', '*', '*', 'F', '*', '*', '*'>,
  boost::geometry::detail::relate::static_mask<'*', '*', 'F', 'T', '*', 'F', '*', '*', '*'>, boost::geometry::detail::relate::static_mask<'*', '*', 'F', '*', 'T', 'F', '*', '*', '*'>, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
  mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, Geometry1 = boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, Geometry2 = boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> >
  >]
relate(Geometry1 const& geometry1,
^

有人想过可能出了什么问题吗？我很困惑。

Answer 1

我已经查看了您的代码，看起来不错。您只是遇到了所选坐标系的限制，您的坐标还没有得到完全支持(还)。

你可以通过改变坐标来验证这一点(这使数据有点滑稽，但它是关于编译成功的)。请参阅此测试程序，它显示了不同的、等效的删除项目的方法:

Live On Coliru

#include <iostream>
#include <vector>
#include <string>
#include <boost/geometry.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/distance_predicates.hpp>
#include <boost/geometry/index/predicates.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg  = boost::geometry;
namespace bgi = bg::index;
namespace bgm = bg::model;

//typedef bgm::point<float, 2, bg::cs::spherical_equatorial<bg::degree> > Point;
typedef bgm::point<float, 2, bg::cs::cartesian> Point;
typedef bgm::box<Point> Box;
typedef std::pair<Box, int> BoxIdPair;

int main() {
    using Tree = bgi::rtree<BoxIdPair, bgi::rstar<16> >;
    Tree tree;

    // Some tree filling code excised from here for the sake of a minimal example.
    tree.insert({ { Point(24,  19), Point(35,  26) }, 100 });
    tree.insert({ { Point(41, 112), Point(54, 148) }, 150 });
    tree.insert({ { Point(34,  24), Point(36, 100) },  92 });
    tree.insert({ { Point(21,   8), Point(43,  15) },   8 });

    while (!tree.empty()) {
        std::cout << "Tree contains " << tree.size() << " box-id values." << std::endl;
        // 1. Choose arbitrary BoxIdPair to be the leader of a new canopy.
        //    Remove it from the tree. Insert it into the canopy map, with its
        //    corresponding id.
        Point origin(0.0, 0.0);

        auto first = bgi::qbegin(tree, bgi::nearest(origin, 1)), 
             last  = bgi::qend(tree);

        if (first != last) {
            tree.remove(*first); // assuming single result
        }
    }
    std::cout << "Tree emptied\n";
}

Note Don't use the iterator-based remove() with iterators into the same rtree because remove() may invalidate them.

Note All of the remove() overloads end up deferring to raw_remove internally.

我不完全确定为什么它不起作用。似乎没有为这个特定的几何组合定义确定索引操作是否 可中断的特征。

更新 感谢 Adam 下面的评论，我们知道这是因为在内部 within() 用于决定在树遍历期间应该检查哪个节点。而 within(box, box) 目前还没有为非笛卡尔坐标系实现。