2d線分を効率的に処理する

Question

私は巨大な2D線分を持っています。だから私は知っている。行番号、 各行セグメントの始点（X、Y、Z）と終点（x、Y、Z）。私は 与えられた線セグメントの近接線分を取得したい。同様にすべての人。私は自分のデータを言うなら、それはようであるthis

を適用することができ接近を検索するに

。

だから、最後で私は、各線のためのベクターとしての近接ラインを取得したいです。私はこのタイプのベクトルのベクトルは、r - ツリーのデータ構造で取ることができると聞いた。私はそれを探していたが、それでも私のために関連するものを見つけることができなかった。また、私はopencvを見ましたが、rツリーがありますが、それはクラシファイアとトレーニングフェーズについて何かを言います...私はそれが私に合わないと思います。

入手方法を知っている人は誰でもいいですか？ラインナンバー、その隣のライン for ex;

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

2 = {1,4,5,6}

3 = {...} .. .. このタイプのベクトルのベクトルはr-treeを使用しています。

私は、このタイプのベクトルをkd-treeを使って得ることができます。しかし、ポイントデータ用に設計されています。ですから、このケースではkd-treeを使うのは難しいと思います。 助けてください、ありがとうございます。

Answer 1

segment Voronoi diagramを構築し、隣接セルから近接候補を取ります。

Answer 2

はい、Rツリーでこれを行うことができます。これらは、ポイントデータに限らず、空間的な拡張を持つ任意のオブジェクト用に設計されています。実際には、最も初期の例のいくつかはポリゴンを使用しました。

あなたはそれらを試しましたか？

Answer 3

任意の種類の空間インデックスまたは空間分割データ構造を使用して、最も近いセグメントを理論的に検索する必要があります。ほとんどの場合、このような空間インデックスのインターフェースはBoxes（AABBs）やPointを保存することができます。この場合、Segmentsの境界Boxを保存し、最も近いBoxesを再度照会した後、対応するSegmentsを再度確認する必要があります。ただし、Segmentsを直接インデックス登録することは可能です。例えば。 kd-treeの場合、分割面を定義する内部ノードを含むバージョンであり、セグメントを格納する。

Boost.Geometry R-treeは、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）を使用することができ、いくつかのしきい値よりも近いセグメントの全てを必要とする場合には。