Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >4.OpenStreetMap Data Model

4.OpenStreetMap Data Model

作者头像
小飞侠xp
发布于 2020-02-18 09:27:16
发布于 2020-02-18 09:27:16
89001
代码可运行
举报
运行总次数:1
代码可运行

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
<?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类扩展该类。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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值。
  • 指示是否已访问该节点的布尔值。
  • 指向节点父节点的指针。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#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属性:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 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有时会有助于增加透明度,以更加复杂的代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 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)
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Leetcode solution 272: Closest Binary
https://blog.baozitraining.org/2019/05/leetcode-solution-272-closest-binary.html
包子面试培训
2019/06/03
6200
Rc-lang开发周记9 OOP之继承
本周的内容主要是做了一些继承相关的实现工作,把项目文件结构好好修了一波,还有就是加了一些测试。本周代码我觉得大多比较简单,很多地方就不过多赘述了。关于parser和ast在之前已经写好了,所以就直接进入代码生成和VM的部分
AkemiHomura
2023/04/07
2580
COMP7801 Topic 2 Spatial Data Management
Relationa indexes (like B+ trees) and query processing methods (sort-merge join, hash-join) are not applicable
pseudoyu
2023/04/11
3280
COMP7801 Topic 2 Spatial Data Management
Helm部署Ingress使用DaemonSet+Taint/Tolerations+NodeSelector
kubernetes集群中需要在指定的几个节点上只部署Nginx Ingress Controller实例,不会跑其他业务容器。
七辰
2023/10/01
4900
Helm部署Ingress使用DaemonSet+Taint/Tolerations+NodeSelector
3.Writing Larger Programs
头文件或.h文件允许将相关的函数,方法和类声明收集在一个位置。然后可以将相应的定义放置在.cpp文件中。编译器认为头声明是一个“承诺”,该定义将在后面代码找到。因此,如果编译器尚未找到定义的函数,则可以继续进行编译,直到找到定义为止。这允许以任意顺序定义(和声明)函数。
小飞侠xp
2020/02/18
4750
3.Writing Larger Programs
【Fiber】:[译]深入解析React的新协调算法
深入研究 React 的新架构 Fiber,了解新协调算法的两个主要阶段。我们将详细了解 React 如何更新组件状态(state)、属性(props)以及如何处理子元素(children)。
WEBJ2EE
2021/02/26
6500
【Fiber】:[译]深入解析React的新协调算法
Data Structure_二叉树_集合_堆_并查集_哈希表
叶子节点就是左右孩子都是空的,但是并不是每一颗树都像上图所示的那样这么规整,有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值,每一个节点都要满足,所有每一个节点下面拿出来的树都可以作为一个二叉树。既然有大于等于了,那么这科树的元素一定要有可比较性才可以。
西红柿炒鸡蛋
2019/01/23
5690
OOALV data_changed 與data_changed_finished事件
data_changed在可編輯字段的數據發生變化時才會觸發。可用來檢查輸入數據的正確性。 data_changed_finished在回車時和可編輯字段數據發生變化后,光標移動時觸發,如果可編輯字段數據檢查失敗,則不會觸發此事件。 這兩個事件都需要調用方法才能觸發。
惨绿少年.
2021/02/24
1.3K0
节点聚类分析:DeepWalk + K-means
同node2vec一致,我们也需要先找到所有节点的 条随机游走路径,每条路径长度为 。
Cyril-KI
2022/09/19
2690
节点聚类分析:DeepWalk + K-means
代码小记
  前一阵子一直在制作一款小游戏,虽说最终的成果并不完美,但也算是花了不少精力,网上批评的声音不少,但更多的则是鼓励,这也让我们颇感欣慰,自省之余,也算拾得一些信心,总之一句话,继续奋力前行~ :)
用户2615200
2018/08/02
2590
代码小记
Classification and regression techniques: decision tree and knn
Lectures 12 and 13: Classification and regression techniques: decision tree and k-nearest neighbor
403 Forbidden
2021/05/19
4820
聊聊java中的哪些Map:(八)ConcurrentSkipListMap源码分析
ConcurrentSkipListMap也是java并发包下面的重要容器,其类的继承结构如下:
冬天里的懒猫
2020/09/02
8720
【从零开始学深度学习编译器】九,TVM的CodeGen流程
【GiantPandaCV导语】这里主要是走读了一下TVM的Codegen流程,从Relay的前端一直梳理到了Graph节点的内存分配,Relay IR到TIR节点的转换,TIR图节点的Schedule优化以及Lower function发生在哪里。这篇文章只是关注了调用链,一些具体的操作比如Schedule的优化,IR到TIR节点的转化以及Lower Function没有具体解释,后面会结合更多实例去尝试理解。
BBuf
2021/07/23
2K0
leetcode(二)
给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。
努力努力再努力F
2018/09/11
6500
leetcode(二)
Data Structure堆Tree并查集图论
堆这种数据结构的应用很广泛,比较常用的就是优先队列。普通的队列就是先进先出,后进后出。优先队列就不太一样,出队顺序和入队顺序没有关系,只和这个队列的优先级相关,比如去医院看病,你来的早不一定是先看你,因为病情严重的病人可能需要优先接受治疗,这就和时间顺序没有必然联系。优先队列最频繁的应用就是操作系统,操作系统的执行是划分成一个一个的时间片的,每一次在时间片里面的执行的任务是选择优先级最高的队列,如果一开始这个优先级是固定的可能就很好选,但是在操作系统里面这个优先级是动态变化的,随着执行变化的,所以每一次如果要变化,就可以使用优先队列来维护,每一次进或者出都动态着在优先队列里面变化。在游戏中也有使用到,比如攻击对象,也是一个优先队列。所以优先队列比较适合处理一些动态变化的问题,当然对于静态的问题也可以求解,比如求解1000个数字的前100位出来,最简单的方法就是排序了,,但是这样多此一举,直接构造一个优先队列,然后出的时候出一百次最大的元素即可。这个时候算法的复杂度就是
西红柿炒鸡蛋
2018/11/07
4250
LeetCode 二叉树 题目分类汇总
简书的 markdown 都不支持 [TOC] 语法……我就不贴目录了。下面按照类别,列出了29道关于二叉树的题目。认真看会发现,其实题目核心思想都是DFS(如果使用的话),并且题目的类型并不多。
Yano_nankai
2018/10/08
1.4K0
java8中skiplist的实现及源码分析
这个类是实现了一个类似于树的二维连接的跳表,它的索引级别是放在分割开的节点里面的,基础节点拥有所有的数据。用这个便利的数据结构代替数组结构的原因主要有两点:
山行AI
2019/06/28
1.2K0
java8中skiplist的实现及源码分析
LeetCode 付费题目(一)
【题目】Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
四火
2022/07/19
2.6K0
掌握branch and cut算法原理附带C++求解TSP问题代码
branch and cut其实还是和branch and bound脱离不了干系的。所以,在开始本节的学习之前,请大家还是要务必掌握branch and bound算法的原理。
短短的路走走停停
2019/08/22
2K0
c# winfrom 可折叠的树形控件
首先需要一个可绑定实体 [Serializable] public class TreeNodeModel { private Image _nodePic; /// <summary> /// 设置图标 /// </summary> public Image NodelPic { get { return _nodePic; } set { _no
冰封一夏
2019/09/11
2.4K0
相关推荐
Leetcode solution 272: Closest Binary
更多 >
LV.1
这个人很懒,什么都没有留下~
领券
💥开发者 MCP广场重磅上线!
精选全网热门MCP server,让你的AI更好用 🚀
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验