Имея карту и корень, мы хотели бы следовать тому, какой стандартный алгоритм поможет в создании пути? - PullRequest
Новая
       15

Имея карту и корень, мы хотели бы следовать тому, какой стандартный алгоритм поможет в создании пути?

6 голосов
/ 18 декабря 2011

У нас есть некоторый набор точек (каждая точка имеет свои X и Y) и многоуровневая карта корней [точка, точка]. Мы можем двигаться через корни из любой точки в любую возможную сторону. Нам дан некоторый путь 2d точек, которым мы хотим следовать как можно ближе:

map

как рассчитать путь следующим образом:

enter image description here

что бы выглядело максимально похожим на данный путь? Каковы полезные алгоритмы, которые могут сделать это (и реализованы ли они в Boost Geometry или Graph или любой другой распространенной библиотеке C ++ с открытым исходным кодом)?

1 Ответ

2 голосов
/ 22 декабря 2011

Это действительно милая маленькая проблема. Если ваш график хорошо связан, жадный подход может работать довольно хорошо. Как в: (1) установить текущую позицию, чтобы быть узлом, ближайшим к началу пути, (2) перейти к соседнему узлу, который находится ближе всего к следующей точке в пути, пока нет более близкой точки, (3) выбрать следующая точка пути и переход к (2), если он не завершен. 

#include <assert.h>
#include <stddef.h>
#include <iostream>
#include <iterator>
#include <vector>
#include <limits>

double sq(double const d)
{
    return d * d;
}

size_t min_dist_point(
    std::vector<double> const& x,
    std::vector<double> const& y,
    std::vector<bool> const& adjacent,
    double const fx,
    double const fy
)
{
    size_t const points = x.size();

    double min_dist_sq = std::numeric_limits<double>::max();
    size_t min_point;

    for (size_t j = 0; j < points; ++j) {
        if (!adjacent[j]) { continue; }
        double const dist_sq = sq(x[j] - fx) + sq(y[j] - fy);

        if (dist_sq < min_dist_sq) {
            min_point = j;
            min_dist_sq = dist_sq;
        }
    }
    assert(min_dist_sq != std::numeric_limits<double>::max());

    return min_point;
}

template <class out_t>
out_t f(
    std::vector<double> const& x,
    std::vector<double> const& y,
    std::vector<std::vector<bool> > adjacent,
    std::vector<double> const& follow_x,
    std::vector<double> const& follow_y,
    out_t out
)
{
    size_t const points = x.size();
    size_t const follow_len = follow_x.size();
    for (size_t i = 0; i < points; ++i) {
        adjacent[i][i] = 1;
    }

    std::vector<bool> const all (points, true);
    size_t pos = min_dist_point(x, y, all, follow_x[0], follow_y[0]);
    *out++ = pos;

    for (size_t i = 1; i < follow_len; ++i) {
        for (;;) {
            size_t const next = min_dist_point(x, y, adjacent[pos], follow_x[i], follow_y[i]);
            if (next == pos) { break; }
            *out++ = (pos = next);
        }
    }

    return out;
}

Если этот алгоритм зацикливается, вам потребуется поиск A *.

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/astar_search.html

...