Повысьте геометрию дерева поиска итератора для точного соответствия окна - PullRequest
Новая
       32

Повысьте геометрию дерева поиска итератора для точного соответствия окна

1 голос
/ 19 мая 2019

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

Я могу сделать это, позвонив 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;
}

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

1 Ответ

2 голосов
/ 19 мая 2019

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

State of Rtree с 2 полями перед вставкой новой: 

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

, поэтому у нас есть 2 коробки a и b. Теперь вы вызываете nearest prediacte с 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 вы передаете point-centroid, если он отбрасывается компилятором (я не уверен, что он может взять точку), вы можете расширить point-centroid в маленькое поле для компиляции.

...