Поиск соседей CGAL не работает должным образом - PullRequest
Новая
       24

Поиск соседей CGAL не работает должным образом

1 голос
/ 17 апреля 2020

Я пытаюсь найти ближайшего соседа в облаке точек к заданной точке. Я следовал примеру документации, в котором точки хранятся в пользовательском векторе, а дерево содержит только индексы. Поскольку результаты оказались не такими, как я ожидал, я также вычисляю ближайшего соседа методом грубой силы. Я объясню мой код:

У меня есть вектор точек (coarsePoints) и у меня есть вектор индексов (xC_vertices). Индексы - это точки в coarsePoints, которые можно пометить как ближайшего соседа.

Вот как я вычисляю ближайшую точку, используя алгоритм грубой силы 

for (int i = 0; i < d_vertices.size(); ++i) {
        Real minDistance = std::numeric_limits<Real>::infinity();
        int vertexId = -1;
        const auto &dPoint = highResPoints[d_vertices[i]];
        const CPF::Point_3 pD{dPoint[0], dPoint[1], dPoint[2]};
        for (int j = 0; j < xC_vertices.size(); ++j) {
            const auto &xPoint = coarsePoints[xC_vertices[j]];
            const CPF::Point_3 pC{xPoint[0], xPoint[1], xPoint[2]};

            if (CGAL::squared_distance(pC, pD) < minDistance) {
                vertexId = j;
                minDistance = CGAL::squared_distance(pC, pD);
            }
        }

При использовании CGAL у меня есть следующее (на основе примера документации): 

class My_point_property_map
{
    const sofa::helper::vector<CPF::SofaTypes::Point> &points;
    const std::vector<CPF::SofaTypes::Tetra::value_type> &xC_vertices;

public:
    typedef CPF::Point_3 value_type;
    typedef value_type &reference;
    typedef std::size_t key_type;
    typedef boost::lvalue_property_map_tag category;

    My_point_property_map(const sofa::helper::vector<CPF::SofaTypes::Point> &pts,
                          const std::vector<CPF::SofaTypes::Tetra::value_type> &xC_vertices_)
        : points(pts)
        , xC_vertices(xC_vertices_)

    {
    }

    value_type operator[](key_type k) const
    {
        const CPF::SofaTypes::Point &sPoint = points[xC_vertices[k]];
        return CPF::Point_3{sPoint[0], sPoint[1], sPoint[2]};
    }

    friend value_type get(const My_point_property_map &ppmap, key_type i) { return ppmap[i]; }

};

using SearchTraitsBase = CGAL::Search_traits_3<CPF::K>;
using SearchTraits = CGAL::Search_traits_adapter<std::size_t, My_point_property_map, SearchTraitsBase>;
using NeighborSearch = CGAL::Orthogonal_k_neighbor_search<SearchTraits>;
using Tree = NeighborSearch::Tree;
using Splitter = typename Tree::Splitter;
using SearchDistance = typename NeighborSearch::Distance;

int searchNeighbor() {
    My_point_property_map ppmap(coarsePoints, xC_vertices);
    Tree searchTree(boost::counting_iterator<int>(0),
                    boost::counting_iterator<int>(xC_vertices.size()),
                    Splitter(),
                    SearchTraits(ppmap));

    SearchDistance trDistance(ppmap);

       for (int i = 0; i < d_vertices.size(); ++i) {

// This is actually following the brute force algorithm, so I have the brute force id and distance available
        NeighborSearch search(searchTree, CPF::Point_3{dPoint[0], dPoint[1], dPoint[2]}, 1, 0, true, trDistance);
        for (const auto &searchResult : search) {
            if (searchResult.first != vertexId) {
                spdlog::get("cpf")->info("Brute force id = {}", vertexId);
                spdlog::get("cpf")->info("CGAL id = {}", searchResult.first);
                spdlog::get("cpf")->info("Brute force distance = {}", minDistance);
                spdlog::get("cpf")->info("CGAL distance = {}", searchResult.second);
            }
        }
    }
}

Это возвращает множество вершин, которые на самом деле отличаются: 

[2020-04-17 18:10:31.988] [cpf] [info] Brute force id = 386
[2020-04-17 18:10:31.988] [cpf] [info] CGAL id = 84
[2020-04-17 18:10:31.988] [cpf] [info] Brute force distance = 0.0
[2020-04-17 18:10:31.988] [cpf] [info] CGAL distance = 0.041339367896971506

Я не уверен, правильно ли я использую NeighborSearch или что происходит. Есть идеи, что может быть не так?

...