Efficient polygon-clipping technique to reduce data transfer requirements for a viewport

摘要

A system that displays a set of polygons is described. This system obtains a set of line segments that defines the set of polygons. The system forms a horizontal index that keeps track of where line segments vertically project onto a horizontal reference line and similarly forms a vertical index for horizontal projections onto a vertical reference line. The system obtains a clip rectangle that defines a view into the set of polygons and uses the horizontal and vertical indexes to determine intersections between borders of the clip rectangle and line segments in the set of line segments. Next, the system uses the determined intersections to clip polygons in the set of polygons that intersect the clip rectangle. Finally, the system transfers the clipped polygons, and also unclipped polygons that fit completely within the clip rectangle, to a display device that displays the view into the set of polygons.