一种公务车辆监管中位置预警的方法

摘要

本发明一种公务车辆监管中位置预警的方法，通过缓冲半径分别绕组成目标对象的各点旋转生成目标缓冲区边界，能够根据预先设定的预警类别和缓冲半径，准确生成对应的敏感地点缓冲区、规定线路缓冲区、电子围栏缓冲区，本发明解决了规定线路缓冲区或电子围栏缓冲区边界线的失真现象；处理了规定线路缓冲区或电子围栏缓冲区边界线的自相交问题，本发明创造性地将缓冲区算法和单调链算法相结合，只需得到敏感地点、规定线路、电子围栏这三者对应的坐标集和缓冲半径，即可构造缓冲区域，进而判断公务车辆位置与这三者的空间关系，最终产生预警，具有极强的操作性。

说明书

技术领域

本发明涉及地理信息系统（GIS）和公务车辆监管领域，尤其涉 及一种公务车辆监管中位置预警的方法，具体的说是一种利用缓冲区 分析生成算法和单调链报警算法来进行空间判定的公务车辆位置预 警的方法。

背景技术

目前，我国正在建设节约型和谐社会，也要求政府职能部门必须 加强自身的管理，而公务车辆监管就是其中非常重要的一部分。公务 车辆监管中涉及到位置预警的关键技术难点是：如何准确判定公务车 辆是否到达敏感地点、偏离规定线路以及出入电子围栏，并能及时产 生预警信息。

当前，缓冲区作为空间分析的重要方法，在许多领域均有应用， 但在准确性上还存在一些不足。其中，缓冲区分析的传统算法主要有 两种，一是角平分线算法，二是凸角圆弧算法，它们在生成缓冲时都 有欠缺，存在边界失真的现象，特别在处理缓冲区边界的自相交问题 时准确性不够，不能满足公务车辆监管中的实际需求。

发明内容

本发明的目的在于提供一种公务车辆监管中位置预警的方法，采 用简化的数据结构，不仅节省了大量的存储空间，而且大大节省了运 算时间，保证了公车监管中位置预警的实时性要求。

一种公务车辆监管中位置预警的方法，包括以下步骤：

步骤1、使用缓冲区分析生成算法，根据预警类别和缓冲半径， 生成敏感地点缓冲区、规定线路缓冲区、电子围栏缓冲区；

步骤2、使用单调链报警算法，用于判别通过GNSS获取的公务 车辆当前位置点与已生成的敏感地点缓冲区、规定线路缓冲区、电子 围栏缓冲区的空间关系，并根据预设的报警规则进行报警。

所述的步骤1中生成敏感地点缓冲区、规定线路缓冲区和电子围 栏缓冲区的做法是：

（1）设敏感地点的坐标点为A，在A点所在平面上任取一点B， 连接A、B两点作为缓冲半径r，设缓冲半径r绕A点沿着顺时针方 向到X轴形成的角度为α，圆心A(x,y)，缓冲半径r绕A点逆时针 旋转角度β，生成点坐标A’(x’,y’)，

其中x’=x+Υ₁*sin(α+β)

y’=y+Υ₁*cos(α+β)

β=0,Υ₁,2Υ₁,….,(n-1)Υ₁,Υ₁＝2π/n，n为由正多边形的边 数，即可得到敏感地点缓冲区边界的内接正n边形的各顶点坐标；

（2）设规定线路的坐标集构成目标线，首先生成目标线上第一 个坐标点的右侧区域，连接第一个点与下一个点构成直线，根据点缓 冲区分析生成算法，角α从π开始，根据Υ₂=π/6逆时针递增取点 （π,π+Υ₂,π+2Υ₂…）,直到α=3π/2，共生成4个坐标点；

其次生成目标线上第k个拐点B的区域，判断拐点B的凹凸性； 根据目标线方向取第k-1个点A，k+1个点C，分别连接A、B和B、C 生成直线AB、BC；设AB、BC的叉积为L，由矢量代数的右手法则， 计算L：若L>0，A、B、C为逆时针方向，拐点B为凸点；若L<0，A、 B、C顺时针方向，拐点B为凹点；若L=0，A、B、C三点共线；设BC 与X正半轴的夹角为α，AB与BC的夹角为β，若拐点为凸点，则把 步骤（1）中的角α改为从θ=α+3π/2-β开始，其他的如步骤（1） 算法生成顶点坐标；若拐点为凹点，则对应的缓冲点为AB、BC的平 行上移的形成的凸交点；

然后生成目标线上末端点的右侧区域，连接末端点和目标线上的 倒数第二点构成直线AB，其缓冲点的生成方法如步骤（1）；

若是左侧区域生成，参照如上关于右侧区域分析生成算法的步 骤，不同之处在于应从目标线上的最后一点开始；

（3）电子围栏的坐标集构成目标面，当目标对象是面时，则把 面的外围多边形作为一条闭合的线，再用步骤（2）中的规定线路缓 冲区的生成方法实现。

所述的解决规定线路缓冲区或电子围栏缓冲区边界线的失真现 象的做法是：

（41）将上述生成的规定线路缓冲区或电子围栏缓冲区称为初始 化缓冲区，如果轴线上当前节点，即转折点处该侧的角为凹角，计算 其夹角α，该节点相邻两条边为r1、r2，上一节点与当前节点之间 的距离为r1边的距离，设为|r1|，当前节点与下一节点之间的距离 为r2边的距离，设为|r2|，|r1|、|r2|分别与夹角α的一半的正切 值的乘积为|r1|tanα/2、|r2|tanα/2；当|r1|tanα/2<r<= |r2|tanα/2，视为无失真，但出现了凹陷现象，故需截去处于平行 线下的缓冲点及其相关凹陷线段，平行连接平行线被截去的线段，处 理失真步骤结束；当r>|r1|tanα/2，产生失真现象，进入步骤（42）；

（42）、根据当前坐标点及其前后坐标点的凹凸性创建链表，点 k-1为点k的前一个坐标点,若点k-1为凸角，取点k-1的对应点集 中的第一个点，所述的点k-1的对应点集是以点k-1为圆心，以缓冲 半径r为半径，以点k到点k-1节点方向为0度方向，逆时针旋转 90°所形成的1/4圆弧上的所有点；若点k-1为凹角，取点k-2的对 应点集中的最后一个坐标点；该点k+1为点k的后一个坐标点，若点 k+1为凸角，取点k+1的对应点集中的第一个坐标点；若点k+1为凹 角，取点k+2的对应点集中的最后一个坐标点，把这些坐标点按目标 线的线路方向顺序插入链表中，形成修改过的坐标点序列表；

（43）、删除初始化缓冲区边界上的失真坐标点，该初始化缓冲 区为直接生成、未进行特殊处理的缓冲区结果，此时对应的也是失真 的坐标点序列表，然后使用步骤（42）中修改过的坐标点序列表替换 失真的坐标点序列表。

所述的处理规定线路缓冲区或电子围栏缓冲区边界线自相交的 做法是：

（51）逐步判断规定线路缓冲区或电子围栏缓冲区边界上各个线 段是否相交，首末线段、相邻线段除外；

（52）如果相交，则记录所有的自相交点；

（53）定义两个动态数组，一个用于存储缓冲区边界多边形有序 结点坐标的动态数组Array1和另一个用于存储所有自相交多边形有 序结点坐标的动态数组Array2；

（54）将以上产生的缓冲区边界多边形的各结点按生成顺序存入 数组Array1中；

（55）应用递归方法求取所有自相交多边形并存入数组Array2 中；

（56）再采用面积的定积分的近似算法，判断数组Array2中自 相交多边形的方向，如果是顺时针方向，则是缓冲区边界多边形的内 环；如果是逆时针方向，则面积绝对值最大的多边形是缓冲区边界多 边形的外环，而其它逆时针方向的多边形不是缓冲区的组成部分；

（57）连接所有求得的缓冲区交点，即得到边界结果。

所述的步骤2的具体做法是：

（1）创建链表

采用单链表来表示目标多边形和参照多边形,单链表的每一个结 点按顶点输入的顺序存储多边形的一个顶点，最后一个结点的指针指 向第一个结点，每个链表由一个头指针指向第一个结点，采用上述数 据结构创建目标多边形和参照多边形链表，判断并计算第一个交点；

（2）计算交点

运用解析几何计算目标多边形中的每条边所在直线和参照多边 形中的任意边所在直线，按直线一般方程求两条线段的交点，并判断 交点坐标是否为实际交点；

若为实际交点，则把该交点以其在目标多边形上的先后顺序，按 多边形路线方向插入到两个多边形的链表中；若出现经过交点的线段 经过多边形顶点的情况，在求出交点后，不再将相同交点插入到链表 中；若出现经过交点的线段与参照多边形的某一边重叠的情况，忽略 该重叠的参照边，只对重合边以外的多边形的边求交；

（3）遍历链表

遍历步骤（1）创建的目标多边形和参照多边形链表，如果存在 交点，则可以判断位置点在缓冲区内；

（4）根据以下预设的报警规则，来产生预警信息：

（41）、到达敏感地点的报警规则：位置点在缓冲区内；

（42）、偏离规定线路的报警规则：位置点在缓冲区外；

（43）、出入电子围栏的报警规则：位置点由缓冲区内变为缓冲 区外、或由缓冲区外变为缓冲区内。

本发明公开了一种公务车辆监管中位置预警的方法，提出了一种 新的缓冲区分析生成算法，解决了传统算法中存在的缺陷，简化了公 务车辆监管中敏感地点缓冲区、规定线路缓冲区、电子围栏缓冲区的 生成过程，在一定程度上解决了边界失真现象，而且能更准确处理缓 冲区自相交问题；基于已生成的缓冲区，提出了一种单调链报警算法， 用于判别通过GNSS获取的公务车辆当前位置点与已生成的敏感地点 缓冲区、规定线路缓冲区、电子围栏缓冲区的空间关系，以达到准确 预警的目的。

附图说明

图1为本发明中敏感地点缓冲区生成过程示意图；

图2为本发明中规定线路缓冲区生成过程示意图；

图3为本发明中规定线路缓冲区的边界自相交解决效果示意图；

图4-1为本发明单调链报警算法涉及的交点情况之一；

图4-2为本发明单调链报警算法涉及的交点情况之二；

图4-3为本发明单调链报警算法涉及的交点情况之三。

以下结合附图和具体实施例对本发明作进一步详述。

具体实施方式

一种公务车辆监管中位置预警的方法，包括以下步骤：

步骤1、使用缓冲区分析生成算法，根据预警类别和缓冲半径， 生成敏感地点缓冲区、规定线路缓冲区、电子围栏缓冲区：

（1）敏感地点缓冲区的生成：

如图1所示，敏感地点的坐标点为A，算法的结果是要生成坐标 点A的缓冲区。

在A点所在平面上任取一点B，连接A、B两点作为缓冲半径r， 设缓冲半径r绕A点沿着顺时针方向到X轴形成的角度为α，圆心 A(x,y)，缓冲半径r绕A点逆时针旋转角度β，生成点坐标 A’(x’,y’)，

其中x’=x+Υ₁*sin(α+β)

y’=y+Υ₁*cos(α+β)

β=0,Υ₁,2Υ₁,….,(n-1)Υ₁,Υ₁＝2π/n，n为由正多边形的边 数，即可得到敏感地点缓冲区边界的内接正n边形的各顶点坐标；

（2）规定线路缓冲区的生成：

如图2所示，规定线路的坐标集构成目标线，算法的结果是要生 成目标线的缓冲区。

首先生成目标线上第一个坐标点的右侧区域，连接第一个点与下 一个点构成直线，根据点缓冲区分析生成算法，角α从π开始，根 据Υ₂=π/6逆时针递增取点（π,π+Υ₂,π+2Υ₂…）,直到α=3π/2， 共生成4个坐标点；

其次生成目标线上第k个拐点B的区域，判断拐点B的凹凸性。 根据目标线方向取第k-1个点A，k+1个点C，分别连接A、B和B、C 生成直线AB、BC；设AB、BC的叉积为L，由矢量代数的右手法则， 计算L：若L>0，A、B、C为逆时针方向，拐点B为凸点；若L<0，A、 B、C顺时针方向，拐点B为凹点；若L=0，A、B、C三点共线。设BC 与X正半轴的夹角为α，AB与BC的夹角为β，若拐点为凸点，则把 步骤（1）中的角α改为从θ=α+3π/2-β开始，其他的如步骤（1） 算法生成顶点坐标；若拐点为凹点，则对应的缓冲点为AB、BC的平 行上移的形成的凸交点；

然后生成目标线上末端点的右侧区域，连接末端点和目标线上的 倒数第二点构成直线AB，其缓冲点的生成方法如步骤（1）；

若是左侧区域生成，参照如上关于右侧区域分析生成算法的步 骤，不同之处在于应从目标线上的最后一点开始；

（3）电子围栏缓冲区的生成：

电子围栏的坐标集构成目标面，算法的结果是要生成目标面的缓 冲区。

当目标对象是面时，则把面的外围，也就是外围多边形作为一条 闭合的线，再用步骤（2）中的规定线路缓冲区的生成方法实现；

（4）解决规定线路缓冲区或电子围栏缓冲区边界线的失真现象。 我们将步骤（2）和（3）中直接生成的缓冲区称为初始化缓冲区。由 于失真现象只会在目标线上的凹侧产生，故通过如下步骤处理相应的 失真现象：

（41）、如果轴线上当前节点（转折点）处该侧的角为凹角，计 算其夹角α，该节点相邻两条边为r1、r2，上一节点与当前节点之 间的距离，为r1边的距离，设为|r1|，当前节点与下一节点之间的 距离，为r2边的距离，设为|r2|，|r1|、|r2|分别与夹角α的一半 的正切值的乘积为|r1|tanα/2、|r2|tanα/2；当|r1|tanα/2<r <=|r2|tanα/2，无失真，但出现了凹陷现象，故需截去处于平行线 下的缓冲点及其相关凹陷线段，平行连接平行线被截去的线段，处理 失真步骤结束；当r>|r1|tanα/2，产生失真现象，进入步骤（42）；

（42）、根据当前坐标点及其前后坐标点的凹凸性创建链表。点 k-1为点k的前一个坐标点,如点k-1为凸角，取点k-1的对应点集 中的第一个点，所述点k-1的的对应点集指的是以点k-1为圆心，以 缓冲半径为半径，以点k到点k-1方向为0度方向，逆时针旋转90 °所形成的1/4圆弧上的所有点；若点k-1为凹角，取点k-2的对应 点集中的最后一个坐标点，该点k+1为点k的后一个坐标点，若点 k+1为凸角，取点k+1的对应点集中的第一个坐标点；若点k+1为凹 角，取点k+2的对应点集中的最后一个坐标点，把这些坐标点按目标 线的线路方向顺序插入链表中，形成修改过的坐标点序列表；

（43）、删除初始化缓冲区（初始化缓冲区为直接生成、未进行 特殊处理的缓冲区结果，此时对应的也是失真的坐标点序列表）边界 上的失真坐标点，然后使用修改过的坐标点序列表替换失真的坐标点 序列表；

（5）处理规定线路缓冲区或电子围栏缓冲区边界线的自相交问 题：

（51）逐步判断规定线路缓冲区或电子围栏缓冲区边界上各个线 段是否相交，首末线段、相邻线段除外；

（52）如果相交，则是有自相交问题，记录所有的自相交点；

（53）定义两个动态数组，一个用于存储缓冲区边界多边形有序 结点坐标的动态数组Array1和另一个用于存储所有自相交多边形有 序结点坐标的动态数组Array2；

（54）将以上产生的缓冲区边界多边形(闭合环)的各结点按生成 顺序存入数组Array1中；

（55）应用递归方法求取所有自相交多边形并存入数组Array2 中；

（56）再采用面积的定积分的近似算法，判断数组Array2中自 相交多边形的方向，如果是顺时针方向，则是缓冲区边界多边形的内 环；如果是逆时针方向，则面积绝对值最大的多边形是缓冲区边界多 边形的外环，而其它逆时针方向的多边形不是缓冲区的组成部分；

（57）连接所有求得的缓冲区交点，即得到边界结果；如图3所 示，是规定线路缓冲区的边界自相交解决结果。

步骤2、使用单调链报警算法，用于判别通过GNSS（全球导航卫 星系统，包括GPS、北斗等）获取的公务车辆当前位置点与已生成的 敏感地点缓冲区、规定线路缓冲区、电子围栏缓冲区的空间关系，根 据预设的报警规则进行报警：

单调链报警算法的基本原理是判断一个多边形是否与另一个多 边形相交。一方面，该算法把敏感地点缓冲区、规定线路缓冲区、电 子围栏缓冲区都作为一个参照多边形进行判断，当参照多边形的顶点 数为0，则表示为敏感地点缓冲区，当参照多边形的顶点数为2，则 表示为规定线路缓冲区，当参照多边形的顶点数大于或等于3，则表 示为电子围栏缓冲区；另一方面，将公务车辆当前位置点也作为一个 顶点数为0的目标多边形，并判断表示位置点的目标多边形是否与前 述表示缓冲区的参照多边形相交。

单调链报警算法的实现：创建目标多边形和参照多边形链表、计 算交点、遍历链表、产生预警信息，具体包括如下步骤：

（1）创建链表

算法采用单线性链表来表示目标多边形和参照多边形,单链表的 每一个结点按序(顶点输入的顺序)存储着多边形的一个顶点。最后一 个结点的指针指向第一个结点(循环单链表)。每个链表由一个头指针 指向第一个结点。采用上述数据结构创建目标多边形和参照多边形链 表，判断并计算第一个交点；

（2）计算交点

本发明的单调链报警算法，共有3种交点情况。正常情况下经过 点A的线段如图4-1所示。另有2种非正常情况：经过多边形顶点的 情况如图4-2所示；与某一条边共线情况，共线就有无穷多的交点， 导致判断规则失效如图4-3所示。

运用解析几何计算目标多边形中的每条边所在直线和参照多边 形中的任意边所在直线，按直线一般方程求两条线段的交点，并判断 交点坐标是否为实际交点；

若为实际交点。则把该交点以其在目标多边形上的先后顺序，按 多边形路线方向插入到两个多边形的链表中；针对图4-2所示，经过 交点的线段经过多边形顶点的情况，在求出交点后，不再将相同交点 插入到链表中；针对图4-3经过交点的线段与参照多边形的某一边重 叠的情况，忽略该重叠的参照边，只对重合边以外的多边形的边求交；

（3）遍历链表

遍历步骤（1）创建的目标多边形和参照多边形链表，如果存在 交点，则可以判断位置点在缓冲区内。

（4）根据以下预设的报警规则，来产生预警信息：

（41）、到达敏感地点的报警规则：位置点在缓冲区内；

（42）、偏离规定线路的报警规则：位置点在缓冲区外；

（43）、出入电子围栏的报警规则：位置点由缓冲区内变为缓冲 区外（出）、或由缓冲区外变为缓冲区内（入）。

公务车辆监管的准确预警，首先要求能够准确生成敏感地点缓冲 区、规定线路缓冲区和电子围栏缓冲区；有了缓冲区，才能快速准确 的判断公务车辆的位置点与三者缓冲区的空间关系，进一步实现位置 预警。相比于传统的缓冲区生成方法，本发明针对应用环境经过优化 的缓冲区算法有效地改进了数据结构设计，简化了缓冲区边界的生成 过程，提高了边界自相交的精度，整体上大大提高了预警区域的生成 速度和准确性，能有效地满足公车监管中预警快速、准确的要求。

本发明单调链报警算法的主要思想是采用循环单线性链表存储 多边形的输入和输出，每个节点按序存储多边形的一个坐标顶点。该 单调链报警算法采用了简单的数据结构，不仅节省了大量的存储空 间，而且节省了大量的运算时间。

本发明只需得到敏感地点、规定线路、电子围栏这三者对应的坐 标集和缓冲半径，即可构造缓冲区域，进而判断公务车辆位置与这三 者的空间关系，最终产生预警，具有极强的操作性。

以上所述，仅是本发明较佳实施例而已，并非对本发明的技术范 围作任何限制，故凡是依据本发明的技术实质对以上实施例所作的任 何细微修改、等同变化与修饰，均仍属于本发明技术方案的范围内。