基于二分法的凸多边形内外点判别算法

Point inclusion test method based on dichotomy

多边形内外点判定算法是图形学的基础型算法,目的是判定待测点是否在指定的多边形之内。由于传统的射线法与角度和法效率偏低,平均时间复杂度为O(n),当多边形边数或者待测点个数较多时,算法耗时较高。因此本文分析了传统的射线法与角度和法的缺点;提出了基于二分法的凸多边形内外点判别算法;最后进行实验仿真,证明该算法的平均时间复杂度为O(n/2)。该算法通过递归的分割凸多边形,判断待测点与分割线的相对位置,最终转化为三角形内外点的判别,具有快速、稳定、准确的优势。

Point inclusion test is a basic algorithm of computer graphics, it＆#39;s purpose is to determine whether a test point is in the specific polygon. Traditional ray-crossing method and angle algorithm have relative low efficiency, their average time complexity are O（n）. So, if a polygon has a great many edges or test points, these algorithms will take much more time. This paper analyses the shortcomings of traditional ray-crossing method and angle algorithm, then proposes an efficient point-in-polygon test method based on dichotomy. At last, this paper uses many experiments to show that the average time complexity of this algorithm is O（n/2）.By partitioning convex polygon recursively and judging the relative position between points and the line, this method eventually translate this problem into judging the relative position between triangle and points. Compared with the classic algorithms, such as the ray crossing method or the angle algorithm, this algorithm not only have the advantage rapid and stable, also can give which triangle region the points locate in.