Найти элементы Boost rtree внутри многоугольника - PullRequest
Новая
       29

Найти элементы Boost rtree внутри многоугольника

0 голосов
/ 26 мая 2018

Я хотел бы найти все элементы, проиндексированные в дереве, которое пересекается с внешним кольцом многоугольника с отверстиями, но которые не полностью находятся внутри какого-либо отверстия, используя библиотеки Boost C ++.

Я знаю, какчтобы получить элемент, пересекающий внешнее кольцо с помощью: 

// Constructing the exterior ring polygon
Boost2dRing p;
for (int i = 0; i < numPunts; i++)
{
    x = Punts.at(i).x;
    y = Punts.at(i).y;
    p.push_back(Boost2dPoint(x, y));
}

// Getting the intersecting elements with that polygon
m_RTree.query(bgi::intersects(p), std::back_inserter(res));
...
// Constructing the polygon for the inner ring (hole)
Boost2dRing p;
for (int i = 0; i < numPuntsHole; i++)
{
    x = PuntsHole.at(i).x;
    y = PuntsHole.at(i).y;
    pHole.push_back(Boost2dPoint(x, y));
}

// Now I try to get the elements inside completely this polygon but I get a compilation error
m_RTree.query(bgi::within(pHole), std::back_inserter(res));

Сообщение об ошибке:

ошибка C2664: 'int boost :: mpl :: assertion_failed (boost :: mpl ::assert :: type) ': невозможно преобразовать аргумент 1 из' boost :: mpl :: fail ************ (__ cdecl boost :: geometry :: стратегии :: inside :: services :: default_strategy:: NOT_IMPLEMENTED_FOR_THESE_TYPES :: * ***********) (boost :: mpl :: assert _ :: types) 'to' boost :: mpl :: assert :: type '1> с 1> [1> Geometry1 = Boost2dBox, 1> Geometry2 = Boost2dRing, 1>
GeometryContained = Boost2dBox, 1>
GeometryContained = Boost2dRing 1>] примечание: ни один конструктор не может принять тип источника, или разрешение перегрузки конструктора было неоднозначным

Есть ли подсказка для достижения этой цели?

1 Ответ

0 голосов
/ 26 мая 2018

Предикат внутри не реализован для выбранных вами операндов геометрии.

Однако вы можете делать то, что хотите, с намного меньшим количеством работы.Допустим, у вас есть ваши кольца, например: 

Boost2dRing exterior, interior;
bg::read_wkt("POLYGON((0.1 0.1,0.1 0.5,0.5 0.5,0.5 0.1,0.1 0.1))", exterior);
bg::read_wkt("POLYGON((0.2 0.2,0.2 0.4,0.4 0.4,0.4 0.2,0.2 0.2))", interior);

Теперь, у Boost Geometry есть концепция Polygon , которая является внешним кольцом и (несколькими) внутренними кольцами:

Многоугольник - это многоугольник - это плоская поверхность, определяемая одной внешней границей и нулем или несколькими внутренними границами ( Спецификация простого объекта OGC )

Итак, давайте использовать это вместо: 

bg::reverse(interior);
Boost2dPolygon polygon;
polygon.outer() = exterior;
polygon.inners().push_back(interior);

Обратите внимание, что ориентация внутреннего кольца инвертирована.

Или, действительно, непосредственно с помощью конструктора: 

Boost2dPolygon polygon({exterior, interior});

Или, даже читая его из WKT сразу: 

bg::read_wkt("POLYGON((0.1 0.1,0.1 0.5,0.5 0.5,0.5 0.1,0.1 0.1) (0.2 0.2,0.4 0.2,0.4 0.4,0.2 0.4,0.2 0.2))", polygon);

Теперь вы можете просто запросить за один проход: 

std::vector<RTree::value_type> res;
m_RTree.query(bgi::intersects(polygon), std::back_inserter(res));

Полная демонстрация!

С учетом следующего sample() содержимого дерева: 

using RTree = bgi::rtree<std::pair<Boost2dBox, std::string>, bgi::rstar<16> >;
RTree sample() {
    RTree tree;

    std::pair<std::string, std::string> items[] = {
        { "BOX(0.2 0.2,0.2 0.4,0.4 0.4,0.4 0.2,0.2 0.2)",           "ok" },
        { "BOX(0.28 0.28,0.28 0.32,0.32 0.32,0.32 0.28,0.28 0.28)", "within gap" },
        { "BOX(0.28 0.28,0.28 0.32,0.36 0.32,0.36 0.28,0.28 0.28)", "small overlap" },
        { "BOX(2 2,2 4,4 4,4 2,2 2)",                               "outside exterior" },
    };
    for (auto& item : items) {
        Boost2dBox box;
        bg::read_wkt(item.first, box);
        checks("box", box);
        tree.insert({box, item.second});
    }

    return tree;
}

Мы можем проверить вещи вручную: 

RTree const m_RTree = sample();

std::cout << "Sample tree:\n";
for (auto& value : m_RTree) {
    std::cout << " - " << std::quoted(value.second) << ": " << bg::wkt(value.first) << "\n";

    Boost2dMultiPolygon mp;
    if (bg::intersection(polygon, value.first, mp))
        std::cout << "      (intersection is " << bg::wkt(mp) << ")\n";
}

Какие отпечатки 

Sample tree:
 - "ok": POLYGON((0.2 0.2,0.2 0.4,0.4 0.4,0.4 0.2,0.2 0.2))
      (intersection is MULTIPOLYGON(((0.2 0.2,0.2 0.4,0.4 0.4,0.4 0.2,0.2 0.2),(0.25 0.25,0.35 0.25,0.35 0.35,0.25 0.35,0.25 0.25))))
 - "within gap": POLYGON((0.28 0.28,0.28 0.32,0.32 0.32,0.32 0.28,0.28 0.28))
      (intersection is MULTIPOLYGON())
 - "small overlap": POLYGON((0.28 0.28,0.28 0.32,0.36 0.32,0.36 0.28,0.28 0.28))
      (intersection is MULTIPOLYGON(((0.35 0.32,0.36 0.32,0.36 0.28,0.35 0.28,0.35 0.32))))
 - "outside exterior": POLYGON((2 2,2 4,4 4,4 2,2 2))
      (intersection is MULTIPOLYGON())

И проверьте результаты, сравнивая с запросом дерева: 

m_RTree.query(bgi::intersects(polygon), std::back_inserter(matches));

std::cout << "Intersecting with: ";
for (auto& match : matches) std::cout << " " << std::quoted(match.second) << " ";

Который печатает: 

Intersecting with:  "ok"  "small overlap"

Просмотреть все Live On Coliru 

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/multi_polygon.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/geometry/geometries/multi_polygon.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/arithmetic/arithmetic.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/intersects.hpp>
#include <boost/geometry/algorithms/envelope.hpp>
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/index/predicates.hpp>
#include <boost/geometry/index/adaptors/query.hpp>
#include <boost/geometry/io/io.hpp>
#include <iostream>
#include <fstream>

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

using Boost2dPoint        = bg::model::d2::point_xy<double>;
using Boost2dRing         = bg::model::ring<Boost2dPoint>;
using Boost2dPolygon      = bg::model::polygon<Boost2dPoint>;
using Boost2dMultiPolygon = bg::model::multi_polygon<Boost2dPolygon>;
using Boost2dBox          = bg::model::box<Boost2dPoint>;

template <typename G> void checks(std::string name, G& geom) {
    std::cout << name << ": " << bg::wkt(geom) << "\n";

    std::string reason;
    if (!bg::is_valid(geom, reason)) {
        std::cout << name << ": " << reason << "\n";

        bg::correct(geom);

        std::cout << bg::wkt(geom) << "\n";
        if (!bg::is_valid(geom, reason)) {
            std::cout << name << " corrected: " << reason << "\n";
        }
    }
}

using RTree = bgi::rtree<std::pair<Boost2dBox, std::string>, bgi::rstar<16> >;
RTree sample() {
    RTree tree;

    std::pair<std::string, std::string> items[] = {
        { "BOX(0.2 0.2,0.2 0.4,0.4 0.4,0.4 0.2,0.2 0.2)",           "ok" },
        { "BOX(0.28 0.28,0.28 0.32,0.32 0.32,0.32 0.28,0.28 0.28)", "within gap" },
        { "BOX(0.28 0.28,0.28 0.32,0.36 0.32,0.36 0.28,0.28 0.28)", "small overlap" },
        { "BOX(2 2,2 4,4 4,4 2,2 2)",                               "outside exterior" },
    };
    for (auto& item : items) {
        Boost2dBox box;
        bg::read_wkt(item.first, box);
        checks("box", box);
        tree.insert({box, item.second});
    }

    return tree;
}

int main() {
    Boost2dPolygon polygon;
    bg::read_wkt("POLYGON((0.1 0.1,0.1 0.5,0.5 0.5,0.5 0.1,0.1 0.1) (0.25 0.25,0.35 0.25,0.35 0.35,0.25 0.35,0.25 0.25))", polygon);
    checks("polygon", polygon);

    RTree const m_RTree = sample();

    std::cout << "Sample tree:\n";
    for (auto& value : m_RTree) {
        std::cout << " - " << std::quoted(value.second) << ": " << bg::wkt(value.first) << "\n";

        Boost2dMultiPolygon mp;
        if (bg::intersection(polygon, value.first, mp))
            std::cout << "      (intersection is " << bg::wkt(mp) << ")\n";
    }
    std::cout << "\n";

    std::vector<RTree::value_type> matches;
    m_RTree.query(bgi::intersects(polygon), std::back_inserter(matches));

    std::cout << "Intersecting with: ";
    for (auto& match : matches) std::cout << " " << std::quoted(match.second) << " ";
    std::cout << "\n";
}
...