Shrinking Regular Bounding Box Filter for Line Segment Intersection Problem

Line segment intersection is one of the most important problems in computational geometry.Plane sweep algorithm is commonly used for this problem with bounding box(BB) filter.However,it is ignored in this filter that the effective part of segment will be shrunk with sweep line moving,so both candidate segment pairs and computational costs are increased.A shrinking regular BB filter is proposed as a strict one,in which the BB is shrunk after the slope of main diagonal of BB is quantified.Experimental results show that the quantities of candidate segment pairs and computation are reduced by on average 16% and 14% respectively.