有效的方式來處理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線段

回答

相關問題