基于方向因子和方向边的多边形内外点判断算法

Algorithm of polygon point in-out test based on direction factor and direction edge

本文在概述已有多边形内外点判断算法的基础上,提出了方向因子和方向边的概念,并利用方向因子和方向边,设计了一种判断点在多边形内外的新算法。该方法首先找出点的方向边,再计算该点与其方向边组成的三角形的方向因子,然后利用计算的方向因子来判断点与多边形的位置关系,其可以有效地解决射线法中的临界位置问题。实验结果表明,该方法易于理解,计算简单,具有较高的可靠性、稳定性和执行效率。

Based on summarizing present algorithms of polygon point in-out test, the direction factor and direction edge were proposed in this paper, and a new algorithm of judging points in or out of polygon was designed using direction factor and direction edge. In this method the direction edge of judged point was found out firstly, then the direction factor of triangle composed of judged point and direction edge was calculated. Lastly, the relation of judged point and the polygon was judged with the calculated direction factor. This method could efficiently solve the critical position problem of the ray method. Experimental results showed that this method was compre hensible, simple, stable, reliable and efficient.