利用叉积判断法实现安全管道判断_方兴
- 格式：pdf
- 大小：1.51 MB
- 文档页数：4
n
2， …，n，设 ∠P i P0 P i +1 = α i ． 如果 Σ α i = 0 ，则 P0
i =1 n
图4
分割法
位于多边形之外; 如果 Σ α i = 2 π，则 P0 位 于 多 边
i =1
形之内． 这里 α i = arccos
V ． ( | VV · || V |)
i i +1 i i +1
3
图2 点在凸多边形外
任意多边形的判断
当多边形为凹时，即使点在多边形内也不能保
至此 可 得 出，点 P0 包 含 在 凸 多 边 形 P1 ，P2 ， …，P n 内的充要条件是叉积 V i × V i +1 ( i = 1 ， 2 ，…， n) 的符号相同． 当点 P0 位 于 凸 多 边 形 的 顶 点 或 边 上时，会出 现 2 对 或 1 对向 量 的 叉积 为 零 向 量，但 其它各向量的 叉积 符 号 相同; 当 点 P0 位 于 凸 多 边 形外部某边延长线上时，也会 出 现 1 对向 量 的 叉积 为零向量，但必然有一对向量 的 叉积 与 其 它各 对向 量叉积的符号相反． 2． 3 面向对象的实现 基于面向对象的思想，可定义一个描述凸多边 形的类 CPolygon，将 各 顶 点按 顺 序 加入 到 数 组 m_ pointArray 中，实现叉积判断 法的 函 数 bool IsInRe图3 叉积判断法流程
Application of Crossmultiply Method to Judgement of Safety Channel
Fang Xing， Fang Jianxun， Wu Xiaoxin
( Unit 92124 ，Dalian 116023 ，China)
Abstract: Crossmultiply method is a simple way to judge whether a point is inside a polygon． An algorithm as well as the implement of this method is described． Benefiting from its simplicity and efficiency， this method is suitable for judging whether a missile is going beyond the safety channel． Keywords: crossmultiply; polygon; safety channel; flight test
图5
填补法
分割法和填补法是将对凹多边形的判断转化为对 多个凸多边形的判断的两种方法，对于不同的凹多边 形， 有时选择分割法方便， 有的选择填补法更好， 一般 的原则是， 要参与判断的凸多边形越少越好．
· 61· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March，
0 0
+ u( u ≥ 0 )
，
求射线与多边形交点 数． 若 交 点 数 为 奇 数，则点 在 多边形内; 为偶数，点在多边形外． 交点计数检验法的优点是算法巧妙，不仅适用 于凹多边形，还适用于 带 孔 的任 意 封 闭 区 域; 但 是 该方法在临界条件下，如 射 线 通过 顶 点 时，需要 一 些特 别 约 定． 另 外，该 方 法 虽 然 便 于用 语 言 描述， 但在具体实现时需要进行较大的变换． 3 ． 3 分割法和填补法 与交点计数法以及夹角和检验法相比，叉积判 断法具有简单高效的优点，每 对向 量 的 叉积计 算 只 涉及 5 次减法运算 和 2 次 乘 法 运 算，最 坏 时 需要 n 次叉积，最好时需要 2 次 叉积，但 只适 用于 凸 多 边 形． 然而，任何凹多边形都可分割成若干个凸多边 形，如 图 4 所 示，于 是，判断 一 点是 否 在 凹 多 边 形 内的问题，可以转化为判断一 点是 否 在 构 成 该 凹 多 边形的任 意 一 个 凸 多 边 形 的 问题． 这 种方 法 称 做 “分割法” ．
2
2． 1
叉积判断法
向量的叉积 向量 a 和 b 的叉积 a 和 b 所决定的平面， 按右手规则从 a
［作者简介］ 方 兴，高级工程师． ［收稿日期］ 2010 03 15
· 59· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March， gion( CPoint point) 被封装在类 CPolygon 中． class CPolygon : public CObject { private: CArray ＜ CPoint， CPoint ＞ m_pointArray; … public: bool IsInP( CPoint point) ;
· 58· 2011 ，( 2 ) : 58 ～ 61 战术导弹技术 Tactical Missile Technology March，
［ 1300 ( 2011 ) 02 0058 04 文章编号］ 1009 -
当点 P0 包含在凸多 边 形 内 时，V1 与 V2 ，V2 与 V3 ，…，V n 与 V n +1 之间的 夹 角 都 小于 π，或 都 大 于 2 ，…，n) 的 π，如图 1 所示，这时 V i × V i +1 ( i = 1 ， 符号相同． 反之，当点 P0 位于凸多边形外部时，所 有顶点都在点 P0 同 侧，必 然 有 一 对向 量 的 叉积 与 其它各对向量叉积的 方 向 相 反，如 图 2 所 示，这 时 V i × V i +1 ( i = 1 ， 2 ，…，n) 的符号不相同．
· 60· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March， 证各对叉积的符号相同，因此 叉积判断 法 仅 适 用于 凸 多 边 形． 对 于任 意 多 边 形，教 科 书 上通常 给 出 “交点记 数 检 验 法 ” ． 下面 简 单 和“夹 角 和 检 验 法 ” 介绍这两种算法，然后介绍本 人 在 实 际 工 作中总 结 : “分割法” “添补法” ． 的方法 和 3 ． 1 夹角和检验法 假定平 面 上 一 个 多 边 形 的 各 顶 点 为 P1 ，P2 ， …，P n ， P0 为一个点， i = 1， 构造向量 V i = P i － P0 ，
图1 点在凸多边形内
… } 设点 P0 其它的坐标为( x0 ，y0 ) ，凸多边形各顶 2 ，…，n，则 点 P i 坐标为( x i ，y i ) ，i = 1 ， V i = ( x i － x0 ) i + ( y i － y0 ) jV i × V i +1 = ［ ( x i － x o ) ( y i +1 － y0 ) － ( y i － y0 ) ( x i +1 － x0) ］ k． 为了便于 说 明问题，这 里 将 函 数 IsInP 的 流程 用图 3 描述． 类似地，可以定义一个描述 圆 的 类 CCircle，属 性为圆心坐标和半径，同样将 判断 点是 否 在 圆 内 的 函数 bool IsInC ( CPoint point ) 封 装 在 类 中． 判断 一 点( x，y) 是否在圆内，只需将其坐标代入不等式( x － x0 ) 2 + ( y － y0 ) 2 ≤ R2 中． 其中， ( x0 ， y0 ) 为圆心， R 为半径．
夹角和检 验 法的 优 点是 描述 简 单，便 于理 解; 缺点是计算量较大，每得到一 个 夹 角 需要 计 算 三 个 点积、两 个 开 平 方 和 一 个 反 三 角 函 数． 此 外，还 需 计算两个向量叉积的符号来判断角度的方向． 3． 2 交点计数检验法 对于凹多边形和带孔的多边形，可以用交点计 数法 判断 一 点是 否 在 其 内 部． 判断方 法 是，从点 P0 ( x0 ，y0 ) ，做 一 水 平 射 线: x {xy = = y
4
4． 1
常见的安全管道
环形管道
O1 和 O2 ，CPolygon 类的对象 P 表示 多 边 形 ABCD， 则点 P 是否在管道内的判断条件为: P． IsInP( p) ＆＆ ! O1 ． IsInC ( p) | | O2 ． IsInC ( p) ．
“分割法” ， 采用 判断一点 P0 是否在图 5 所示的 凹多边形内，可以表示为 P123 ． IsInP ( P0 ) P1345 ． IsInP ( P0 ) ; 其 中，P123 和 P1345 为 CPolygon 类的对象，分别表 示多边形 P1 P2 P3 和 P1 P3 P4 P5 ． 有时连接凹多边形凹角两侧的顶点，可构成一 个大凸多边形，如图 5 所 示，这个大 凸 多 边 形 是由 原来的凹多边形加上一个小 凸 多 边 形构 成 的，这 样 判断一点是否在凹多边形内 的 问题，可 以 转 化 为 判 断一点是否在大凸多边形内，但 不 在小 凸 多 边 形 内 “填补法” ． 的问题． 这种方法称做 “填补法” ， 采用 判断一点 P0 是否在图 5 所示的 凹多边形内，可以表示为 P1245 ． IsInP ( P0 ) ＆＆! P234 ． IsInP ( P0 ) ; 其 中，P1245 和 P234 为 CPolygon 类的对象，分别表 示多边形 P1 P2 P4 P5 和 P2 P3 P4 ．
利用叉积判断法实现安全管道判断
方 兴， 方建勋， 吴小欣
( 92124 部队，大连 116023 ) ［ 摘 要］ 说明了叉积判断法是判断平面上一点是否 在 凸 多 边形 内 的 简 单 方法，介 绍 了 它 的 基 本 算 法和 具 体 实
现，并通过分割法和填补法将其改进为适合任意多边形以及有圆弧边界区域 的 方法． 该 方法简 单实 用，特 别 适 合 用于对飞行器的超安全管道判断． ［ 关键词］ 叉积判断法; ［ 中图分类号］ TJ760 多边形; 安全管道; 飞行试验 ［ 文献标识码］ A
2， …，n，设 ∠P i P0 P i +1 = α i ． 如果 Σ α i = 0 ，则 P0
i =1 n
图4
分割法
位于多边形之外; 如果 Σ α i = 2 π，则 P0 位 于 多 边
i =1
形之内． 这里 α i = arccos
V ． ( | VV · || V |)
i i +1 i i +1
3
图2 点在凸多边形外
任意多边形的判断
当多边形为凹时，即使点在多边形内也不能保
至此 可 得 出，点 P0 包 含 在 凸 多 边 形 P1 ，P2 ， …，P n 内的充要条件是叉积 V i × V i +1 ( i = 1 ， 2 ，…， n) 的符号相同． 当点 P0 位 于 凸 多 边 形 的 顶 点 或 边 上时，会出 现 2 对 或 1 对向 量 的 叉积 为 零 向 量，但 其它各向量的 叉积 符 号 相同; 当 点 P0 位 于 凸 多 边 形外部某边延长线上时，也会 出 现 1 对向 量 的 叉积 为零向量，但必然有一对向量 的 叉积 与 其 它各 对向 量叉积的符号相反． 2． 3 面向对象的实现 基于面向对象的思想，可定义一个描述凸多边 形的类 CPolygon，将 各 顶 点按 顺 序 加入 到 数 组 m_ pointArray 中，实现叉积判断 法的 函 数 bool IsInRe图3 叉积判断法流程
Application of Crossmultiply Method to Judgement of Safety Channel
Fang Xing， Fang Jianxun， Wu Xiaoxin
( Unit 92124 ，Dalian 116023 ，China)
Abstract: Crossmultiply method is a simple way to judge whether a point is inside a polygon． An algorithm as well as the implement of this method is described． Benefiting from its simplicity and efficiency， this method is suitable for judging whether a missile is going beyond the safety channel． Keywords: crossmultiply; polygon; safety channel; flight test
图5
填补法
分割法和填补法是将对凹多边形的判断转化为对 多个凸多边形的判断的两种方法，对于不同的凹多边 形， 有时选择分割法方便， 有的选择填补法更好， 一般 的原则是， 要参与判断的凸多边形越少越好．
· 61· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March，
0 0
+ u( u ≥ 0 )
，
求射线与多边形交点 数． 若 交 点 数 为 奇 数，则点 在 多边形内; 为偶数，点在多边形外． 交点计数检验法的优点是算法巧妙，不仅适用 于凹多边形，还适用于 带 孔 的任 意 封 闭 区 域; 但 是 该方法在临界条件下，如 射 线 通过 顶 点 时，需要 一 些特 别 约 定． 另 外，该 方 法 虽 然 便 于用 语 言 描述， 但在具体实现时需要进行较大的变换． 3 ． 3 分割法和填补法 与交点计数法以及夹角和检验法相比，叉积判 断法具有简单高效的优点，每 对向 量 的 叉积计 算 只 涉及 5 次减法运算 和 2 次 乘 法 运 算，最 坏 时 需要 n 次叉积，最好时需要 2 次 叉积，但 只适 用于 凸 多 边 形． 然而，任何凹多边形都可分割成若干个凸多边 形，如 图 4 所 示，于 是，判断 一 点是 否 在 凹 多 边 形 内的问题，可以转化为判断一 点是 否 在 构 成 该 凹 多 边形的任 意 一 个 凸 多 边 形 的 问题． 这 种方 法 称 做 “分割法” ．
2
2． 1
叉积判断法
向量的叉积 向量 a 和 b 的叉积 a 和 b 所决定的平面， 按右手规则从 a
［作者简介］ 方 兴，高级工程师． ［收稿日期］ 2010 03 15
· 59· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March， gion( CPoint point) 被封装在类 CPolygon 中． class CPolygon : public CObject { private: CArray ＜ CPoint， CPoint ＞ m_pointArray; … public: bool IsInP( CPoint point) ;
· 58· 2011 ，( 2 ) : 58 ～ 61 战术导弹技术 Tactical Missile Technology March，
［ 1300 ( 2011 ) 02 0058 04 文章编号］ 1009 -
当点 P0 包含在凸多 边 形 内 时，V1 与 V2 ，V2 与 V3 ，…，V n 与 V n +1 之间的 夹 角 都 小于 π，或 都 大 于 2 ，…，n) 的 π，如图 1 所示，这时 V i × V i +1 ( i = 1 ， 符号相同． 反之，当点 P0 位于凸多边形外部时，所 有顶点都在点 P0 同 侧，必 然 有 一 对向 量 的 叉积 与 其它各对向量叉积的 方 向 相 反，如 图 2 所 示，这 时 V i × V i +1 ( i = 1 ， 2 ，…，n) 的符号不相同．
· 60· 2011 ，( 2 ) 战术导弹技术 Tactical Missile Technology March， 证各对叉积的符号相同，因此 叉积判断 法 仅 适 用于 凸 多 边 形． 对 于任 意 多 边 形，教 科 书 上通常 给 出 “交点记 数 检 验 法 ” ． 下面 简 单 和“夹 角 和 检 验 法 ” 介绍这两种算法，然后介绍本 人 在 实 际 工 作中总 结 : “分割法” “添补法” ． 的方法 和 3 ． 1 夹角和检验法 假定平 面 上 一 个 多 边 形 的 各 顶 点 为 P1 ，P2 ， …，P n ， P0 为一个点， i = 1， 构造向量 V i = P i － P0 ，
图1 点在凸多边形内
… } 设点 P0 其它的坐标为( x0 ，y0 ) ，凸多边形各顶 2 ，…，n，则 点 P i 坐标为( x i ，y i ) ，i = 1 ， V i = ( x i － x0 ) i + ( y i － y0 ) jV i × V i +1 = ［ ( x i － x o ) ( y i +1 － y0 ) － ( y i － y0 ) ( x i +1 － x0) ］ k． 为了便于 说 明问题，这 里 将 函 数 IsInP 的 流程 用图 3 描述． 类似地，可以定义一个描述 圆 的 类 CCircle，属 性为圆心坐标和半径，同样将 判断 点是 否 在 圆 内 的 函数 bool IsInC ( CPoint point ) 封 装 在 类 中． 判断 一 点( x，y) 是否在圆内，只需将其坐标代入不等式( x － x0 ) 2 + ( y － y0 ) 2 ≤ R2 中． 其中， ( x0 ， y0 ) 为圆心， R 为半径．
夹角和检 验 法的 优 点是 描述 简 单，便 于理 解; 缺点是计算量较大，每得到一 个 夹 角 需要 计 算 三 个 点积、两 个 开 平 方 和 一 个 反 三 角 函 数． 此 外，还 需 计算两个向量叉积的符号来判断角度的方向． 3． 2 交点计数检验法 对于凹多边形和带孔的多边形，可以用交点计 数法 判断 一 点是 否 在 其 内 部． 判断方 法 是，从点 P0 ( x0 ，y0 ) ，做 一 水 平 射 线: x {xy = = y
4
4． 1
常见的安全管道
环形管道
O1 和 O2 ，CPolygon 类的对象 P 表示 多 边 形 ABCD， 则点 P 是否在管道内的判断条件为: P． IsInP( p) ＆＆ ! O1 ． IsInC ( p) | | O2 ． IsInC ( p) ．
“分割法” ， 采用 判断一点 P0 是否在图 5 所示的 凹多边形内，可以表示为 P123 ． IsInP ( P0 ) P1345 ． IsInP ( P0 ) ; 其 中，P123 和 P1345 为 CPolygon 类的对象，分别表 示多边形 P1 P2 P3 和 P1 P3 P4 P5 ． 有时连接凹多边形凹角两侧的顶点，可构成一 个大凸多边形，如图 5 所 示，这个大 凸 多 边 形 是由 原来的凹多边形加上一个小 凸 多 边 形构 成 的，这 样 判断一点是否在凹多边形内 的 问题，可 以 转 化 为 判 断一点是否在大凸多边形内，但 不 在小 凸 多 边 形 内 “填补法” ． 的问题． 这种方法称做 “填补法” ， 采用 判断一点 P0 是否在图 5 所示的 凹多边形内，可以表示为 P1245 ． IsInP ( P0 ) ＆＆! P234 ． IsInP ( P0 ) ; 其 中，P1245 和 P234 为 CPolygon 类的对象，分别表 示多边形 P1 P2 P4 P5 和 P2 P3 P4 ．
利用叉积判断法实现安全管道判断
方 兴， 方建勋， 吴小欣
( 92124 部队，大连 116023 ) ［ 摘 要］ 说明了叉积判断法是判断平面上一点是否 在 凸 多 边形 内 的 简 单 方法，介 绍 了 它 的 基 本 算 法和 具 体 实
现，并通过分割法和填补法将其改进为适合任意多边形以及有圆弧边界区域 的 方法． 该 方法简 单实 用，特 别 适 合 用于对飞行器的超安全管道判断． ［ 关键词］ 叉积判断法; ［ 中图分类号］ TJ760 多边形; 安全管道; 飞行试验 ［ 文献标识码］ A
