Повышение геометрии rtree находит итератор для точного совпадения поля

При вставке нового ящика в дерево я хочу сначала проверить, нет ли уже идентичного ящика в дереве. Если это так, я хочу просто получить это значение, иначе мне нужно будет вставить новое значение. Каков наилучший (т.е. наиболее эффективный) способ сделать это?

Я могу сделать это, вызвав nearest(box,1), а затем проверив равенство:

#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 bgi = boost::geometry::index;

typedef bg::model::point<double, 1, bg::cs::cartesian> TPoint;
typedef bg::model::box<TPoint> TBox;
typedef std::pair<TBox, void*> TPair;
typedef bgi::rtree<TPair, bgi::quadratic<16>> TTree;

TTree::const_query_iterator findExact(const TTree& tree, const TBox& box)
{
    auto it = rtree.qbegin(bgi::nearest(box, 1));
    if(it == rtree.qend() || !bg::equals(it->first, box))
        return rtree.qend();
    return it;
}

Действительно ли это лучший (то есть наиболее производительный) способ выполнить этот запрос?


c++ boost boost-geometry
person Robert Fraser    schedule 18.05.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Это не безопасный подход. Я легко могу представить ситуацию, которая может не сработать:

Состояние Rtree с двумя ящиками перед вставкой нового:

(0,2) --- (1,2)
  |    b    |
(0,1) --- (1,1)
  |    a    |
(0,0) --- (1,0)

поэтому у нас есть 2 коробки a и b. Теперь вы вызываете предикат nearest с 1 в качестве количества результатов, когда пытаетесь вставить новое поле ввода с той же геометрией, что и поле a. distance между входной геометрией и a равен 0, но 0 также соответствует distance(input,b). nearest может возвращать только одну коробку - какую? вы не знаете, если он возвращает поле b, вы вставляете дубликат a в Rtree.

Безопасный метод может быть следующим:

  1. получить новое поле ввода
  2. вычислить его центр тяжести
  3. получить ВСЕ поля из rtree, которые содержат входной центроид
  4. перебрать возвращенные поля и вызвать функцию equals для пары (поле из rtee, поле ввода)

Для этого вы можете использовать содержит предикат, который использует метод boost::geometry::within. В качестве ввода contains/within вы передаете точку - центроид, если он отбрасывается компилятором (я не уверен, что он может принимать точку), вы можете расширить точку-центроид в маленькое поле для компиляции.

person rafix07    schedule 19.05.2019
comment
Ах; Я не знал, что ближайший работает таким образом с коробками, но я думаю, что это имеет смысл. - person Robert Fraser; 21.05.2019