高级检索

    判定点集是否在多边形内部的算法

    AN AlGORITHM FOR DECIDING WHETHER THE SET OF POINTS IS IN THE POLYGON

    • 摘要: 本文提出了判定n个点的点集S是否落入多边形L内部的算法,该算法的复杂性为:max(O(mn),O(lnlogn))次比较和O(ln)次乘法,其中m是L的顶点数,l为S的凸包层数.

       

      Abstract: An algorithm for deciding whether the set of points is in the polygon is presented in this paper.The algorithm requires max (O(mn),O(ln log n )) comparisons and O(ln) multiplications,in which n is the number of points of the point set, m is the number of vertices of the polygon,and l is the number of layers in the convex hulls of the point set.

       

    /

    返回文章
    返回