Abstract:

There are three main problems in line clip:reducing the number of segments intersection,reducing the time complexity for computation property of intersections and determining whether nonintersection lines is in clip polygons.This paper presents an improved line clip algorithm against general polygon window.The algorithm uses RTree and Cell structures to calculate segment intersections between segments in lines and segments in polygon edges.Then,based on uniform subdivision,a method named local radial is introduced in order to reduce the time complexity for pointinpolygon.The algorithm has three improvements.Firstly,segmentintersections of two spatial index structures can be calculated simultaneously.Secondly,a ‘local radial method’ is presented to reduce the time complexity for computation property of intersections,whose time complexity is,and the method avoids judging the orientation of clip polygons.Finally,the algorithm can be used in the clipping window that is general polygon.

Key words: R-Tree；cell index；clipping line；local radial