Indexed by: Journal paper

First Author: ZHANG JUN

Co-author: Peng Wang

Journal: Journal of Image and Graphics

Discipline: Engineering

First-Level Discipline: Information and Communications Engineering

Volume: 13

Issue: 12

Page Number: 2409-2413

Key Words: Vector data, Data organization, Polygon clipping

Date of Publication: 2008-12-11

Abstract: 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 crosspoints. Furthermore, about the data structure, the new method uses the single direction allinked 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.