эффективный способ обработки 2d сегментов линии

Теоретически поиск ближайших сегментов должен быть возможен с использованием любого типа пространственного индекса или структуры данных разделения пространства. Чаще всего интерфейс такого пространственного индекса позволяет хранить блоки (AABB) или точки, поэтому в этих случаях вам придется хранить ограничивающие блоки сегментов, а затем после запроса ближайших блоков снова проверять соответствующие сегменты. Однако можно индексировать сегменты напрямую. Например. в случае kd-дерева это будет версия, содержащая внутренние узлы, определяющие плоскости разделения и листы, хранящие сегменты.

Boost.Geometry R-tree поддерживает сегменты в Boost версии 1.56.0 и выше. Ниже приведен пример для 2D-сегментов с использованием этой реализации пространственного индекса:

// Required headers
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/segment.hpp>
#include <boost/geometry/index/rtree.hpp>

// Convenient namespaces
namespace bg = boost::geometry;
namespace bgm = boost::geometry::model;
namespace bgi = boost::geometry::index;

// Convenient types
typedef bgm::point<double, 2, bg::cs::cartesian> point;
typedef bgm::segment<point> segment;
typedef std::pair<segment, size_t> value;
typedef bgi::rtree<value, bgi::rstar<16> > rtree;

// Function object needed to filter the same segment in query()
// Note that in C++11 you could pass a lambda expression instead
struct different_id
{
    different_id(size_t i) : id(i) {}
    bool operator()(value const& v) const { return v.second != id; }
    size_t id;
};

int main()
{
    // The container for pairs of segments and IDs
    std::vector<value> segments;
    // Fill the container
    for ( size_t i = 0 ; i < 10 ; ++i )
    {
        // Example segment
        segment seg(point(i, i), point(i+1, i+1));
        segments.push_back(std::make_pair(seg, i));
    }

    // Create the rtree
    rtree rt(segments.begin(), segments.end());
    // The number of closest segments
    size_t k = 3;

    // The container for results
    std::vector< std::vector<value> > closest(segments.size());

    for ( size_t i = 0 ; i < segments.size() ; ++i )
    {
        // Find k segments nearest to the i-th segment not including i-th segment
        rt.query(bgi::nearest(segments[i].first, k) && bgi::satisfies(different_id(i)),
                 std::back_inserter(closest[i]));
    }

    // Print the results
    for ( size_t i = 0 ; i < closest.size() ; ++i )
    {
        std::cout << "Segments closest to the segment " << i << " are:" << std::endl;
        for ( size_t j = 0 ; j < closest[i].size() ; ++j )
            std::cout << closest[i][j].second << ' ';
        std::cout << std::endl;
    }
}

Если вам нужны ВСЕ сегменты, которые ближе некоторого порога, вы можете использовать итеративные запросы (пример).

Да, R-деревья могут это делать. Они предназначены для произвольных объектов с пространственной протяженностью, не ограниченных точечными данными. На самом деле в некоторых из самых ранних примеров использовались многоугольники.

Вы пробовали их использовать?

Создайте сегментную диаграмму Вороного, а затем выберите варианты близости из соседние клетки.