判定检测点是否在多边形内的新方法.pdf

判定检测点是否在多边形内的新方法 陈树强 陈学工 王丽青 中南大学信息科学与工程学院，长沙，410083 Email:chenshu7920@126.com 摘 要 本文提出一种新方法以检测一个点是否在多边形内。该方法将矢量和射线法结 合，彻底解决了射线法所具有的奇异情况。实验结果证明，该方法具有简单、易实现、快速 等优点。 关键字 多边形、射线法、计算几何 1．引言 判断点在多边形内外[1,5,6]是计算机图形学的最基本算法，在计算机图形处理、模式识别、 CAD及科学计算可视化中有着广泛的应用。判断点在多边形内外的算法有主要有定向射线法、 角度法。角度法要使用复杂的三角运算，计算量大；在工程上应用最多的是定向射线法，这 种方法简单、可靠，但其难以处理对边界点及边界与射线共线等特殊情况的处理。今年来， 人们提出了基于可见边的点在多边形内外判断[1,4] [2,3] 以及通过多边形进行层次化存储 ，可以 缩短检测处理所需要的时间等方法。这些方法主要从可靠性、计算量等方面进行了改进。本 文所提出的方法通过将有向角和射线法结合，彻底解决了射线法所具有的奇异情况，具有简 单、快速、易实现等优点。 2 ．基本概念 设OA 、OB 是非零矢量，将OA 绕点 O 旋转到与OB 方向相同的位置时，所形成的角 ∠AOB 称为有向角。规定逆时针旋转为正方向，顺时针旋转为负方向。 设线段 s 的两个顶点为 a 和 b ，则 s 与直线 l 所形成的关系可划分为三大类：（a ） ｓ有 且仅有一个顶点（a 或者 b ）在 ｌ上，称这种关系为半跨越；（b ） ｓ的两个顶点a 和 b 分别 在 ｌ的两侧，称这种关系为跨越；（c ）ｓ的两个顶点a 和 b 在 ｌ的同一侧或线上，称这种关 系为未跨越。 过点Q作 ｘ正方向的水平射线 ｌ。若线段s跨越（或半跨越）射线 ｌ且与点Q所成的有向 角∠aQb 为正，称为正向跨越（或正向半跨越），否则称为负向跨越（负向半跨越）。如图 1， 线段P P 、P P 、P P 、P P 都属于正向半跨越直线l，P P 、P P 属于负向半跨越直线l，线 1 2 3 4 4 5 6 7 2 3 5 6 1 段P P 属于负向跨越直线l，线段P P 、 7 8 8 9 P P 属于未跨越直线l 。设线段s与射线 0 1 ｌ交于点 ｋ，那么线段s可以看作线段 ak ，kb组合而成（如图 1 中的P P 可看 7 8 作由P k 、kP 矢量和）。若将s与l 的关系 7 8 用f （s ，l ）的值来表示其权重，如下表 示： 　　　正向半跨越 1 ⎧ ⎪ － 　　负向半跨越 ⎪ 1 ⎪ f s l 　　　未跨越 = ( , ) ⎨0 ⎪ 　　　正向跨越 2 ⎪ ⎪ － 　　负向全跨越 ⎩ 2 3 ．多边形内外点判定算法 在本文中，假定