处理二维线段的有效方法

Question

我有大量的二维线段。所以，我知道，每个线段的行号，开始(X，Y，Z)和结束(x，Y，Z)。我想得到一个给定线段的接近线段。所有人也一样。 要找到接近度，我可以应用这

如果我说我的数据是一样的；

​

因此，在最后的，我想得到接近线作为每个线段的向量。我听说这种向量向量可以用r树数据结构来取.我在找，但还是找不到相关的。我也看过opencv，有一个r-树，但是它说明了分类器和训练阶段.所以，我想它不适合我。

谁知道如何得到线no，那么它的邻接线表示ex；

1= {2,4，7,66,32,12} 2= {1,4,5,6} 3={ . }。。。这类向量向量使用r-树.

我知道，我们可以用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;
    }
}

如果您需要比某些阈值更接近的所有段，则可以使用迭代查询 (示例)。

Answer 2

是的，R-树可以做。它们是为具有空间扩展的任意对象而设计的，而不限于点数据。实际上，一些最早的例子使用了多边形。

你试过用它们吗？

Answer 3

构建一个段Voronoi图，然后从邻近的单元中获取邻近候选单元。