有一些地图和一些根我们想要遵循什么标准算法有助于创建路径？

Question

我们有一些点(每个点都有X和Y)和一个根的多点图[point,point].我们可以在任何可能的方向从任何一点移动到任何一点.我们给出了一些我们希望尽可能接近的2d点的路径:

如何计算这样的路径:

这对于给定的路径看起来尽可能相似吗？什么是有用的算法可以做这样的事情(并在Boost Geometry或Graph或任何其他常见的开源C++库中实现)？

Answer 1

这是一个非常可爱的小问题。如果你的图连接良好，贪心方法可能会很有效。如：（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