4.OpenStreetMap Data Model

OpenStreetMap是一个开源项目，旨在为用户免费创建生成世界各的地图。

OpenStreetMap数据以OSM XML文件（.osm文件）的形式出现。

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="CGImap 0.0.2">
 <bounds minlat="54.0889580" minlon="12.2487570" maxlat="54.0913900" maxlon="12.2524800"/>
 <node id="298884269" lat="54.0901746" lon="12.2482632" user="SvenHRO" uid="46882" visible="true" version="1" changeset="676636" timestamp="2008-09-21T21:37:45Z"/>
 <node id="261728686" lat="54.0906309" lon="12.2441924" user="PikoWinter" uid="36744" visible="true" version="1" changeset="323878" timestamp="2008-05-03T13:39:23Z"/>
 <node id="1831881213" version="1" changeset="12370172" lat="54.0900666" lon="12.2539381" user="lafkor" uid="75625" visible="true" timestamp="2012-07-20T09:43:19Z">
  <tag k="name" v="Neu Broderstorf"/>
  <tag k="traffic_sign" v="city_limit"/>
 </node>
 ...
 <node id="298884272" lat="54.0901447" lon="12.2516513" user="SvenHRO" uid="46882" visible="true" version="1" changeset="676636" timestamp="2008-09-21T21:37:45Z"/>
 <way id="26659127" user="Masch" uid="55988" visible="true" version="5" changeset="4142606" timestamp="2010-03-16T11:47:08Z">
  <nd ref="292403538"/>
  <nd ref="298884289"/>
  ...
  <nd ref="261728686"/>
  <tag k="highway" v="unclassified"/>
  <tag k="name" v="Pastower Straße"/>
 </way>
 <relation id="56688" user="kmvar" uid="56190" visible="true" version="28" changeset="6947637" timestamp="2011-01-12T14:23:49Z">
  <member type="node" ref="294942404" role=""/>
  ...
  <member type="node" ref="364933006" role=""/>
  <member type="way" ref="4579143" role=""/>
  ...
  <member type="node" ref="249673494" role=""/>
  <tag k="name" v="Küstenbus Linie 123"/>
  <tag k="network" v="VVW"/>
  <tag k="operator" v="Regionalverkehr Küste"/>
  <tag k="ref" v="123"/>
  <tag k="route" v="bus"/>
  <tag k="type" v="route"/>
 </relation>
 ...
</osm>

XML文件包含几个元素类型，这些元素类型对您要编写的代码很重要：节点、方式和关系。

节点

节点是OpenStreetMap数据模型中最基本的元素之一。每个节点指示一个具有标识符id、纬度lat和经度lon的点。node元素中还有其他与此项目无关的XML属性，例如将节点添加到数据集中时的用户id和时间戳。另外，一个节点可以有多个标签来提供附加信息。

道路

道路是表示地图中某个要素的有序节点列表。这个特征可以是道路，公园的边界，或者地图上的其他特征。每种道路至少有一个标记，该标记表示关于该道路的一些信息，并且每种道路还属于至少一个关系，如下所述。

关系

关系是记录其他数据元素之间关系的数据结构。来自OpenStreetMap wiki的示例包括：

• 一种路线关系，列出形成主要公路、自行车道或公共汽车路线的方式。

• 描述有孔区域的多多边形，该区域的外边界和内边界由两种方式给出。

IO2D项目

https://github.com/cpp-io2d/P0267_RefImpl/tree/master/P0267_RefImpl/Samples/maps

代码结构

该项目的启动代码可在此处找到。
在仓库中，应该看到以下五个目录：

• cmake

该目录包含一些CMakeLists.txt文件，这些文件是项目查找必要的库所必需的。无需为此项目使用此目录。

• instructions

该目录包含一组练习的标记指令文件。同样，不需要在这里直接使用文件，但是在处理项目时，每组指令将显示在终端工作区中，以进行适当的练习。

• src

该项目的源代码包含在此处

• test

此目录包含使用Google Test框架实现的各种练习的单元测试。在开发代码时，查看此目录中的相关测试以查看预期的答案和相应的代码可能会有所帮助。如果代码未通过测试，则控制台将告诉哪个文件包含失败的测试。

• thirdparty

此目录包含此项目已包含的第三方库。无需直接使用此代码

src

main.cpp控制程序的流程，完成四个主要任务：

• OSM数据被读入程序。
• 创建一个RouteModel对象，将OSM数据存储在可用的数据结构中。
• RoutePlanner对象是使用RouteModel创建的。此计划器最终将对模型数据执行A*搜索，并将搜索结果存储在RouteModel中。
• RouteModel数据是使用IO2D库呈现的。

model.h and model.cpp

这些文件来自IO2D示例代码。它们用于定义读取和存储OSM数据的数据结构和方法。OSM数据存储在一个模型类中，该模型类包含节点、方法、道路和其他OSM对象的嵌套结构

RouteModel类

Model当前代码中存在的类并不包含执行A *搜索所需的所有数据或方法，因此我们将用一个RouteModel类扩展该类。

class RouteModel : public Model {

  public:
    //RouteModel 的 Node 也是继承的
    class Node : public Model::Node {
      public:
        // Add public Node variables and methods here.

        Node(){
            std::cout<<"RouteModel Init"<<"\n";
        }
        //因为有init 一个pointer parent_model, 因此一定要写成 initial list 的方式
        Node(int idx, RouteModel * search_model, Model::Node node) : Model::Node(node), parent_model(search_model), index(idx) {
            std::cout<<"RouteModel Init"<<"\n";
        }

      private:
        // Add private Node variables and methods here.
        int index;
        RouteModel * parent_model = nullptr;

    };

    // Add public RouteModel variables and methods here.
    RouteModel(const std::vector<std::byte> &xml);

    //这个 path 存结果
    std::vector<Node> path; // This variable will eventually store the path that is found by the A* search.

    //Task2:Add a public "getter" method SNodes. This method should return a reference to the vector of Nodes stored as m_Nodes.
    std::vector<Node>& SNodes(){
        return m_Nodes;
    }

  private:
    // Add private RouteModel variables and methods here.

    //Taks1:Add a private vector of Node objects named m_Nodes. This will store all of the nodes from the Open Street Map data.
    //m_Nodes 存所有open street map 的 data, 之后给Astar 用
    std::vector<Node> m_Nodes;
};

Node 类

Model::Node当前代码中存在的类不包含执行A *搜索所需的所有数据。为了执行搜索，最理想的是每个节点至少包含以下信息：

• 节点的g值。
• 节点的h值。
• 指示是否已访问该节点的布尔值。
• 指向节点父节点的指针。

#include <limits>
#include <cmath>
#include <unordered_map>
#include "model.h"
#include <iostream>
//因為Model 裡面只有一個Node 的資訊, 要能做A*, 你需要所有的Node,
//因此我們繼承Model 來造一個RouteModel 準備收集所有要用的Node 給A*

/*
Task:
In route_model.h:

Add a private vector of Node objects named m_Nodes. This will store all of the nodes from the Open Street Map data.
Add a public "getter" method SNodes. This method should return a reference to the vector of Nodes stored as m_Nodes.



*/
class RouteModel : public Model {

  public:

    //RouteModel 的 Node 也是繼承來的
    class Node : public Model::Node {
        /*
        The Node Class
        The Model::Node class that exists in the current code doesn't contain all the data that would be needed to perfom an A* search.
        In order to perform a search, it would be ideal for each node to contain at least the following information:

            1.The g-value for the node.
            2.The h-value for the node.
            3.A boolean to indicate if the node has been visited.
            4.A pointer to the node's parent.

        In this exercise, you will fill out the RouteModel::Node class in route_model.h, which will extend the Model::Node class
        so that the data above, along with a few other useful variables, can be included with each node.
        Note that the RouteModel::Node class already has the following private variables:

            1.An int index.
            2.A pointer to a RouteModel object named parent_model. This variable is important,
                as it allows each node to access data stored in the parent model that the node belongs to.

        To complete this exercise:
        Add the following public variables to the RouteModel::Node class:
            1.A Node pointer parent, which is initialized to a nullptr.
            2.A float h_value, which is initialized to the maximum possible: std::numeric_limits<float>::max().
            3.A float g_value, which is initialized to 0.0.
            4.A bool visited, which is initialized to false.
            5.A vector of Node pointers named neighbors.

        Pass testing:
            [==========] Running 2 tests from 1 test case.
            [----------] Global test environment set-up.
            [----------] 2 tests from RouteModelTest
            [ RUN      ] RouteModelTest.RouteModelData
            [       OK ] RouteModelTest.RouteModelData (67 ms)
            [ RUN      ] RouteModelTest.RouteModelNode
            RouteModel Init
            RouteModel Init
            [       OK ] RouteModelTest.RouteModelNode (61 ms)
            [----------] 2 tests from RouteModelTest (128 ms total)

            [----------] Global test environment tear-down
            [==========] 2 tests from 1 test case ran. (128 ms total)
            [  PASSED  ] 2 tests.


        */
      public:

        //Add
        Node * parent = nullptr;
        float h_value = std::numeric_limits<float>::max();
        float g_value = 0.0;
        bool visited = false;
        std::vector<Node*> neighbors;

        // Add public Node variables and methods here.
        Node(){
            std::cout<<"RouteModel Init"<<"\n";
        }
        //因為有init 一個pointer parent_model, 因此一定要寫成 initial list 的方式
        Node(int idx, RouteModel * search_model, Model::Node node) : Model::Node(node), parent_model(search_model), index(idx) {
            std::cout<<"RouteModel Init"<<"\n";
        }




      private:
        // Add private Node variables and methods here.

        //An int index.
        int index;
        //A pointer to a RouteModel object named parent_model. This variable is important,
        //as it allows each node to access data stored in the parent model that the node belongs to.
        RouteModel * parent_model = nullptr;

    };

    // Add public RouteModel variables and methods here.
    RouteModel(const std::vector<std::byte> &xml);

    //這個 path 最後會存著結果
    std::vector<Node> path; // This variable will eventually store the path that is found by the A* search.

    //Task2:Add a public "getter" method SNodes. This method should return a reference to the vector of Nodes stored as m_Nodes.
    std::vector<Node>& SNodes(){
        return m_Nodes;
    }

  private:
    // Add private RouteModel variables and methods here.

    //Taks1:Add a private vector of Node objects named m_Nodes. This will store all of the nodes from the Open Street Map data.
    //這個m_Nodes 會拿來存所有open street map 的 data, 之後給Astar 用
    std::vector<Node> m_Nodes;
};

this 指针

IncrementDistance()方法隐式引用当前Car实例的distance属性：

// The Car class
class Car {
  public:
    // Method to print data.
    void PrintCarData() {
        cout << "The distance that the " << color << " car " << number << " has traveled is: " << distance << "\n";
    }

    // Method to increment the distance travelled.
    void IncrementDistance() {
        distance++;
    }

    // Class/object attributes
    string color;
    int distance = 0;
    int number;
};

可以通过使用this指向当前类实例的指针在C ++中使其明确。使用this有时会有助于增加透明度，以更加复杂的代码：

// The Car class
class Car {
  public:
    // Method to print data.
    void PrintCarData() {
        cout << "The distance that the " << this->color << " car " << this->number << " has traveled is: " << this->distance << "\n";
    }

    // Method to increment the distance travelled.
    void IncrementDistance() {
        this->distance++;
    }

    // Class/object attributes
    string color;
    int distance = 0;
    int number;
};

创建RouteModel节点

RouteModel类，并且已经完成了RouteModel::Node嵌套类，可以创建RouteModel节点。
当RouteModel调用构造函数，它调用Model与开放街道地图数据的构造。发生这种情况时，Model:Node将创建对象的集合。但是，为了执行A *搜索，将需要使用RouteModel::Node对象。
修改RouteModel构造函数。构造函数将使用Model:Node对象向量创建新RouteModel::Node对象。RouteModel::Node然后，这些对象将存储在的m_Nodes向量中

• 在RouteModel构造函数中route_model.cpp，编写一个带计数器的for循环，以循环遍历由Model::Node给出的s 的向量this->Nodes()。
• 对于Model循环中的每个节点，使用RouteModel::Node构造函数创建一个新节点，并将新节点推到的后面m_Nodes。
• 使用RouteModel::Node接受三个参数的构造函数：Node(int idx, RouteModel * search_model, Model::Node node)