Efficient polygon-clipping technique to reduce data transfer requirements for a viewport
First Claim
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.
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.
26 Citations
30 Claims
-
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. - 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 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. - 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 rectangle that defines a view into the set of polygons, wherein the set of polygons is defined by a set of line segments; uses a horizontal index to determine intersections between vertical borders of the clip rectangle and line segments in the set of line segments; uses a vertical index to determine intersections between horizontal borders of the clip rectangle and line segments in the set of line segments; uses 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 transfers 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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
-
Specification