摘要
提出一种检测点与多边形关系的新算法,通过扫描建立适合查找的多边形层次结构。检测时,运用二分查找,找到与检测点相关的边,通过该点与相关边的关系判断出点与多边形的关系。实验结果表明,该方法简单有效,有较高的检测速度。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2004年第20期86-88,共3页
Computer Engineering
关键词
点
简单多边形
包含检测
Point
Simple polygon
Inclusion test