③任意 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中不存在钝角时，则通过
l,
√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—
14 J. 20,3 1:11 0 .作者简介
{
/线段的右手边/}
许
静女， 1 7 ( 9 2一 )中国电子科技集团公司第五十四研究，
所高级工程师。主要研究方向：形图像学。图
3 4
2 0 Ra i g n e i g Vo 3 09 d o En i e rn 1. 9 No. 1 1