| 确定任意简单多边形平移时碰撞部位的扫描算法 |
| |
| 引用本文： | 曲吉林.确定任意简单多边形平移时碰撞部位的扫描算法[J].计算机学报,2000,23(7):692-698. |
| |
| 作者姓名： | 曲吉林 |
| |
| 作者单位： | 山东财政学院计算机科学与工程系,济南,250014 |
| |
| 基金项目： | 财政部“九五”规划课题基金!( 960 75 )资助 |
| |
| 摘 要： | 设Ｐ和Ｑ为平面内任意两个互不相交的简单多边形，若Ｐ沿方向ｄ平移时与Ｑ碰撞，采用平面扫描法，通过提取多边形的单调链，给出了求其碰撞部位的算法，最坏情况下，算法的时间复杂性为Ｏ（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ），其中ｎ和ｍ分别为多边形Ｐ与Ｑ的边数，与现有的算法相比，降低了时间复杂性。
|
| 关 键 词： | 计算几何 简单多边形 碰撞部位 算法 |
| 修稿时间： | 1999-03-31 |
Plane-Sweep Algorithm for Determining the Colliding Parts of Simple Polygons |
| |
| QU Ji-Lin.Plane-Sweep Algorithm for Determining the Colliding Parts of Simple Polygons[J].Chinese Journal of Computers,2000,23(7):692-698. |
| |
| Authors: | QU Ji-Lin |
| |
| Abstract: | Let P and Q be two nonintersecting simple polygons in the plane,if P translates in indirection d and collides with Q , the touch parts of them can be found by using the plane sweep technique. The plane sweep algorithm in this paper runs in time O((m n) log (m n) ) in worst presented case,where n and m are the edge number of polygons P and Q . |
| |
| Keywords: | computational geometry simple polygon colliding parts algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
