用VC++实现的任意多边形裁剪算法 |
| |
引用本文: | 李海姣,张维锦.用VC++实现的任意多边形裁剪算法[J].计算机应用,2005,25(Z1):421-423. |
| |
作者姓名: | 李海姣 张维锦 |
| |
作者单位: | 华东交通大学,土木建筑学院,江西,南昌,330013 |
| |
摘 要: | 提出了一个用VC++语言实现的凸多边形、凹多边形,也可以是带内环的多边形的裁剪算法,可以求上述多边形的"交"、"并"以及"差".首先,该算法使用VC++支持的CObList类和CArray类的对象存储数据,具有占用内存空间少及处理速度快的特点;再通过算法和数据结构的设计不仅使得多边形顶点可按顺时针方向或逆时针方向输入,而且减少了求解过程中对多边形顶点数据的遍历次数;基于判断和计算交点是裁剪算法的主要工作,文中引入了求交前的预处理,避免了大量不必要的求交,降低了算法的时间复杂度.最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理.
|
关 键 词: | 多边形裁剪 VC++数据结构 凸多边形 凹多边形 交点计算预处理 |
文章编号: | 1001-9081(2005)12Z-0421-03 |
修稿时间: | 2005年3月25日 |
本文献已被 CNKI 万方数据 等数据库收录! |
|