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.

主权项

1. A computer-implemented method for displaying a set of polygons, comprising:
obtaining a clip rectangle that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments; using a horizontal index to determine intersections between vertical borders of the clip rectangle and line segments in the set of line segments; using a vertical index to determine intersections between horizontal borders of the clip rectangle and line segments in the set of line segments; using the determined intersections to clip polygons in the set of polygons that intersect the clip rectangle to form clipped polygons that fit within the clip rectangle; and transferring the clipped polygons and also unclipped polygons that fit completely within the clip rectangle to a device to be presented to a user as the view into the set of polygons.