Clipping polygons based on a scan of a storage grid
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, comprising:
storing line segments, defining a set of polygons, in association with corresponding tiles of a storage grid;
generating clipped polygons that fit within a clip region by clipping the set of polygons using a set of the line segments identified by a scan of the storage grid, the scan retrieving the set of the line segments associated with scanned tiles and terminating at a tile intersecting an edge of the clip region; and
providing the clipped polygons for presentation.
2. The computer-implemented method of claim 1 , wherein each of the corresponding tiles of the storage grid is associated with a corresponding key indexed by minimum coordinates of the tile.
3. The computer-implemented method of claim 1 , wherein, for each vertex failing inside a particular tile of the storage grid, the storage grid assigns to the particular tile a first of the line segments entering the vertex and a second of the line segments exiting the vertex.
4. The computer-implemented method of claim 1 , wherein the storage grid assigns each of the line segments twice, once for a first vertex the line segment enters and once for a second vertex the line segment exits.
5. The computer-implemented method of claim 1 , wherein the scan of the storage grid retrieves the set of the line segments associated with a first set of the corresponding tiles falling within the clip region and a second set of the corresponding tiles intersecting a boundary of the clip region.
6. The computer-implemented method of claim 1 , wherein the scan of the storage grid comprises a plurality of forward scans terminating at a set of the corresponding tiles intersecting the edge of the clip region.
7. The computer-implemented method of claim 1 , wherein generating the clipped polygons further comprises:
identifying intersections between the clip region and the line segments; and
clipping the set of polygons using the set of the line segments and the intersections.
8. The computer-implemented method of claim 1 , wherein the clipped polygons correspond to a first subset of the polygons that intersect with the clip region and a second subset of the polygons that surround the clip region, the method further comprising providing the clipped polygons and a third subset of the polygons that fit within the clip region for presentation.
9. The computer-implemented method of claim 1 , wherein the clip region corresponds to a moveable viewport, the method further comprising updating the clipped polygons upon a repositioning of the moveable viewport.
10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method comprising:
storing line segments, defining a set of polygons, in association with corresponding tiles of a storage grid;
generating clipped polygons that fit within a clip region by clipping the set of polygons using a set of the line segments identified by a scan of the storage grid, the scan retrieving the set of the line segments associated with scanned tiles and terminating at a tile intersecting an edge of the clip region; and
providing the clipped polygons for presentation.
11. The non-transitory computer-readable storage medium of claim 10 , wherein each of the corresponding tiles of the storage grid is associated with a corresponding key indexed by minimum coordinates of the tile.
12. The non-transitory computer-readable storage medium of claim 10 , wherein, for each vertex failing inside a particular tile of the storage grid, the storage grid assigns to the particular tile a first of the line segments entering the vertex and a second of the line segments exiting the vertex.
13. The non-transitory computer-readable storage medium of claim 10 , wherein the storage grid assigns each of the line segments twice, once for a first vertex the line segment enters and once for a second vertex the line segment exits.
14. The non-transitory computer-readable storage medium of claim 10 , wherein the scan of the storage grid retrieves the set of the line segments associated with a first set of the corresponding tiles falling within the clip region and a second set of the corresponding tiles intersecting a boundary of the clip region.
15. The non-transitory computer-readable storage medium of claim 10 , wherein the scan of the storage grid comprises a plurality of forward scans terminating at a set of the corresponding tiles intersecting the edge of the clip region.
16. The non-transitory computer-readable storage medium of claim 10 , wherein generating the clipped polygons further comprises:
identifying intersections between the clip region and the line segments; and
clipping the set of polygons using the set of the line segments and the intersections.
17. The non-transitory computer-readable storage medium of claim 10 , wherein the clipped polygons correspond to a first subset of the polygons that intersect with the clip region and a second subset of the polygons that surround the clip region, the method further comprising providing the clipped polygons and a third subset of the polygons that fit within the clip region for presentation.
18. The non-transitory computer-readable storage medium of claim 10 , wherein the clip region corresponds to a moveable viewport, the method further comprising updating the clipped polygons upon a repositioning of the moveable viewport.
19. A computing system comprising:
at least one processor and at least one associated memory; and
a display mechanism configured to execute on the at least one processor, wherein the display mechanism is configured to:
store line segments, defining a set of polygons, in association with corresponding tiles of a storage grid;
generate clipped polygons that fit within a clip region by clipping the set of polygons using a set of the line segments identified by a scan of the storage grid, the scan retrieving the set of the line segments associated with scanned tiles and terminating at a tile intersecting an edge of the clip region; and
provide the clipped polygons for presentation.
20. The computing system of claim 19 , wherein the clip region corresponds to a moveable viewport, wherein the display mechanism is configured to update the clipped polygons upon a repositioning of the moveable viewport.