基于轨迹计算的临界多边形求解算法

摘要：

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题.该算法的基本原理是:1)求解多边形顶点相对于另一多边形的轨迹线;2)求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形.该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度.

关键词：临界多边形、轨迹线、线段索引、排样

所属期刊栏目：18

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

资助基金：中国科学院资助项目60573146;国家科技攻关项目2003AA411310

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

页数：共7页

页码：1123-1129