Finding the kernel of planar shapes

摘要

The kernel of a planar shape is the locus of interior points from which all boundary points can be seen. This paper discusses an algorithm for determining the kernel of a planar shape. To find the kernel we could first ask what is the interior region seen from each boundary point. The intersection of these regions corresponding to all boundary points is, by definition, the kernel. Since it would be quite impractical to implement the kernel-finding algorithm just described, we should first determine interior regions that are jointly seen from boundary points that belong to boundary fragments. Based on this idea, a practical algorithm can be designed. It is an efficient way to intersect regions in the plane induced by suitably defined boundary fragments and determined via visibility constraints. It is shown that for a wide class of planar shapes, the resulting procedure is computationally efficient. In particular, for the case of a polygon with N edges, the algorithm has a time complexity of O(N) and hence is optimal. It is usually more efficient and in the worst case at least as good as a previously proposed O(N) algorithm.