PIP indexing technique to clip polygons in a clipping region
First Claim
1. A computer-implemented method for displaying a set of polygons, comprising:
- obtaining a clip region that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments;
using a PIP index to determine intersections between borders of the clip region and line segments in the set of line segments;
looking up tiles of a storage grid that intersect with the clip region to identify endpoints of line segments in the set of line segments for which the endpoints fall within the tiles;
using the determined intersections and the identified endpoints to clip polygons in the set of polygons that intersect the clip region to form clipped polygons that fit within the clip region; and
providing the clipped polygons to a device for a presentation of the view into the set of polygons.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
62 Citations
30 Claims
-
1. A computer-implemented method for displaying a set of polygons, comprising:
-
obtaining a clip region that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments; using a PIP index to determine intersections between borders of the clip region and line segments in the set of line segments; looking up tiles of a storage grid that intersect with the clip region to identify endpoints of line segments in the set of line segments for which the endpoints fall within the tiles; using the determined intersections and the identified endpoints to clip polygons in the set of polygons that intersect the clip region to form clipped polygons that fit within the clip region; and providing the clipped polygons to a device for a presentation of the view into the set of polygons. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for displaying a set of polygons, the method comprising:
-
obtaining a clip region that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments; using a PIP index to determine intersections between borders of the clip region and line segments in the set of line segments; looking up tiles of a storage grid that intersect with the clip region to identify endpoints of line segments in the set of line segments for which the endpoints fall within the tiles; using the determined intersections and the identified endpoints to clip polygons in the set of polygons that intersect the clip region to form clipped polygons that fit within the clip region; and providing the clipped polygons to a device for a presentation of the view into the set of polygons. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A system that displays a set of polygons, comprising:
-
at least one processor and at least one associated memory; and a display mechanism that executes on the at least one processor, wherein during operation, the display mechanism; obtains a clip region that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments; uses a PIP index to determine intersections between borders of the clip region and line segments in the set of line segments; looks up tiles of a storage grid that intersect with the clip region to identify endpoints of line segments in the set of line segments for which the endpoints fall within the tiles; uses the determined intersections and the identified endpoints to clip polygons in the set of polygons that intersect the clip region to form clipped polygons that fit within the clip region; and provide the clipped polygons to a device for a presentation of the view into the set of polygons. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
-
Specification