高级检索

判断简单多边形的核是否为空的一个快速算法

A Fast Algorithm to Determine Whether the Kernel of Simple Polygon is Empty

  • 摘要: 简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界.文中考查了简单多边形的核在构成方面的性质,结合已有结果,提出了一个算法.该算法能快速地判断简单多边形是否有核,有核时可以方便地求出核中一个顶点.对算法进行简单扩展,可以求得核中一边及完整的核.给出的算法容易理解,便于实现,可以广泛地应用于一些涉及可见性的问题及许多其它问题中.

     

    Abstract: The kernel of simple polygon is a point set within the polygon where all boundaries of polygon are visible from any point within the kernel.A new algorithm based on the conclusions available in references is introduced which can quickly determine whether the kernel of simple polygon is empty,and easily find a vertex of kernel when the kernel is not empty.Through uncomplicated generalization the algorithm can find an edge of kernel and then the kernel itself.It is comprehensible and practical to implement.

     

/

返回文章
返回