基于顶点凸凹性多边形的核的算法  

Algorithm to Calculate the Kernel of Simple Polygon Based on Convexo-concave Features of Vertices

作　　者：段鹏[1] 莫亚林[1] 王进[2] 

机构地区：[1]河南理工大学机械与动力工程学院,河南焦作454000 [2]浙江大学计算机辅助设计与图形学(CAD&CG)国家重点实验室,杭州310027

出　　处：《科技导报》2008年第13期36-39,共4页Science & Technology Review

摘　　要：简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。The kernel of a simple polygon is a point set in interior of this polygon, in which all boundaries of this polygon are visible from any point. A new algorithm based on convexo-concave features of vertices of the polygon is proposed, which can be used to judge the existence of the kernel and obtain the point set of the kernel. Utilizing a part of the adjacent edges of concave vertices, the initial kernel is separated which is composed of convex vertices of the polygon, and then the vertices coordinates of the kernel can quickly be calculated. The given algorithm is easy to realize, and can be widely applied to other visibility problems, such as camera orientation and so on.

关 键 词：多边形 核 顶点凸凹性 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]