论文类型：期刊论文
第一作者：张钧
合写作者：王鹏
发表刊物：中国图象图形学报
学科门类：工学
一级学科：信息与通信工程
卷号：13
期号：12
页面范围：2409-2413
关键字：矢量数据，数据组织，多边形裁剪
发表时间：2008-12-11
摘要：为实现飞行地理环境中高效地数据调用, 以满足实时性要求, 就需要对飞行地理环境中海量的栅格数据与矢量数据进行统一地数据组织。 这种统一的数据组织方法不仅要对海量的栅格数据进行矩形分块组织, 同时也要对海量的矢量数据进行矩形分块组织。 为了高效地对海量的矢量数据进行矩形分块组织, 就需要采用高效的矢量数据矩形分块裁剪算法。 现有的多边形裁剪算法中, Sutherland-Hodgeman算法和 Maillot算法对于裁剪的结果多边形有多个分离部分时都得不到正确的裁剪结果, 而 Weiler-Atherton算法、Vatti算法和 Greiner-Hormann算法却总能得到正确的裁剪结果。后 3种算法中, 虽然 Greiner-Hormann算法在空间消耗和时间消耗上都是性能最好的, 但仍不能满足实际工程的要求。为进一步提高裁剪速度, 提出了一种新的快速有效的矩形窗口的多边形裁剪算法。该新算法不仅继承了后 3种算法在连接形成裁剪的结果多边形时的优点, 而且还对 Greiner-Hormann算法在插入交点时的处理方式进行了改进, 并采用了比 Greiner-Hormann算法中应用的双向链表更为简单的单向链表的数据结构。 实验结果表明, 新算法不仅能得到正确的裁剪结果, 而且在空间消耗和时间消耗上的性能优于 Greiner-Hormann算法, 可满足实际工程的要求。