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

简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。

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

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.