一种判定运动目标越界的算法

发布时间：2021-06-05

一种判定运动目标越界的算法

信号与信息处理

一

种判定运动目标越界的算法许静，张冬宁，张学军

(中国电子科技集团公司第五十四研究所，河北石家庄 00 8 ) 50 1摘要运用计算机图形学技术，对运动目标是否越过限定界限进行剖析，提出将该工程问题转换为固定点与线段的位置关系判定的计算几何问题，并基于点与线间位置关系，利用非交叉连续线段的有序性，通过角度和方向的判断，对运动点和有序线段的关系进行了有效的判定，解决了运动目标越界的问题，并在实际工程中取得了良好的应用效果。特别是运行时问、效率的方面，充分验证了该方法在解决目标越界问题的有效性。关键词计算机图形学；运动目标；有序线段；位置关系 T 315 P1 . 文献标识码 A 文章编号 10—3 0 (0 9 1—0 3—0 0 3 16 20 ) 1 0 2 3中图分类号

An Al o ih f r De e tn h o i g Ta g t Be o d t e Bo n a y g rt m o t c i g t e M v n r e y n h u d rXU Jn,Z AN o gnn,Z A u—u ig H G D n—ig H NG X ejn( h 4hR sac ntueo ET T e5 t eerhIsi t f C C,S ah a gH bi0 0 8, C ia) t h izu n ee 5 0 1 hn OAb ta t T i p p r n lss sr c h s a e a ay e wh te h mo ig ag t v rtp h b un ay, a d ta so ms h s n ie rn p o lm it a eh r te vn tre o ese s t e o d r n r n fr ti e gn e g rb e i no

g o t c po lm y c mp trg a hc e h oo y. Ba e n te p sto a eain hp a n ons a d l e, od rie so o - rsig e mer rbe b o ue r p istc n lg i s d o h oiin lrlt s i mo g p it n i s o n re l s fn n co sn n

cneui n eme t a djd igb n lsa ddrcin, w ae e et eysl

e h rbe h te vn agtoe tp h o sct el esg ns n gn y age n i t s eh v f ci l ovd tepo lm w eh rmoig t e vr e ste v i u e o f v r sb n r . T e cu le gn e n e utid c ts t a ti lo tm o ny d ce s he c mpuain c mpe i ou day h a ta n ie r g r s l n iae h t hs ag r h n to l e ra e t o i i tto o lxt y, b t lo n r ae h u as ice s teefcie e s fe tv n s .Ke y wor s c mp t rg a h c; mo i g t r e; o d ry s g n; p s t na e a i n h p d o ue p is r v n a g t r e l e me t o ii lr l t s i o o

0引言随着现代信息技术的发展，来越多的领域采越用了空间信息与业务逻辑分析判断相结合的技术手段，借助数据结构和计算机图形学等基础学科，将业

时检测其是否超越了规定的界限。如果目标的越界情况出现，必要时则采取紧急措施，阻止其越界行动。

由于可以连续不断地获得运动目标的位置信息，而且当其位置点迹存在较大误差或密度不够时，通过定位信息预处理将位置数据进行规范化，以提

务问题转化为计算机可实现的复杂的判定与运算，其中对运动目标活动区域的监控和报警就是其中一个典型问题。在边防、防、航和交通管理等诸多领域内均海导

高数据的可用性。警戒线在图形上表现为人为划定的简单折线，不存在线段交叉等复杂情况。因此，解决运动目在标越界判定问题前，了突出关键问题，为假设： ①运动目标的定位数据应经过数据过滤，出剔了飞点等异常点； ②运动目标的定位数据密度能够满足判定要求；

存在监视确定的警戒线周围的情况，防止运动目标接近或越过警戒线。因此就产生了一个如何判定运动目标接近甚至越过警戒线的问题，当运动目标接近警戒线到限定的距离时给出报警提示，提示监控人员采取行动，防止其越过界限。

③警戒线简化成简单的非

交叉的有序线段； ④警戒线的警戒距离是全线等值的。在满足上述条件下，经分析可得出需要解决的问题是运动目标与警戒线 2个对象问的关系，判即定的对象是运动目标和警戒线，判定的内容是它们之间的关系。实际使用中对这 2对象间的关系要个求如下：收稿日期：090.6 20.82

本文从实际需求出发，通过应用环境分析，形成应用开发模型，出了运用计算机图形学等专业技提术的解决方法和实现步骤。

1问题的提出与分析在边防、防导航、通管理中经常会监视运动海交

目标的运动情况，特别是对于目标的运动范围，实要3 2 2 0 Ra o Ensn rng Vo 3 09 di a i 1. 9 No. 1 1

一种判定运动目标越界的算法

信号与信息处理①当运动目标在警戒线告警距离要求范围外时，没有到达警戒状态，进行处理；则不 ②当运动目标在警戒线告警距离要求范围内，进行报警，提示监视者并记录当前状况。

2算法分析2 1算法需求分析 .在解决运动目标越界问题前，首先需要明确算法需要的主要要素：戒线和警戒方向。警戒线可警用简单有序连续线进行描述，而警戒方向则是判定是否越界的关键。 2 1 1简单有序连续线 ..简单的连续线是一组首尾相连的线段组成的有限集合， 2个相邻线段的交叉点即是这 2条线的每顶点，因此有序线段可以用有序的点序列 P, 。P, P,,表示，可以用向量 P P1 P 2…, 2… P也 o, l, PP一

条，因此，了提高系统的运算，先通过警戒线的为首外接矩形判断运动目标是否处于该警戒线判定的范围内。这样就可以滤除不在该警戒线附近的运动目标，高了运算效率。提在警戒线外接矩形内的运动目标，按照警戒则线存储的顺序逐段进行判断，出与运动目标距离找最近的线段。在判断过程中会出现如图所示的 2种情况：运动目标与线段的垂线在线段上，图 1①如中垂线 a所示；运动目标与线段的垂线在延长线②上，图中垂线 c所示。如/一 .

、

运动目标

尸 2

P所代表的线段表示。

图 1

运动目标与警戒线的位置关系

由于有序连续线的方向性对越界的判断具有极其重要的意义，因此本文中采用了向量的表示方法，通过首尾接续的有序线段的起点和终点，决定整来个连续线的走向为顺时针或逆时针。此外，对于简单的有序线还具有系列特征： ①所有的顶点都各不相同；

对于后一种情况，距离则不能采用垂线的距其离，而是要用运动目标与线段两端点连线的最短距离来替代运动目标与线段的距离。具体的算法描述如下：

运动目标点 P ( O Y )线段 P 2其中",0与 g l ( P P (, 1, 2(,Y ),线公式为 A*+ 1 l Y ) P 2 2 )直 B Y+C=0 。P1 2 问的距离为： P

②任何顶点都只属于与之关联的 2条线段的起点或终点；

③任意 2线段都不相交。条 2 12警戒方向 ..警戒方向是指从警戒线的那一侧进行穿越是属于报警情况，即是从警戒线走向的左侧或右侧进行

d=/—X)+(1 y)。￣ (l 2 y一 2 则 12 P,成立：

() 1

2 1一为钝角时， P其必然有如下公式

>;+或d,√d+。 (√d d, p>; d 2 p。 )此时采用取 P点到 P, 2两点距离的最小值 11 9为运动目标与警戒线段的距离：d=mi( n。,

穿越警戒线。由于警戒线可由简单有序连续线表示，连续而线的方向又可分为顺时针或逆时针，因此在实际实

de ) e。

() 3

现过程中，了简化运算，为将警戒方向统一规定为从警戒线的右侧穿越到左侧，若原定义的警戒线方向与该方向不同，通过将警戒线重新倒排序的方法则使其一致。2 2算法解析 .

当 p 12 pP,d:

21 P中不存在钝角时，则通过

√A+B2

( 4)

运动目标越界的问题根据不同情况可以分解成2个部分：动目标接近警戒线和运动目标穿越警运戒线。

2 2 1运动目标接近警戒线的算法 ..在这种情况下，要判断的是该运动目标是否首

接近警戒线，近的是哪一段，后在进行是否超越接之警戒距离的判断。在实际

情况下，动目标很多，运警戒线也不止一

直接计算其间的距离。通过上述算法的描述，以直接根据运算结果可判断是否进入警戒距离。 2 2 2运动目标穿越警戒线的算法 ..运动目标的特点就是运动的，因此运动目标的定位信息是由一系列具有时间特性的空问数据组成的。运动目标穿越警戒线的位置关系如图 2所示。由此便可以根据其相邻 2点位置所组成的线段是否与警戒线相交来判断运动目标是否越界，体算法具描述如下：

当线段 P P 与运动目标 2个时段的连线斜率20 09年无线电工程第 3 9卷第 1期 3 1 3

一种判定运动目标越界的算法

信号与信息处理相同时，不存在交点。则e ei k> d 1 l ( s f kl k<琥) 1

当线段 P P。:与运动目标 2个时段的连线存在交点时，可求得交点坐标 (则当分母不为 0的情况下 ):(3 Y 4一y 3 (一 1 4 ) 2 )一( l一y 1 (一 ) Y 2 2 ) 4 3}

/线段的左手边/f

一— _一

■

‘■

厂

’

等 1(一 )一(Y一Y )净 1。 5 (一Y ) 4 3) 4 3 ( 4 y二二 ( ) 2 2一 )当求得的值在 P P线段范围内，必然存在 :则交点，即动目标存在穿越警戒线的情况。o起始运动位置

③判定运动目标是否在警戒线外接区域内。此时可以直接通过目标点是否在外接区域横纵座标的最大和最小值之间的判断方法进行判断； ④若目标在警戒区域内，利用上述的运动目则标接近警戒线的算法对各条警戒的轮巡判断，到直得到运算结果； ⑤采用运动目标穿越警戒线的算法对运动目标是否穿越警戒线进行判定。为了提高运算效率，需要进行如下具体解决办法：确定 2条线段的坐标范围是否有相交部分，如果没有相交部分，则一定没有交点。

图 2运动目标穿越警戒线的位置关系

i ( ( i(, ): l=m x, ) f ( m n 4< < a( 3 3 4 )

l( i , )=< a(,4 ) l rn 3 a ( 4< 2=m x 3 ) )

3应用实践在实际工程项目中对上述算法进行了详细的设计与实现。在实现过程中分

成如下几个步骤： ①通过鼠标采用人机交互的方式，按照输入点

&&( ri( 3 Y ) ( n Y, 4<:Y<:ma ( 3 y ) a 1 xY, 4)

l( i( 3Y )=Y< a( 3Y) ) l rn Y,4< 2=m x Y,4 ) ) a;

/可能存在交点，算交点/计}es le

的先后次序依次连接各点形成警戒线； ②确定警戒方向并根据警戒线右侧为正方向的原则，对警戒线进行调整。即当警戒方向在警戒线的左边时，对警戒线进行倒排序。判断取警戒要线 ( P。线段与正上方的夹角如 P) ,目标点与 P (, 1组成线段与正上方的夹角 k线段 P 2 1Y ), 1 P反向延长线与正上方的夹角。于是就有当 t k>时， >d t k> k为线段的左手边； t当 k<d k时， d>k>t k k为线段的右手边，具体的实现如下：it f k>d ( k)1

{ /不存在交点，回/返}

通过上述步骤，实现了运动目标接近和穿越警戒线的判断，该算法在工程应中取得了良好效果。

4结束语本文运用需求获取与分析的基本方法，过对通运动目标越界问题的深入剖析，工程实际问题转将化为点与线段、段与线段间空间关系的问题。针线对转化后的问题特征，充分考虑运行时间、在效率的情况下，出了相应的解决方法，给经实际工程项目中应用和检验，证了该方法在解决目标越界问题的验有效性。参考文献

i(t f k>=&&>= d k)1

/线段的左手边/I

es f<d > t ) l i e ( kl l k{

. 1 .

/线段的右手边/f

[]孙家广，隆文 .算机图形学[ .京：清华大学出 1许计 M]北版社，9 3 8 7 19:1—3 .[]H L , C S N K D C J .求工程[ . 2 U LM E C J K O , I K A. J需 A M]北京：华大学出版社， 0:1—3 .清 2 3 7 3 0

}es f t d ) l i k< k e (

{i t=&& k f k< (<= d k)

[]孙建国，廷华， 3艾帅资等 .型地图的空间相关关类系[]武汉大学学报，083 () 0—