An Algorithm to Searching for the Kernel of a Simple Polygon

摘要：

In this paper, an algorithm to searching for the kernel of a simple polygon is proposed. The concave vertices of the polygon are merely deal with in the course of finding the kernel so the algorithm is efficient. The kernel of a polygon is found by cutting the polygon region using the lines passing by the edge which adjacent a concave vertex. In this course, a method is presented to determinate whether a ray intersect with a line segment by two special triangles orientations which are identified by extremity vertices sequence. Not only can the algorithm judge whether the kernel of simple polygon is empty timely, but also get the vertexes of boundaries of the kernel. Test results show the high efficiency and stability of this algorithm.

关键词： simple polygon kernel convex vertex and concave vertex extremity point

作者: Jun Zhao Xin Wang

作者单位: School of Mathematics, Physics and Software Engineering Lanzhou Jiaotong University Lanzhou, Gansu 7 Graduate schoole Lanzhou Jiaotong University Lanzhou, Gansu 730070, China

会议类型: 国际会议

会议名称: The 2010 International Conference on Computer Application and System Modeling(2010计算机应用与系统建模国际会议 ICCASM 2010)

会议地点: 太原

会议语种:英文

页码: 455-457

在线出版日期: 2010-10-22（万方平台首次上网日期，不代表论文的发表时间）