论文部分内容阅读
提出一种基于点集排序，逐行（或逐列）扫描平面点集S，判定点集S中的点是否在多边形L内部的算法，该算法的时间复杂性在最坏情况下为：max(O(n log n),O(km log m)次比较和O（km)次乘法，其中n为点集S的点数，m为多边形L的顶点数，k=min(u,v)，其中u,v分别为点集S中的点分布的行数和列数，该算法思路简单，易实现，且在一般情况下，效率比已有的算法高。