基于凸片段分解和格网的点在多边形中的可见边检测

摘要：

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算；然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.

关键词：多边形、可见边、凸片段、格网、并行计算

所属期刊栏目：25

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金60833007,60928006;中国科学院知识创新工程领域前沿项目

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

页数：共7页

页码：1114-1120