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

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

A New Fast Polygon C lipping Algorithm for Vector Data

To achieve efficient data transfer in real time fly geometric environment(FGE),uniform data organization for massive raster and vector data in the FGE is demanded.In uniform data organization,the rectangular blocking organization is used to deal with massive raster and vector data.To efficiently organize data with rectangular block for vector data needs efficient clipping algorithm using rectangular clipping window.Sutherland-Hodgeman method and Maillot method are this kind of polygon clipping algorithms using rectangular clipping window.But Sutherland-Hodgeman method and Maillot method can not get the correct clipping results if the number of the separate parts in the result polygon is more than one.Weiler-Atherton method,Vatti method and Greiner-Hormann method can get the correct clipping results in this case.Greiner-Hormann method has the best performance in time and space consuming comparing with Weiler-Atherton method and Vatti method.A new fast polygon clipping method using rectangular clipping window is proposed in this paper.The advantage that Weiler-Atherton method,Vatti method and Greiner-Hormann method use linking to form the result polygon has been used as reference in the new method.The new method also improves the mode that Greiner-Hormann method used to insert the cross points.Furthermore,about the data structure,the new method uses the single directional linked list that is simpler than the bidirectional linked list used by Greiner-Hormann method.The experimental results show that the new method can obtain correct clipping result and it has less time and space consumption comparing with Greiner-Hormann method.