高效处理2D线段的方法

Question

我有一大堆二维线段，所以我知道每条线段的线号，起始点（X，Y，Z）和结束点（x，Y，Z）。我想要为给定的线段获取相邻线段。同样适用于所有线段。

为了找到相邻线段，我可以应用this 如果我说我的数据是这样的;

所以，最后我想要每个线段的相邻线段作为向量。我听说可以使用r树数据结构获取这种类型的向量的向量。我正在搜索它，但仍然找不到适合我的相关内容。另外，我查看了opencv，有一个r-tree但它关于分类器和训练阶段说些什么... 所以，我猜它不适合我。

有人知道如何获取线号，然后是它的相邻线路，例如；

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

2 = {1,4,5,6}

3 = {...} .. .. 这种向量的向量使用r树。

我知道，我们可以使用kd树获取这种类型的向量。但它是为点数据设计的。因此，我认为很难在这种情况下使用kd树。 请帮忙，谢谢。

- gnp

Answer 1

理论上，可以使用任何空间索引或空间分割数据结构来搜索最近的线段。通常这种空间索引的接口允许存储框（AABBs）或点，因此在这些情况下，您将被强制存储线段的边界框，然后在查询最接近的框后再检查相应的线段。但是也可以直接索引线段。例如，在kd树的情况下，它将是一个版本，其中包含定义分裂平面的内部节点和存储线段的叶子节点。

Boost.Geometry R-tree支持线段，Boost版本1.56.0及以上版本中提供了该实现的2d线段示例。Boost.Geometry Boost

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

如果您需要所有距离小于某个阈值的片段，您可以使用迭代查询（示例）。

- Adam Wulkiewicz

Answer 2

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

你尝试过使用它们吗？

- Has QUIT--Anony-Mousse

---

我尝试使用它，但是我无法在OpenCV中弄清楚。因为我找到的东西都说训练阶段和分类器。而我没有训练阶段...如果您能指导我，我将不胜感激。谢谢。 - gnp

R树与分类无关。它们应该有一个“查找最近邻居”的功能。但我从未使用过OpenCV。 - Has QUIT--Anony-Mousse

请告诉我其他可以用来获取最近邻居的库，谢谢。 - gnp

实际上，我试图使用以下两个链接...但是，对我来说，我找不到任何一种方法适用于我的情况。http://docs.opencv.org/modules/ml/doc/random_trees.html和http://public.cranfield.ac.uk/c5354/teaching/ml/examples/c++/opticaldigits_ex/randomforest.cpp 任何帮助都将不胜感激。谢谢。 - gnp

随机森林通常指的是决策树。它们与R树无关，完全不同，除了在某个地方使用类似树形结构之外，它们几乎没有任何共同点。 - Has QUIT--Anony-Mousse

尝试使用http://libspatialindex.github.com/代替（我尚未验证它是否可以处理空间对象而不仅仅是点）。 - Has QUIT--Anony-Mousse

Answer 3

构建一个分割 Voronoi 图，然后从相邻单元中获取近距离候选项。

- n. m.