Having a map and a root, we would like to follow what standard algorithm will help in creating the path?

Question

We have some set of points (each point has its own X and Y) and a multi-valued mapping of roots [point, point]. We can move along the roots from any point to any in any possible direction. We are given a certain path of 2d points along which we want to follow as close as possible:

how to calculate this way:

which will look as close to the given path as possible? What useful algorithms can such things do (and are implemented in Boost Geometry or Graph, or any other open source C ++ shared library)?

Answer 1

This is a very cute little problem. If your schedule is well connected, then a greedy approach may work pretty well. As in: (1) set the current position as the node closest to the beginning of the path, (2) move to the neighboring node, which is closest to the next point of the path until there is a point closer, (3) select the next point in the path and go (2) if not done.

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

If this algorithm gets stuck in a loop, you will need to search for A *.

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