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

Question

У меня есть файл osm для моего города, я использую Libosmium для его чтения, и я сохраняю узлы каждого пути как вершины моего графа и делаю ребра между каждыми двумя соседними узлами каждым способом и вычисляю эвклидово расстояние между ними.

проблема в том, что:

Пути не связаны друг с другом! Я не могу добраться до пункта назначения из моего источника, даже если на карте Google есть маршрут, но между путями нет пересечения узлов (нет общих узлов), поэтому я не могу добраться до пункта назначения! Какие узлы я должен добавить в свой график и как правильно их связать? чтобы я мог добраться до пункта назначения с моего узла?
Код, который я использовал для создания ребер, следующий

// Loop the Whole Map of Ways
  for ( it = MyWayMap.begin(); it != MyWayMap.end(); it++ ){
      WayCounter++;
      NodesOfWayIndex = 0; //reset Index
      //define a vector of nodes with size of Way
      vector<Vertex> WayNodes(it->second.nodeRefList.size());
      //======================================================
      // Loop The Nodes of Each way
      for(auto j = it->second.nodeRefList.begin(); j != it->second.nodeRefList.end(); ++j){

          VertexID = it->second.nodeRefList.at(NodesOfWayIndex);
          //declare Variable for Eucledean Distance
          double dist = 0;
          WayNodes[NodesOfWayIndex] = VertexID ;
          //---------------------------------------------------------------------
          // if the VertexId doesn't exist yet give back do the following
          if(BelalMap.find(VertexID) == BelalMap.end()){
              // assign idType values to the idmap
              //idmap[IdMapIndex] = VertexID;
              IdMapIndex++;
              // Fill BelalMap
              BelalMap.insert({VertexID,IdMapIndex});
              if(NodesOfWayIndex == 0) Node1 = IdMapIndex;
              else {
                  Node2 = IdMapIndex ;
                  dist = distance(WayNodes[NodesOfWayIndex - 1], WayNodes[NodesOfWayIndex]);
                  add_edge(Node1, Node2,dist,MyGraph);
                  add_edge(Node2, Node1,dist,MyGraph);
                  Node1 = Node2 ;

                } // end else
            }//end of outer if
          //--------------------------------------------------------------------
          //if the VertexId already exists give back it's Vertex number
          else {
              if(NodesOfWayIndex == 0) Node1 = BelalMap.find(VertexID)->second;
              else {
                  // Calculating Eucledan Distance Between Nodes
                  dist = distance(WayNodes[NodesOfWayIndex - 1], WayNodes[NodesOfWayIndex]);
                  Node2 = BelalMap.find(VertexID)->second;
                  add_edge(Node1, Node2,dist,MyGraph);
                  add_edge(Node2, Node1,dist,MyGraph);
                  Node1 = Node2 ;
                }// end of inner else
            }//end of outer else

          //======================================================

          // increase The indexs after iterating each node.
          NodesOfWayIndex++;
        }// end of Nodes of Way Loop
    }// end of Ways of Map Loop

Answer 1

О том, как построить граф маршрутизации из OSM XML, уже рассказывалось здесь: https://help.openstreetmap.org/questions/19213/how-can-i-convert-an-osm-xml-file-into-a-graph-representation/19214. Цитата из этого ответа:

Предполагая, что вам нужны только дороги, возможный алгоритм таков:

1. разобрать все способы; отбросьте те, которые не являются дорогами, а для остальных запомните идентификаторы узлов, из которых они состоят, увеличивая "счетчик ссылок" для каждого узла, на который имеется ссылка.
2. разобрать все пути второй раз; путь обычно становится одним ребром, но если какие-либо узлы, кроме первого и последнего, имеют счетчик ссылок больше единицы, тогда разделите путь на два ребра в этой точке. Узлы со счетчиком ссылок, равным единице, которые не являются ни первыми, ни последними, могут быть отброшены, если вам не нужно вычислять длину ребра.
3. (если вам нужна геометрия для узлов вашего графа) сейчас проанализируйте раздел узлов XML, записав координаты для всех узлов, которые вы сохранили.

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

Судя по вашему описанию, вы забыли создать края между разными способами. Способы связаны друг с другом, если они совместно используют узел. Вам нужно разделить путь в каждом узле, который используется более чем одним путем, чтобы создать правильные ребра в вашем графе маршрутизации.

Также см. Раздел "Маршрутизация" в вики OSM.