cách hiệu quả để xử lý các đoạn đường 2d

Question

Tôi có tập hợp các đoạn đường 2D lớn. Tôi biết vậy; Số dòng, Bắt đầu (X, Y, Z) và Kết thúc (x, Y, Z) của mỗi đoạn đường. Tôi muốn nhận được phân đoạn đường lân cận cho một đoạn đường nhất định. Tương tự như vậy cho tất cả.

Để tìm sự gần gũi tôi có thể áp dụng this

Nếu tôi nói dữ liệu của tôi nó là như;

Vì vậy, vào cuối Tôi muốn có được dòng gần như một vector cho từng phân khúc dòng. Tôi nghe loại vector của vector này có thể được thực hiện với cấu trúc dữ liệu r-tree. Tôi đã tìm kiếm nó nhưng vẫn không thể tìm thấy một trong những có liên quan cho tôi. Ngoài ra tôi nhìn vào opencv, có một r-tree nhưng nó nói một cái gì đó về phân loại, và giai đoạn đào tạo ... vì vậy, tôi đoán nó không phù hợp với tôi.

Bất kỳ ai cũng có thể biết cách nhận dòng không, sau đó là dòng lân cận cho ví dụ cũ;

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

2 = {1,4,5,6}

3 = {...} .. .. loại vector này của vector sử dụng r-tree.

Tôi biết, chúng tôi có thể lấy loại vectơ này bằng kd-tree. Nhưng nó được thiết kế cho dữ liệu điểm. Vì vậy, rất khó để sử dụng kd-tree cho trường hợp này tôi nghĩ. bất kỳ trợ giúp nào, xin cảm ơn.

Answer 1

Tạo segment Voronoi diagram, sau đó lấy các ứng cử viên lân cận từ các ô lân cận.

Answer 2

Có, Cây có thể làm điều này. Chúng được thiết kế cho các đối tượng tùy ý với mở rộng không gian, không giới hạn dữ liệu điểm. Trên thực tế, một số ví dụ sớm nhất đã sử dụng các đa giác đa giác.

Bạn đã thử sử dụng chúng chưa?

Answer 3

Về mặt lý thuyết, tìm kiếm Phân đoạn gần nhất có thể sử dụng bất kỳ loại cấu trúc dữ liệu phân vùng không gian hoặc chỉ mục nào. Thông thường giao diện của chỉ mục không gian như vậy cho phép lưu trữ Hộp (AABB) hoặc Điểm trong trường hợp này, bạn buộc phải lưu trữ Hộp phân đoạn và sau đó sau khi truy vấn Hộp gần nhất, hãy kiểm tra lại Phân đoạn tương ứng. Tuy nhiên, bạn có thể lập chỉ mục Phân đoạn trực tiếp. Ví dụ. trong trường hợp của kd-tree, nó sẽ là một phiên bản chứa các nút bên trong xác định các mặt phẳng tách và các mảng lưu trữ lá.

Boost.Geometry R-tree hỗ trợ Phân đoạn trong Boost phiên bản 1.56.0 trở lên. Dưới đây là ví dụ cho các phân đoạn 2d sử dụng thực hiện chỉ số không gian này:

// 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; 
    } 
} 

Trong trường hợp bạn cần tất cả phân đoạn được gần hơn một số ngưỡng bạn có thể sử dụng iterative queries (example).