于凯，俞孟蕻

（江苏科技大学 计算机科学与工程学院，江苏 镇江 212003）

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

于凯，俞孟蕻

（江苏科技大学 计算机科学与工程学院，江苏 镇江 212003）

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

凸多边形；二分法；包含测试；递归分割

多边形内外点判别算法也叫做点的包含测试（point-inpolygon test），目的是测试一个点是否在多边形内［1］。该算法在计算机图形学、模式识别、地理信息系统等众多领域中有着广泛的应用。例如，当工业上需要判断矿井是否在指定的区域内，或者游戏中需要判断点击的位置是否在指定的区域内。解决此类问题首先通过仿真，将指定区域建模成多边形，而矿井或者点击的位置就是待测点，通过多边形内外点判别算法判定此待测点是否在该多边形内，从而确定矿井或者点击位置是否在指定区域内。算法的平均时间复杂度也就是判定待测点是否在多边形内的平均耗时，耗时减少，会使得游戏的体验更好，工业上工程的进度更快。……