求解简单多边形核的新算法

利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对多边形的核为空集的情况加以报告.在多边形有核的情况下,裁剪过程不断更新包含核的多边形,快速求解得到包含核的凸多边形,从而可以采用凸多边形的线裁剪算法来加速求核计算.新的求核算法在快速判断出空核和提高求核速度方面都有较大改进.

A new algorithm for finding the kernel of a simple polygon

By using the position information of concave vertices, a new algorithm for finding the kernel of a simple polygon was proposed,which could automatically select concave vertex to clip against polygon to obtain the kernel.While the selected concave vertex was clipping,the unselected vertices were separated into two collections,one was composed of concave vertices for further separation,another was composed of concave vertices for clipping against convex polygon containing kernel later.If the kernel of the simple polygon was null,the algorithm could report it as soon as possible by checking the existence of the kernel step by step.Otherwise,the algorithm could find the convex polygon containing kernel quickly so that the remaining concave vertices might use line clipping algorithm against convex polygon for speedup.