2d çizgi parçalarını işlemek için etkin bir yol

Question

Büyük bir dizi 2B çizgi parçası yaşıyorum. Yani biliyorum; Satır numarası, Her satırın başlangıç ​​(X, Y, Z) ve Bitiş (x, Y, Z). Belirli bir satır segmenti için yakınlıklı çizgi segmentleri almak istiyorum. Aynı şekilde herkes için.

benim veri derseniz o gibidir this

uygulayabilirsiniz yakınlık bulmak için;

Yani, sonunda ikimizim doğru parçasının için bir vektör olarak yakınlık hatlarını almak istiyorum. numaralı vektörün vektörünün r-tree veri yapıları ile alınabileceğini duydum. Onu arıyordum ama benim için uygun olanı bulamadım. Ayrıca opencv'e baktım, bir r-tree var ama sınıflandırıcı ve eğitim aşamasıyla ilgili bir şeyler söylüyor ... bu yüzden bana uymuyor.

kimse, hiçbir ardından komşusu hatlarını exhattını nasıl bilebilir;

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

2 = {1,4,5,6}

3 = {...} .. .. r-tree kullanarak vektörün bu tip vektör.

Kd ağacını kullanarak bu tür vektörleri alabiliriz. Ancak nokta verileri için tasarlanmıştır. Yani, bu durumda kd-ağaç kullanmak zordur. herhangi bir yardım lütfen, teşekkürler.

Answer 1

segment Voronoi diagram oluşturun, ardından komşu hücrelerden yakınlık adaylarını alın.

Answer 2

Evet, R-ağaçları bunu yapabilir. Nokta verileriyle sınırlı olmaksızın, uzamsal uzantıya sahip keyfi nesneler için tasarlanmıştır. Aslında en eski örneklerden bazıları çokgenler kullanıldı.

Onları kullanmayı denediniz mi?

Answer 3

Teorik olarak en yakın Segmentleri araştırmak, herhangi bir mekansal dizin veya alan bölümleme veri yapısı kullanarak mümkün olmalıdır. Çoğu zaman bu tür uzamsal indekslerin ara yüzleri Kutuları (AABB'ler) veya Noktaları depolamaya izin verir, bu yüzden bu durumlarda Sınırlayıcı Kutu Segmentlerini saklamak zorunda kalırsınız ve en yakın Kutuları sorguladıktan sonra karşılık gelen Segmentleri tekrar kontrol edin. Ancak, Segmentleri doğrudan dizinlemek mümkündür. Örneğin. kd ağacında, bölme düzlemlerini tanımlayan iç düğümleri içeren bir versiyon olurdu ve depolama segmentlerini yapraklar.

Boost.Geometry R-ağacı, Boost sürüm 1.56.0 ve üstü sürümleri destekler. Eğer bir eşikten daha yakın olan Segment TÜM gerekli durumda

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

Eğer iterative queries (example) kullanabilirsiniz: Aşağıda bu mekansal indeks uygulamasını kullanarak 2d segmentler için örnektir.