点与简单多边形关系的新算法

New Algorithm for Simple Polygon and Point

提出一种检测点与多边形关系的新算法,通过扫描建立适合查找的多边形层次结构。检测时,运用二分查找,找到与检测点相关的边,通过该点与相关边的关系判断出点与多边形的关系。实验结果表明,该方法简单有效,有较高的检测速度。

A new algorithm is presented to do the inclusion test for simple polygon. A preprocessing is used to establish a hierarchical data structure for binary search. The algorithm searches correlative edges for the point and then examines the relationship between the point and the polygon. The experiment results show that the algorithm is simple, efficient and fast.