轨道交通GPS数据约简的数学模型与算法研究
- 格式:pdf
- 大小:355.42 KB
- 文档页数:4
城市交通运输规划中的模型与算法研究随着城市化进程的加速,城市交通问题日益突出,如何高效地规划和优化城市交通运输系统成为当前需要解决的问题。
而在城市交通规划中,模型与算法的研究显得尤为重要。
一、模型研究城市交通规划中需要建立一些数学模型来解决当下城市交通面临的问题。
这些模型可以反映出交通系统的运行状况,先进的模型将会逐渐替代传统的手工编制方法,减少人工干预。
常见的模型有以下几种:1.交通流模型交通流模型是一种动态模型,它可以用来模拟车辆在路网上的运行流程。
交通流模型不仅可以反映季节变化等交通特征,还可以模拟紧急情况下的路况变化,为交通规划提供指导。
2.路线选择模型路线选择模型是一种静态模型,它可以用来预测不同用户在不同时间段内选择路线的情况,并为城市交通规划提供可行性分析。
3.化规模模型化规模模型可以将城市交通规划的复杂性转化为一个简单的问题,计算系统可以在实时模式下自动优化城市交通系统。
二、算法研究模型的研究只是建立一个良好的框架,而算法则是实现这个框架的基础。
在城市交通规划中,常用的算法有以下几种:1.模拟退火算法模拟退火算法是一种基于随机模拟的全局优化算法,目的是将系统的能量降至最低。
在城市交通规划中,模拟退火算法被广泛应用于路线优化。
2.遗传算法遗传算法是一种基于进化论的算法,它通过模拟生物适应性来寻找最优解。
在城市交通规划中,遗传算法被广泛应用于个体和社会交通系统的优化。
3.模糊逻辑算法模糊逻辑算法是一种用于处理模糊性问题的算法,它可以直接处理交通系统中具有不确定性的现象,提高交通流量和效率。
在城市交通规划中,模糊逻辑也被广泛应用。
三、模型与算法的应用传统的城市交通规划方法通常依赖于人工经验,这种方法有时不仅效率低下,而且容易出错。
而在模型与算法的基础上,城市交通规划不仅可以建立更精确的定量分析模型,还可以通过模拟操作提前预测问题并提前发现潜在的风险。
在大多数交通规划中,交通容量的分配是一个关键问题。
长安大学硕士学位论文
图2.1机载GPS单点定位
知数,所以要实现绝对定位,必须同时观测和得到四颗导航卫星的伪距观测值。
GPS绝对定位在空问和时间上是独立的,它的每一次定位代表了该测点在该时刻的位置,与其他测点和其它时刻无关,并且绝对定位是指提供定位信息的唯一性,而不是指固定不动的。
利用这一特点将接收机安装在运动目标上,就可以测出运动目标的瞬时位置和运动速度,所以利用GPS技术就可以解决运动目标的定位和导航问题。
2.2.2GPs动态相对定位
利用GPS进行绝对定位(或单点定位)时,其定位精度,将受到卫星轨道误差、钟差及信号传播误差等诸多因素的影响,尽管其中一些系统性误差,可以通过模型加以削弱,但其残差仍是不可忽略的。
实践表明,目前静态绝对定位精度,约可达米级。
而动态绝对定位精度仅为lOm~40m.这一精度远不能满足目前静态和动态用户的要求。
GPS相对定位,也叫差分GPS定位,是目前GPS定位中精度最高的一种定位方法,它广泛地应用于大地测量、精密工程测量、地球动力学的研究和精密导航等领域。
GPS动态相对定位,是指将一台接收机安设在一个固定基准站上,而另一台接收机安置在运动的载体上,并且在运动中,与固定基准站的接收机进行同步观测,以确定运动载体相对固定基准站的瞬时位置。
若基准站坐标已知,则可实时地确定运动点相应于每一观测历元的瞬时位置。
测码伪距动态相对定位法,。
轨迹数据挖掘算法在交通出行分析中的应用研究近年来,随着智能手机和定位技术的普及,轨迹数据挖掘算法在交通出行分析中的应用呈现出越来越广阔的前景。
轨迹数据是通过收集个体在空间和时间上的运动信息获得的,它可以包含有关个体的行为、偏好以及交通规律等重要信息。
通过挖掘和分析这些轨迹数据,我们可以深入了解交通出行过程中的行为模式、结构特征和运动规律,从而为交通规划、交通管理和出行模式优化提供科学依据和参考。
首先,轨迹数据挖掘算法在交通出行分析中能够帮助我们发现和识别出行行为模式。
通过对轨迹数据进行聚类和分类分析,可以将人群划分为不同的出行群体,如通勤者、学生群体、休闲出行者等等。
这些分类信息可以帮助我们了解不同群体的出行偏好、出行节奏以及出行时间分布等,为交通规划和出行模式优化提供参考。
同时,轨迹数据挖掘还可以揭示出行行为模式的变化趋势,如节假日和工作日出行模式的差异等。
这些信息对于交通管理部门合理调配交通资源、疏导交通流量具有重要意义。
其次,轨迹数据挖掘算法在交通出行分析中能够帮助我们揭示交通网络的结构特征。
通过对轨迹数据进行网络分析,我们可以建立出行网络图,揭示道路节点的连通性、网络拓扑结构以及网络中的关键节点和关键路径,这对于评估交通网络的韧性和可靠性具有重要价值。
此外,通过挖掘轨迹数据中的路线选择信息,可以了解交通网络中的主要流量通道以及拥堵点,为交通规划和道路改进提供有益参考。
这些结构特征的分析可以帮助我们更好地理解交通网络的运行机制,从而提高交通系统的运输效率和交通出行的便利性。
第三,轨迹数据挖掘算法在交通出行分析中能够帮助我们发现交通规律和行为特征。
通过对轨迹数据进行时间序列分析,我们可以揭示不同时间段交通流量的变化趋势和规律,如高峰期、低谷期以及交通拥堵程度的变化等。
这些规律信息对于交通管理部门制定交通管控策略、合理规划道路和交通设施具有重要意义。
同时,轨迹数据挖掘还可以揭示驾驶行为特征,如平均速度、刹车次数、加速度等,这些信息对于交通行为研究和交通安全改进具有重要价值。
轨道交通信号与控制的智能算法研究在现代社会,轨道交通作为一种高效、安全、环保的交通方式,在人们的日常出行和城市发展中发挥着至关重要的作用。
而轨道交通信号与控制技术则是保障轨道交通系统安全、高效运行的关键。
随着科技的不断进步,智能算法在轨道交通信号与控制领域的应用日益广泛,为提高轨道交通的运行效率和服务质量带来了新的机遇和挑战。
一、轨道交通信号与控制的重要性轨道交通系统的运行涉及到列车的运行调度、信号的传输与处理、轨道的维护与管理等多个方面。
其中,信号与控制技术起着“指挥中枢”的作用,它决定了列车的运行速度、运行间隔、停靠站点等关键参数,直接影响着轨道交通系统的运行效率、安全性和可靠性。
例如,在城市地铁系统中,如果信号与控制技术出现故障,可能会导致列车晚点、停运,甚至发生追尾等严重事故,给乘客的出行带来极大不便,同时也会对城市的交通秩序造成严重影响。
因此,不断优化和改进轨道交通信号与控制技术,对于提高轨道交通系统的整体性能具有重要意义。
二、智能算法在轨道交通信号与控制中的应用1、模糊逻辑算法模糊逻辑算法是一种基于模糊集合理论的智能算法,它能够处理具有不确定性和模糊性的信息。
在轨道交通信号与控制中,模糊逻辑算法可以用于列车的自动驾驶系统,根据列车的运行状态、线路条件、客流量等因素,自动调整列车的运行速度和加速度,实现列车的平稳运行和节能控制。
例如,当列车接近弯道时,模糊逻辑算法可以根据弯道的曲率半径、列车的速度等因素,自动调整列车的加速度,使列车在弯道上保持稳定的运行状态。
此外,模糊逻辑算法还可以用于轨道交通信号系统的故障诊断和预警,通过对信号设备的运行数据进行分析,及时发现潜在的故障隐患,提高信号系统的可靠性。
2、遗传算法遗传算法是一种基于生物进化原理的智能算法,它通过模拟自然选择和遗传变异的过程,来寻找最优解。
在轨道交通信号与控制中,遗传算法可以用于列车运行图的优化编制,根据客流量、列车的运行速度、停靠站点等因素,制定出最优的列车运行计划,提高列车的运行效率和服务质量。
智能交通领域的数据挖掘与建模技术研究一、引言智能交通系统拥有处理海量数据的能力,人们可通过该系统根据交通运输情况作出正确决策,提高车辆行驶效率,减少拥堵、安全隐患等问题。
数据挖掘和建模技术是智能交通领域中非常重要的研究内容。
本文主要介绍智能交通领域的数据挖掘和建模技术,并结合案例进行分析。
二、智能交通领域的数据挖掘技术数据挖掘是对大数据进行分析和加工,提取有用信息的技术。
智能交通系统中的数据挖掘主要是从各种设备如路况探测器、智能识别系统、GPS 等设备获取数据,进行数据预处理、数据集成、数据清理、数据变换、数据挖掘和模型评价等步骤。
1.数据预处理数据预处理是数据挖掘的首要任务,其目的是去除不准确、冗余、丢失等错误数据,确保后续挖掘的准确性。
在智能交通领域,数据预处理包括数据采集、数据清洗、数据集成和数据标准化等步骤。
2.数据变换数据变换是指将多源、异构、不一致的数据转换为可处理的格式。
在智能交通领域中,由于数据来源的差异,数据类型和格式存在较大差异,因此数据变换是至关重要的。
常见的数据变换方式包括数据重构、数据转化和数据集成等。
3.数据挖掘数据挖掘是通过分析数据中未知的、有用的、潜在的信息来对未来的事件进行预测和决策。
智能交通领域中的数据挖掘通常是基于分类、聚类、关联规则挖掘等方式进行的。
4.模型评价模型评价是模型建立后,确定模型的精确性、可靠性和适应性。
在智能交通领域中的模型评价通常是使用交叉验证、ROC 曲线、混淆矩阵等方法进行评估。
三、智能交通领域的建模技术智能交通领域的建模技术,是根据已有的数据,依据统计学原理和机器学习算法,构建性质模型,对新数据进行预测和分析。
智能交通领域的建模技术包括监督学习、非监督学习和半监督学习三种方式。
1.监督学习监督学习是指在已有标注数据的情况下,根据已有数据训练模型,并通过新数据的标签进行验证和预测。
在智能交通领域中,监督学习可以通过分类、回归、关联和序列预测等方式实现。
智能交通中的数据挖掘与建模研究智能交通是一个以人类交通需求和行为为核心的研究领域,它是一种基于信息技术、通信技术、传感器技术等,对交通流、交通行为进行智能化处理,提高道路使用效率、建立智能交通系统和交通安全保障的概念。
在这个领域,数据挖掘和建模是一个非常重要的技术,其目的是为了发掘、分析和理解交通数据的内在规律,从而为基于数据的决策和预测提供支持。
本文将从智能交通数据的来源、挖掘和建模的研究现状以及在实际应用中的应用等方面进行阐述。
一、智能交通数据的来源智能交通的数据来源主要包括道路监控、移动通信技术、数字地图、传感器技术等,其中,道路监控数据是智能交通数据的主要来源之一。
道路监控设备种类繁多,如路面传感器、视频监控、雷达监控、交通信号灯,以及卫星定位等,这些设备对实时道路状况的捕捉和记录,为智能交通管理系统提供了大量的有价值的数据。
另外,移动通信技术也为智能交通数据的收集提供了巨大的便利。
手机定位、蓝牙等技术的不断发展,使得大量移动终端设备不断生成各种交通数据,如轨迹数据、车速数据、行程数据等,这些数据包含了大量有价值的交通信息,为智能交通的研究者提供了广泛的研究空间。
数字地图作为交通领域的重要基础设施,其数据也成为智能交通数据的重要来源之一。
数字地图涵盖了交通路网、交通设施、车辆信息等各类交通信息,这些信息为智能交通研究者的分析和建模提供了快捷、准确的基础。
二、智能交通数据挖掘和建模的研究现状智能交通数据挖掘和建模的研究一方面注重发掘交通数据的内在规律,提取有价值的信息,另一方面则对交通数据进行建模并进行预测和优化,以提高交通运行效率和安全性。
这里我们对该领域研究现状进行分析。
交通流量预测是数据挖掘和建模的重要应用之一。
预测交通流量可以提高交通运行效率和交通安全性,减少交通拥堵和事故的发生。
当前,交通流量预测主要有基于数据挖掘的方法和基于机器学习的方法。
基于数据挖掘的方法主要是通过分析历史数据,挖掘交通数据的规律性,从而对未来的交通流量进行预测。
GPS技术在城市轨道测量方法与应用随着城市轨道交通系统的不断发展,对城市轨道的测量和定位要求也越来越高。
而全球定位系统(GPS)技术为城市轨道的测量和定位提供了有效的方法和工具。
GPS是由美国发起,由全球多颗卫星、地面差分站台、用户接收机等组成的一种导航与定位系统。
它通过测量卫星与接收机之间的距离,利用三角定位原理计算出接收机的坐标。
GPS技术具有高精度、高效率、无需人工干预等特点,因此在城市轨道测量中应用广泛。
首先,GPS技术可以用于城市轨道的高程测量。
城市轨道的高度是影响轨道线路设计和运营的重要参数,而传统的高程测量方法通常需要大量的人力、物力和时间,工作效率低下。
而GPS技术可以通过接收机直接获取地面高程,减少了测量人员和设备的需求,提高了高程测量的效率和准确度。
其次,GPS技术可以用于城市轨道的水平测量。
城市轨道的水平坐标是轨道线路设计、施工和维护的关键信息,而传统的水平测量方法通常需要进行复杂的坐标计算,且易受到人为误差和地形限制。
而GPS技术可以通过接收机获取卫星信号,实时计算出测量点的水平坐标,减少了测量误差和依赖地形的限制。
此外,GPS技术还可以用于城市轨道的线路布设和监测。
在轨道线路布设过程中,GPS技术可以通过接收机的位置信息,提供给施工人员线路的位置和方向,实现轨道线路的准确布设。
在轨道线路的运营过程中,GPS技术可以实时监测轨道的位移和变形,提供给维护人员及时修复和调整轨道线路,保障运营安全和稳定。
另外,GPS技术还可以应用于城市轨道的列车运行控制和调度。
在城市轨道运营中,列车的运行控制和调度是关键环节,而GPS技术可以通过定位和导航功能,实时提供列车的位置、速度和方向等信息,帮助调度员准确掌握运行状况和调度列车的优化路径,提高运行效率和安全性。
综上所述,GPS技术在城市轨道测量中的应用具有重要意义。
它可以提高测量的效率和准确度,减少人力和资源的浪费,为城市轨道的设计、施工、维护和运营提供可靠的技术支持。
轨迹数据挖掘算法在城市交通流分析中的应用研究城市交通流是一个非常复杂的系统,其中包括各种交通方式的运动和交叉,涉及到许多不同的因素,如道路状况、交通信号灯、天气情况等等。
因此,对城市交通流进行分析和优化是非常重要的。
近年来,随着移动设备的广泛普及,人们的日常移动轨迹数据成为了一种有价值的资源,通过对这些数据进行挖掘和分析,可以帮助我们更好地了解城市交通流的运行和优化。
轨迹数据挖掘是一种从空间和时间上对移动对象轨迹数据进行分析的方法。
它可以通过对轨迹数据的分析,揭示出移动对象的移动规律和行为模式,从而为城市交通流的研究提供更加准确和完整的数据支持。
例如,通过对汽车、公交车等交通工具的移动轨迹数据进行分析,可以帮助我们了解道路拥堵状况、交通流量分布、车流速度等信息,从而指导城市交通规划和道路建设。
在轨迹数据挖掘算法中,有许多常用的方法,如基于聚类的轨迹分段方法、基于时间空间笛卡尔积的轨迹匹配方法、基于距离度量的轨迹相似性匹配方法等等。
这些方法都可以通过对轨迹数据进行分析和处理,提取出有用的信息并形成可视化的结果,为城市交通流分析提供更加有效的手段。
基于轨迹数据挖掘算法的城市交通流分析可以涵盖多个方面。
其中,最为重要的是道路网络和交通模型的分析。
通过对移动对象轨迹数据的采集和分析,我们可以了解到不同道路段的拥堵程度、车辆通过路口的时间和车速等信息,这些信息可以被用来构建道路网络和交通模型,进而为城市交通规划和道路设计提供重要参考。
此外,基于轨迹数据挖掘算法,我们还可以对城市交通流进行行为分析。
例如,我们可以从轨迹数据中挖掘出不同交通工具的出行行为习惯,如不同时间段内的通勤方式、交通工具选择偏好等信息,从而帮助交通管理部门更好地规划和优化城市交通流。
综上所述,基于轨迹数据挖掘算法的城市交通流分析是一个非常有价值和有前景的研究领域。
随着移动设备的普及和轨迹数据的不断采集,我们相信这个研究领域会越来越受到重视,同时也会为城市交通流的分析和优化带来越来越多的成果和改善。
第30卷第4期铁 道 学 报Vol.30 No.4 2008年8月J OURNAL OF T H E CHINA RA IL WA Y SOCIET Y August2008文章编号:100128360(2008)0420116204轨道交通GPS数据约简的数学模型与算法研究陈德旺, 蔡伯根, 王 剑, 唐 涛(北京交通大学轨道交通控制与安全国家重点实验室,北京 100044)摘 要:利用实测轨道GPS数据生成电子地图是实现列控智能化的一个重要环节。
为减少存储空间和提高列车定位的实时性,需要对大量GPS数据进行约简,找出其中的少量关键数据。
通过数学建模和分析,轨道交通GPS数据约简问题是一个N P问题,难以求得最优解。
本文提出一种启发式线性算法,并给出6个性能指标的定义。
两个铁路区间的实测GPS数据用于对算法的性能指标进行分析比较。
计算结果表明,该算法是有效的且运行速度较快。
该算法能以较低的约简率在一定误差要求的前提下约简大量GPS数据。
在误差约束为1m时,约简率小于2%;误差约束为2m时,约简率约为1%。
随着轨道弯曲程度的增加,约简率有所增加。
关键词:轨道交通;全球定位系统;电子地图;数据约简;启发式算法中图分类号:U284 文献标志码:AMathem atical Model and Algorithm of DataR eduction for R ail w ay GPS DataC H EN De2wang, CA I Bai2gen, WAN G Jian, TAN G Tao(State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University,Beijing100044,China)Abstract:Utilization of huge data of railway GPS(Global Po sition System)to generate an elect ronic map is an improtant step to realize t he intelligent train cont rol.To decrease t he memory space and enhance t he real2time p roperty of t rain po sitioning,it is necessary to find an effective data reduction algorit hm for huge GPS data. Modeling and analysis indicate t hat t he p roblem of railway GPS data reduction is a N P p roblem and it is hard to get t he optimal solution.A heuristic algorit hm was p ut forward and6performance indexes were defined in t his paper.The surveyed GPS data of two railway sections were used to analyze t he performance index of t he algo2 rit hm.The comp utational result s show t hat t he algorit hm is effective and t he running speed of t he algorit hm is very high.The algorit hm can reduce t he huge GPS data in a very low reduction rate under certain error require2 ment.When t he error requirement is1m,t he reduction rate is less t han2%;when t he error requirement is2 m,t he reduction rate is about1%.Wit h t he increase of t he camber of railway,t he reduction rate increases. K ey w ords:rail traffic;GPS;electronic map;data reduction;heuristic algorit hm 全球定位系统GPS在城市车辆、飞机、船舶导航、大地测量、地图绘制和火箭导弹监控等众多领域得到广泛应用[1]。
同样,在铁路勘测、定位和监控方面有着好的发展前景[2,3]。
目前欧洲各国铁路正在加强利用GPS技术,沿相应线路设置差分基站,并使之与移动通信技术结合,以提高铁路的通过能力和可靠性[4]。
收稿日期:2006211227;修回日期:2007204223基金项目:国家自然科学基金面上项目(60776833);国家自然科学基金重点项目(60634010);轨道交通控制与安全国家重点实验室(北京交通大学)开放基金项目(SK L2007K005)作者简介:陈德旺(1976─),男,安徽南陵人,副教授,博士。
E2m ail:dwchen@ 列车调度指挥智能化是铁路运输现代化的重要标志[5]。
实现列车的智能化调度和监控,可消除行车安全隐患,提高运行效率。
精确的电子地图是列车智能化调度和监控的重要环节[6]。
铁路传统的测量方法难以获取电子地图所需的大量基础数据。
采用GPS测量操作简便、进度快,可极大提高工作效率[7]。
在获取大量轨道GPS数据之后,一个重要问题是采用有效的约简算法简单高效地表示轨道,以减少存储空间和提高电子地图匹配效率,同时要把误差控制在允许范围内。
轨道可分为直线轨道和曲线轨道,直线轨道表示相对简单,曲线轨道在电子地图上的表示方法则是一个难点。
目前常用方法有NU RBS 表示[8]、B ézier 曲线表示等[9,10]。
这类曲线表示方法会导致数据存储量增大,尤其是相应的地图匹配算法复杂。
实际的曲线铁轨是渐近线形状,曲率半径比较大。
文献[6]发现,只要取较少的点就可把分段直线替代曲线轨道的误差控制在一定范围内。
本文提出可在轨道上依次取点,用顺次相连的折线近似代表曲线轨道。
用折线表示轨道形成的误差有两种:横向误差和纵向误差。
横向误差为折线偏离轨道的最大正交投影距离;纵向误差即轨道长度与折线长度之差。
本文推导了数据约简的组合数学模型,提出一种启发式算法,并以铁路实测的GPS 数据对算法性能进行分析和比较。
1 数据描述和数学模型1.1 数据描述本文所用的数据是青藏铁路的实测GPS 数据,是用差分GPS 技术测量,精度为cm 级。
本文选取其中的两个区间数据对算法效果进行验证,其中区间1有9935组数据,区间2有8452组数据。
前后两测点间距离为1.5m ~3m ,平均距离为2m ,每个区间长约20km 。
为慎重起见,先将GPS 经纬度数据转化为X Y坐标,同时将区间的起点转化为坐标原点,如图1和图2所示。
对于约简算法而言,同时控制两个误差指标比较困难,本文以横向误差为约束条件,再去检验纵向误差。
复线区段上下行线路中心线之间和车站内相邻股道之间的距离约为5m 。
对于横向误差约束,分别设为1m 和2m 。
这显然可以区分出上下行列车轨道;同样也可以区分开车站内不同股道。
1.2 数学模型轨道交通GPS 数据约简,其实就是在所测数据集中选择最少的关键数据点,构成顺次相连的折线,并使得每个实测数据到相应分段上的最大正交距离不超过设定的横向误差约束。
本文利用组合优化理论[11]推导了数学模型描述该问题:min6ni =1z i (1)z i ∈(0,1),Πi =1,2,…,n(2)z 1=1 z n =1(3)Πd i ,j ≤E(4)式中,所有数据点的个数为n ,设定的横向误差约束为E 。
约束条件式(2)表示在这n 个数据点中,如果第i个点被选中,则z i =1,否则为0。
约束条件式(3)表示分段直线第一段的起点是该数据集的起点;分段直线最后一段的终点是数据集的终点。
所以数据集中还有n -2个点可以被选为分段点。
约束条件式(4)表示实测数据到相应分段直线的正交距离不超过设定的横向误差,d i ,j 表示分段点i 与下一分段点j 之间的点到这两点连线间的正交距离。
该组合问题共有2n -2种可能的解。
实际中,一般以一个铁路区间的GPS 数据为一个基本单元进行约简,n 约为8000。
由于点到直线的投影距离公式是非线性的,并且求最大投影距离不超过设定横向误差的约束条件也是非线性的,所以该问题是一个分段非线性的组合问题。
不难看出,该问题是一个大规模的N P 完全问题,在有限的时间内难以求得最优解,必须结合工程实际寻求较优解。
2 算法和性能指标2.1 启发式算法该算法的基本思想是“步步为营,不能进则退”。
具体来说,从起点开始试探下一个假设终点,能前进(误差满足要求)尽可能地前进,不能进则退后一步;找到下一个终点后,再以该终点为起点,寻找下下个终点;如此循环直到所有数据点都包括在各分段中。
显然,该算法是一个简单实用的局部优化的启发式算法。
算法的步骤为:711第4期轨道交通GPS 数据约简的数学模型与算法研究 第1步 将区间起点设为起始点,作为所有分段中的起始点,i=1。
第2步 从起点i开始,以该点之后的第2个点(i+2)为假设终点。
第3步 将起点和假设终点连接成直线。
如果起点和终点的X坐标相等,直线斜率为无穷大,则用式( 5)计算正交距离,其中的x是起点或者终点的X坐标;否则,求出该直线的斜率k和截距b,利用点到直线距离公式,计算起点和假设终点之间的数据点x i到该直线的正交距离,如式(6)所示。
d i=|x i-x|(5)d i=|kx i+b-y i|k2+1(6) 第4步 求这些正交距离中的最大值D maxD max=max{d i}(7) 第5步 如果D max小于设定的横向误差E,则假设终点向前方(从起点到终点的方向为前方)移动一个点,回到第3步。
第6步 如果D max大于E,则当前终点为所假设终点的前面一点,并将新的起点设为当前终点,回到第2步继续找下一个终点。
第7步 直到所有的点都在包括各分段之中。
从算法的过程看,该算法是一个线性算法,算法的效率取决于数据集合的规模。
2.2 算法性能指标在满足横向误差约束时,算法的性能指标有:(1)分段数m:分段直线的总数,越少越好。