有效的方式来处理2D线段

我有大量的二维线段。所以，我知道;行号，开始（X，Y，Z）和结束（x，Y，Z）的每个线段。我想获得给定线段的邻近线段。同样适用于所有人。有效的方式来处理2D线段

要找到我可以申请this

如果我说我的数据是为附近;

enter image description here 因此，在末尾我想要接近线作为每个线段的向量。我听说这种类型的矢量可以与r-tree数据结构一起拍摄。我正在搜索它，但仍找不到相关的一个给我。另外我看了opencv，还有一棵r-tree，但是它讲述了关于分类器和训练阶段......所以，我想它不适合我。

谁能知道如何获得行号，那么其邻居行为ex;

1 = {2,4-，7,66,32,12}

2 = {1,4,5,6}

3 = {...} .. .. 这种类型的向量使用r-tree。

我知道，我们可以用kd-tree得到这种类型的向量。但它是为点数据设计的。所以，我认为这种情况很难使用kd-tree。任何帮助，谢谢。

来源

2013-03-18 gnp

建立一个segment Voronoi diagram，然后从邻居单元中取出邻近候选。

来源

2013-03-18 17:45:34

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

您是否尝试过使用它们？

来源

2013-03-18 17:47:20

我试过使用它。但我无法用opencv搞清楚。正如我发现的那样，训练阶段和分类器。我，我没有训练阶段..如果你在这方面指导我，我真的很感激。谢谢， – gnp 2013-03-18 21:34:41

R树与分类无关。他们应该有一个“寻找最近的邻居”功能。但我从来没有使用过opencv。 – 2013-03-18 21:56:27

然后，请让我知道我可以用来获得这种最近邻居的其他图书馆。谢谢 – gnp 2013-03-19 08:45:21

理论上可以使用任何种类的空间索引或空间分区数据结构搜索最近的分段。大多数情况下，这种空间索引的界面允许存储Boxes（AABB）或Points，因此在这些情况下，您将被迫存储边界框的分段，然后在查询最近的分栏后再次检查相应的分段。但是，可以直接对Segments进行索引。例如。在kd-tree的情况下，它将是一个包含定义分割平面的内部节点和存储分段的叶子的版本。

Boost.Geometry R树支持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; 
    } 
}

在您需要的所有比某个阈值越接近段的情况下，你可以使用iterative queries（example）。

来源

2014-08-01 15:43:48

有效的方式来处理2D线段

回答

相关问题