эффективный способ обработки двухмерных отрезков

Question

эффективный способ обработки двухмерных отрезков

У меня огромный набор 2D отрезков. Итак, я знаю; Номер строки,
Начало (X, Y, Z) и Конец (x, Y, Z) каждого отрезка. я хочу получить
сегменты ближней линии для данного отрезка. Аналогично для всех.

Чтобы найти близость я могу подать заявку этот

Если я скажу мои данные, это как;

введите описание изображения здесь
Итак, в конце Я хочу получить бесконтактные линии как вектор для каждого отрезка. Я слышал этот тип вектор вектора может быть взято с помощью структур данных r-дерева. Я искал это, но все еще не мог найти соответствующий для меня. Также я посмотрел в opencv, есть r-дерево, но оно говорит кое-что о классификаторе и фазе обучения … так что, думаю, оно мне не подходит.

Может кто-нибудь знает, как получить линия нет, то соседние линии для бывших;

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

2 = {1,4,5,6}

3 = {…} .. ..
этот тип вектора с использованием r-дерева.

Я знаю, мы можем получить этот тип векторов, используя kd-дерево. Но он рассчитан на точечные данные. Я думаю, что в этом случае сложно использовать kd-дерево.
любая помощь, пожалуйста, спасибо.

8

c++data-structures kdtree r-tree

Решение

Другие решения

Да, R-деревья могут сделать это. Они предназначены для произвольных объектов с пространственным расширением, не ограниченных точечными данными. На самом деле некоторые из самых ранних примеров, используемых многоугольники.

Вы пытались их использовать?

3

Построить сегментная диаграмма Вороного, затем возьмите кандидатов близости из соседних ячеек.

1

Источник

Accepted Answer

Теоретически поиск ближайших сегментов должен быть возможен с использованием любого типа структуры данных пространственного индекса или пространственного разделения. Чаще всего интерфейс такого пространственного индекса позволяет хранить Ящики (AABB) или Точки, поэтому в этих случаях вы будете вынуждены хранить ограничивающие Ящики с Сегментами, а затем после запроса ближайших Ящиков снова проверить соответствующие Сегменты. Однако можно индексировать сегменты напрямую. Например. в случае kd-дерева это будет версия, содержащая внутренние узлы, определяющие плоскости разбиения и сегменты хранения листьев.

Boost.Geometry R-дерево поддерживает сегменты в Увеличение версия 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;
}
}

В случае, если вам нужны ВСЕ Сегменты, которые ближе, чем какой-либо порог, вы можете использовать итерационные запросы (пример).

4