boost::geometry Наиболее эффективный способ измерения максимального / минимального расстояния точки до многоугольного кольца.

Question

Я использую boost::geometry библиотека в программе, в основном для обработки объектов многоугольника.

Сейчас я пытаюсь оптимизировать мой код для лучшего масштабирования с помощью больших полигонов. Одна из моих функций проверяет для заданного многоугольника и заданной точки (обычно внутри многоугольника) минимальное и максимальное расстояние между точкой и внешним кольцом многоугольника.

Я делаю это путем зацикливания на краях многоугольника:

polygon pol;
point myPoint;
double min = 9999999, max = 0;
for(auto it1 = boost::begin(bg::exterior_ring(pol)); it1 != boost::end(bg::exterior_ring(pol)); ++it1){
    double distance = bg::distance(*it1, myPoint);
        if(max < distance)
            max = distance;
        if(min > distance)
            min = distance;
    }

Я надеюсь, что есть алгоритмы, более быстрые, чем этот, линейные по числу многоугольников ребер. Есть ли такая вещь уже внутри boost::geometry библиотека?

Answer 1

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

Жить на Колиру

#include <boost/geometry.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/algorithms/distance.hpp>

namespace bg = boost::geometry;

using point = bg::model::d2::point_xy<double>;
using polygon = bg::model::polygon<point>;

int main() {
    polygon pol;
    boost::geometry::read_wkt(
            "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
            "(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))", pol);

    point myPoint(7, 7);
    double min = 9999999, max = 0;

    std::cout << "Minimal distance: " << bg::distance(pol, myPoint);

}

Печать

Minimal distance: 4.71699

Дальнейшие подсказки:

Вы должны рассмотреть ранжирование расстояний, используя comparable_distance , Как видно из примера, здесь предлагается циклическое прохождение всех выбранных расстояний... поэтому я не думаю, что в настоящее время у библиотеки есть лучшее предложение.

Планируются более сложные алгоритмы, число которых может быть связано с этой проблемой:

• http://boost-geometry.203548.n3.nabble.com/distance-between-geometries-td4025549.html
• ветка списка рассылки http://lists.boost.org/geometry/2013/08/2446.php
• еще один здесь http://lists.boost.org/geometry/2013/09/2494.php

Также обратите внимание, что у Boost Geometry Index есть связанный предикат comparable_distance_far но это еще не выставлено.

Резюме

Вы можете хотя бы немного улучшить, используя здесь сравнимое расстояние.

Функции были запланированы, и похоже, что есть шанс, что запрос их в списке рассылки /Boost Trac поможет получить их там.

Answer 2

Для лучшей производительности вы должны использовать RTree с boost::geometry::index. Создание RTree имеет свою стоимость, но тогда вычисление ditance точки к любому из (много) многоугольных колец будет намного быстрее. Пример кода:

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

int main()
{
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<double, 2, bg::cs::cartesian> point;
    typedef bg::model::polygon<point> polygon;

    point p{ 0, 0 };
    // create some polygon and fill it with data
    polygon poly;
    double a = 0;
    double as = bg::math::two_pi<double>() / 100;
    for (int i = 0; i < 100; ++i, a += as)
    {
        double c = cos(a);
        double s = sin(a);
        poly.outer().push_back(point{10 * c, 10 * s});
        poly.inners().resize(1);
        poly.inners()[0].push_back(point{5 * c, 5 * s});
    }
    // make sure it is valid
    bg::correct(poly);

    // create rtree containing objects of type bg::model::pointing_segment
    typedef bg::segment_iterator<polygon const> segment_iterator;
    typedef std::iterator_traits<segment_iterator>::value_type segment_type;

    bgi::rtree<segment_type, bgi::rstar<4> > rtree(bg::segments_begin(poly),
                                                   bg::segments_end(poly));

    // get 1 nearest segment
    std::vector<segment_type> result;
    rtree.query(bgi::nearest(p, 1), std::back_inserter(result));

    BOOST_ASSERT(!result.empty());

    std::cout << bg::wkt(result[0]) << ", " << bg::distance(p, result[0]) << std::endl;

    return 0;
}