摘要： 提出了一种判断点是否在多边形内的新方法，该方法由两部分组成：(1)预处理，即先求出多边形的所有极点；(2)检测，即采用折半查找找到相关点和相关边，根据被检测线穿过的相关边数来判断检测点是否在多边形内。该方法解决了射线法无法解决的奇异情况，且在检测过程中不必处理多边形的所有边。实验结果证明，该方法简单、易实现、快速。

关键词: 多边形, 射线法, 计算几何

Abstract: This paper puts forward a new method for detecting whether a point is within a polygon. The method is composed of two sections, namely, pretreatment for the obtainment of all forked points of the polygon P and detection for finding out related points and edges by using binary search, according to the parity of the number of the related edge which detection line passes through to test wheter a point is within tge polygon. The method can deal with abnormal conditions which ray-crossing algorithm can not and need not handle all edges of polygon in the detection process. Experimental results show that the method is robust and efficient in computation.

Key words: polygon, ray-crossing, computational geometry

中图分类号: 

• TP391.41