一种新的矢量数据多边形的快速裁剪算法

摘要

为实现飞行地理环境中高效的数据调用,以满足实时性要求,就需要对飞行地理环境巾海量的栅格数据与矢量数据进行统一的数据组织.这种统一的数据组织方法不仅要对海量的栅格数据进行矩形分块组织,同时也要对海量的矢量数据进行矩形分块组织.为了高效地对海量的矢量数据进行矩形分块组织,就需要采用高效的矢量数据矩形分块裁剪算法.现有的多边形裁剪算法中,Sutherland-Hodgeman 算法和Maillot算法对于裁剪的结果多边形有多个分离部分时都得不到正确的裁剪结果,而Weiler-Atherton算法、Vatti算法和Greiner-Hormann算法却总能得到正确的裁剪结果.后3种算法中,虽然Greiner-Hormann算法在空间消耗和时间消耗上都是性能最好的,但仍不能满足实际工程的要求.为进一步提高裁剪速度,提出了一种新的快速有效的矩形窗口的多边形裁剪算法.该新算法不仅继承了后3种算法在连接形成裁剪的结果多边形时的优点,而且还对Greiner-Hormann算法在插入交点时的处理方式进行了改进,并采用了比Greiner-Hormann算法中应用的双向链表更为简单的单向链表的数据结构.实验结果表明,新算法不仪能得到正确的裁剪结果,而且在空间消耗和时间消耗上的性能优于Greiner-Hormann算法,可满足实际工程的要求.