c++ - Manera eficiente de manejar segmentos de línea 2D

data-structures kdtree

Question

Estoy teniendo un gran conjunto de segmentos de línea 2D. Así que sé; Número de línea, Begin (X, Y, Z) y End (x, Y, Z) de cada segmento de línea. Quiero obtener segmentos de líneas de proximidad para un segmento de línea determinado. Del mismo modo para todos.

Para encontrar la proximidad puedo aplicar esto

Si digo mis datos, es como;

Entonces, al final quiero obtener líneas de proximidad como vector para cada segmento de línea . Escuché que este tipo de vector de vector se puede tomar con estructuras de datos de árbol r. Estaba buscándolo pero aún no pude encontrar el relevante para mí. También miré en opencv, hay un r-tree pero dice algo sobre clasificador y fase de entrenamiento ... así que, supongo que no me queda bien.

¿Alguien puede saber cómo obtener la línea no, luego sus líneas vecinas para ex;

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

2 = {1,4,5,6}

3 = {...} .. .. este tipo de vector de vector usando r-tree.

Lo sé, podemos obtener este tipo de vectores usando kd-tree. Pero está diseñado para los datos de puntos. Entonces, es difícil usar kd-tree para este caso, creo. cualquier ayuda por favor, gracias.

Answer 1

Construya un diagrama de segmentos de Voronoi , luego tome candidatos de proximidad de las celdas vecinas.

Answer 2

Sí, los árboles R pueden hacer esto . Están diseñados para objetos arbitrarios con extensión espacial, no se limitan a datos de puntos. En realidad, algunos de los ejemplos más antiguos usaban polígonos .

¿Has intentado usarlos?

Answer 3

Teóricamente, la búsqueda de los Segmentos más cercanos debería ser posible utilizando cualquier tipo de estructura de datos de partición espacial o índice espacial. Muy a menudo, la interfaz de dicho índice espacial permite almacenar Cajas (AABB) o Puntos, por lo que en estos casos se vería forzado a almacenar Cajas de Segmentos delimitadoras y luego, después de consultar los Casilleros más cercanos, verificar nuevamente los Segmentos correspondientes. Sin embargo, es posible indexar Segmentos directamente. Por ejemplo, en el caso de kd-tree sería una versión que contiene nodos internos que definen planos de división y hojas que almacenan segmentos.

Boost.Geometry R-tree admite segmentos en Boost versión 1.56.0 y superior. A continuación se muestra el ejemplo de 2d segmentos que usan esta implementación de índice espacial:

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

En caso de que necesitara TODOS los Segmentos que están más cerca que algún umbral, podría usar consultas iterativas ( ejemplo ).