基于凸剖分的点在多边形内的高效判定

摘要

提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.