有效的方式来处理2D线段(efficient way to handle 2d line segme

我有巨大的一套2D线段。所以，我知道; 行号，开始（X，Y，Z），并且每个线段的结束（X，Y，Z）。我想接近线段对于给定的线段。同样，对于所有。
为了找到接近我可以申请这个

如果我说我的数据是作为;

所以，最后我想接近线为每个线段的向量 。我听说过这种类型的载体的载体可以与R-tree数据结构来考虑。我正在寻找，但还是没能找到相关的一个我。此外，我看着在OpenCV中，有一个R树，但它说一些关于分类和训练阶段......所以，我想它不适合我。

任何人都可以知道如何获得线前没有，那么它的邻居线 ;

1 = {2,4-，7,66,32,12}
2 = {1,4,5,6}
3 = {...} .. ..使用R-树这种类型的载体的载体。

我知道，我们可以得到这样的类型使用kd树载体。但它是专为点数据。因此，它是很难使用kd树对于这种情况，我认为。任何帮助，请，谢谢。

Answer 1:

理论上搜索最近的段应该使用任何种类的空间索引或空间分割数据结构是可能的。大多数情况下这种空间索引的接口允许存储盒（的AABB）或点，以便在这些情况下，您会被强制存储边界段的复选框，然后查询最近盒后再次检查相应的细分。但是它可以直接索引段。例如，在kd树的情况下，它应该是一个包含限定分裂平面和叶子存储段内部节点的一个版本。

Boost.Geometry R树支持区隔升压版本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;
    }
}

如果你需要的所有比某个阈值，你可以使用接近段的迭代查询（例如）。