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

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