快速判断点是否在自交多边形内的方法.docx

系统仿真学报Vol. 15 No. 11Nov. 2003 1592 JOURNAL OF SYSTEM SIMULATION快速判断点是否在自交多边形内的方法吴坚，姜虹，王小椿（西安交通大学机械工程学院数控研究所，西安 710049）摘要：提出一种新方法，检测一个点是否在多边形和环内。此方法从检测点发出一条射线，根据边与射线的位置关系，定义了边相对于射线的位置函数，然后计算出所有边的位置函数之和，据此 判断检测点是否在多边形和环内。该方法不仅能够检测简单多边形，还可用于检测自交多边形，并 能同时检测多个多边形。实验结果表明，该方法简单，可靠，检测速度快。 关键词：多边形；简单多边形；自交多边形；包含检测文章编号：1004-731X (2003) 11-1592-03中图分类号：TP391文献标识码：AA method for the decision of a point whether in or not in self-intersected polygonWU Jian, JIANG Hong, WANg Xiao-Chun(School of Mechanic Engineering, Xian Jiaotong Univercity, Xian 710049, China )Abstract：In this paper a new method is proposed to decide whether a point is in a polygon, a self-intersected polygon and a ring. A ray is rejected from the test point. According to the position between the edges of polygon and the ray, we define a posit ion function of edges as to the ray, and then count the sum of the position function of all edges. We can decide whether the point is in the polygon, the self-intersected polygon or the ring by the sum. This method applies not only for simple polygon, but also for self-intersected polygon and several simple polygons in the same time. Experiment result indicates that this method is simple, robust and fast.Keywords：polygon; simple polygon; self-intersected polygon; inclusion test点发出一条射线，求该射线与多边形相交的数目。如果是奇数，则点在多边形内，否则点在多边形外。虽然射线法简单、 有效，但该方法只能用来检测简单多边形，不能用于检测自 相交多边形。本文提出了一种新的检测方法可以解决上面的 问题。为了方便论述，且不失一般性，以下均规定多边形(不 包括自交多边形)以及环中多边形的顶点依次按逆时针方向 排列，射线的方向为水平向右，边的方向符合多边形顶点的 排列顺序。首先，定义一个函数 f(e)，e 是多边形的边，而 且是具有方向的边，边的方向由起点到终点。函数 f(e)称为 边关于射线的位置函数。该函数满足几个条件：(1) 如果边 由下往上穿过射线，则 f=1；(2) 如果边从上往下穿过射线， 则 f=1；(3) 如果边不穿过射线，则 f=0。其次，再定义一 个变量 F 满足下面的公式：n引言点在多边形或多面体内的检测在计算机图形学方面具有大量的应用。对于点在多边形内的检测，许多学者已作了 广泛的研究1-4，但是这些方法只能判断一个点是否在简单 多边形内，不能判断点是否在自交多边形内。本文提出了一 种判断方法，不仅能够检测简单多边形，而且还能检测自交 多边形，并能同时检测多个多边形。多边形定义为线段的有限集合，该集合中每条线段的端 点恰好为两条邻边所共有，而且没有边的子集具有这个性 质。线段为多边形的边，其端点是多边形的顶点，而且顶点 数和边数相等。若多边形的不相邻的边对不相交，则称该多 边形为简单多边形。简单多边形把平面分为两个不同的区 域：内部区域（有界的）和外部区域（无界的）。一般情况 下，多边形理解为边界和内部区域的并。本文所研究的多边 形为简单多边形、自相交多边形和环。 (1)F f ( e )ii 1如果 F=1，则检测点在多边形的内部，如果 F=0，则检测点在多边形的外部。在图 1 中，P、Q 是检测点，m 是由1点在简单多边形内的检测检测一个点是否在一个多边形内，也就是判断该点是否 在这个多边形的内部。一种常用的方法是射线法，即从检测P 点发出的射线，方向如图，P P P P P P P P 是一个多边1 2 3 4 5 6 7 1形。对于 P 点来说，射线穿过多边形的边为 P3P4、P4P5、P5P6、P6P7，其对应的位置函数 f 分别为 1，1,1，1，故 F=0，P 点在多边形外。对于 Q 点，射线穿过的边为 P3P4、 P4P5、P5P6，故 F=1，Q 点在多边形内。显然 F 是检测点的函数，对于任意一个简单多边形，F 的取值只能是 0 或 1， 满足 F=1 的点所组成的集合是多边形的内部，F=0 的点集是 多边形的外部。收稿日期：2002-10-16修回日期：2002-12-31作者简介：吴 坚(1968-), 男, 山西祁县人, 博士生, 研究方向为隐函数技术在 CAGD/CAM 中的应用; 姜 虹(1973-), 女, 山东人, 博士, 研究 方向为 CAGD/CAM; 王小椿 , 江苏人 , 教授 , 博导 , 研究方 向为 CAGD/CAM。Vol. 15 No. 11Nov. 2003 1593 吴坚, 等：快速判断点是否在自交多边形内的方法Step5 输出结果。Step6 结束。2点在自交多边形内的检测P6P4Y7如果多边形的不相邻的边对有交点，且交点为有限多个，则称该多边形为自交多边形。自交多边形把平面分成多个不同的区域，其中一个区域是无界的，称其为自交多边形OX的外部区域，而其它的区域都是有边界的，称其为内部区域。图 1点在简单多边形内的检测检测点与自交多边形的相对位置情况比检测点与简单多边值得注意的是，对于一些奇异情况，比如射线穿过多边形的顶点或与多边形的边重合，上面的方法不能适用，这时 必须修改位置函数 f，使其除了具有前面的定义外，还要满 足几个附加的条件：当多边形的边与射线重合时， f=0。如 果边的方向向上，且射线通过边的一个顶点，则 f=0.5。如 果边的方向向下，且射线通过边的一个顶点，则 f=0.5。 对于奇异情况，判断检测点是否在多边形内的准则与非奇异 情况相同，即：当公式(1)中的 F=0 时，检测点在多边形的 外部。当 F=1 时，检测点在多边形的内部。设 n 是多边形 的边数，多边形的边为 PiPi+1 (i=1 n ，Pn+1=P1)，点 Pi、Pi+1 的坐标分别为(xi, yi)、(xi+1, yi+1)，P 是检测点，其坐标为(x0, y0)，用程序实现该算法的详细步骤如下：Step1 输入多边形各个顶点和检测点的坐标。Step2 设置 F=0。Step3 依次将多边形每条边 PiPi+1 (i=1 n ，Pn+1=P1)的 顶点的 y 坐标与检测 P 的 y 坐标进行比较，分以下几种情 况分别处理。(1) 当 yi y0，且 yi+1y0 时，F 不变；(2) 当 yi y0，且 yi+1y0 时，F 不变；(3) 当 yi = yi+1 时，会出现几种情况，需要分别对待。 如果 y0yi，F 不变。如果 y0yi，且 xix0xi+0 或 xix0xi+0， 则检测点在边 PiPi+1 上，程序转入 step 5，否则 F 不变。(4) 当 yi y0xc 时，射线不穿过 PiPi+1 边，F 不变；当 x0 y0 yi+1 时，同上一种情况一样，需要按照公 式(2)算出 xc，若 x0xc 时，F 不变；若 x0xc 时，F=F1。 如果 x0=xc，则 P 点在边 PiPi+1 上，程序转到 step 5。(6) 当 yi yi+1，且 y0 = yi 或 y0 = yi+1 时，F=0.5。Step4 判断变量 F。如果 F=0，则检测点在多边形的外 部。如果 F=1，则检测点在多边形的内部。图 2 类自交多边形与检测点的相对位置和三个内部区域，A、B、C 所在的内部区域分别是 1 区、2 区和 3 区。按照上面的方法进行检测，检测的数据及结果见表 1。表 1 图 2 自交多边形的检测结果Fk1点射线穿过的边k1检测结果A B CDP2P3, P3P4, P4P5P3P4P4P5P3P4, P4P511102在 1 区内在 2 区内 在 3 区内 在外部11P mQP P5 P3P1 P2Vol. 15 No. 11Nov. 2003 1594 系 统 仿真 学 报2.2 点在类自交多边形内的检测类自交多边形的 F 值可能为 0、1、2，与 1 类自 交多边形相同，F=0 表示检测点在自交多边形的外部，F 为 其它值时，检测点在自交多边形的内部，只是 F=2 所表为 2、1、0，表示 C 点在外环的外部，A 点在 内环的内部、B 点在内 环和外环围成的中间 区域。P3CQ3BQ1AQ2示的区域包含在某个 F=1 的区 域的内部。例如，在 图 3 中， P1P2P3P4P5P6P7P8P1 是一个 2 类自 交多边形，A、B、P1P2PP854检测实例图 4 环与检测点的相对位置AP1P6P7P4我们使用 PC 机（PIII450/128M）对此算法进行了测试，对图 3 中的检测点和自交多边形，判断点 A、B、C 相对于 该自交多边形的位置，检测结果见表 2。BCPP23图 3 检测点与 2 类自交多边形的相对位置表 2检测数据检测点时间(s)FC 是检测点，按照同样的方法，它们的 F 值分别为 2、1、0，因此 C 点在自交多边形的外部，A、B 两点在自交多边形的 内部，而且 A 点所在的区域位于 B 点所在区域的内部。3点在环内的检测平面内两个简单多边形所组成的图形有三种类型：第一 种类型是一个多边形在另一个多边形的内部，这种图形称作 环，其中面积较小的多边形叫做内环，面积较大的多边形叫 做外环。第二种类型是两个多边形的内部相交，但彼此不包 含。第三种类型是两个多边形的内部不相交。由于这类图形 的检测方法大同小异，故本文只讨论第一类图形。一个环把平面分成了三个部分，分别是内环的内部、 外环内部和内环的外部的交集、外环的外部，检测点可能位 于这三个区域当中的一个。判断检测点与环的相对位置有两 种方法，一种是分别判断检测点是否在内环和外环的内部， 然后根据相应的结果确定检测点在环的哪个区域。另一种方 法是把内环和外环看成一个整体，也就是说，将两个多边形 所有边合并在一起当作一个多边形处理，采用类似于类自 交多边形的方法。本文只讨论后一种方法，在图 4 中，A、 B、C 是检测点，按照 2.2 节的方法，A、B、C 的 F 值分别A B C2.5442.4242.4402105结论本文提出了一个新的算法，以检测一个点是否在简单 多边形、自交多边形和环内。该算法简单、可靠，并且容易 使用，检测速度快，不但能够检测简单多边形，而且还适用 于检测自交多边形和环，还可以同时检测点相对于多个多边 形的位置。参考文献:1Feito F R, J C Torres. A Urena: Orientation, simplicity, and inclusion test for planar polygonsJ. Computer & Graphics, 1995, 19(4):595-600.王文成, 吴恩华. 判断检测点是否在多边形或多面体内的新方法J. 软件学报, 2000, 11(12): 1614-1619.周培德. 计算几何算法分析与设计M. 北京: 清华大学出版社,1999.李维诗, 李江雄, 柯映林. 平面多边形方向及内外点判断的新方法J. 计算机辅助设计与图形学学报, 2000, 12(6): 405-03.234（上接第 1573 页）参考文献：Knowledge and Data Engineering Exchange Workshop C. 1999. Lavrenko V, Schmill M, Lawrie D, Ogilvie P, Jensen D, Allan J. Mining of Concurrent Text and Time Series A. Proceedings of the6th International Conference on Knowledge Discovery and DataMining C. 2000: 37-44.Keogh E, Pazzani M. Relevance feedback retrieval of time series data A. Proceedings of the 22th Annual International ACM-SIGIR Conference on Research and Development in Information RetrievalC.1999: 183-190.Keogh E, Pazzani M. An enhanced representation of time serieswhich allows fast and accurate classification, clustering and61Heckbert P S, Garland M. Survey of polygonal surface simplificationalgorithms, multi resolution Surface ModelingCourse A.on Computer724thProceedings of the International ConferenceGraphics and Interactive Techniques C. 1997.2Hunter J, McIntosh N. Knowledge-based event detection in complex time series data M. Artificial Intelligence in Medicine. Springer,1999: 271-280.Shatkay H, Zdonik S. Approximate queries and representations for large data sequences A. Proceedings of the 12th IEEE International