Clipping polygons to fit within a clip region

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;

looking up, from a storage grid, tiles that intersect the clip region to identify endpoints of a subset of line segments in the set of line segments for which the endpoints fall within the tiles;

using the subset of line segments 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.

2. The computer-implemented method of claim 1 , wherein looking up the tiles comprises a forward scan of the storage grid that terminates when reaching a tile intersecting an edge of the clip region.

3. The computer-implemented method of claim 1 , further comprising determining intersections between edges of the clip region and line segments in the set of line segments using the storage grid.

4. The computer-implemented method of claim 1 , further comprising determining intersections between edges of the clip region and line segments in the set of line segments using the storage grid by:

maintaining the storage grid by keeping track of the set of line segments with respect to a tiled grid, wherein the tiled grid divides a region occupied by the set of polygons into a set of tiles and wherein each entry in the storage grid identifies line segments with endpoints that fall within a corresponding tile in the tiled grid;

identifying relevant tiles in the set of tiles that intersect or are contained within the clip region;

looking up the relevant tiles in the storage grid to identify line segments having endpoints that fall within the relevant tiles; and

winnowing the set of line segments to comprise only the identified line segments.

5. The computer-implemented method of claim 1 , further comprising providing to the device, with the clipped polygons, polygons of the set of polygons that surround the clip region.

6. The computer-implemented method of claim 1 , wherein using the subset of line segments to clip polygons comprises, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

inserting intersections between the polygon and the clip region into the polygon list; and

generating one or more clipped polygons based on the polygon list.

7. The computer-implemented method of claim 1 , wherein using the subset of line segments to clip polygons comprises, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

maintaining a clip region list including vertices of the clip region;

inserting intersections between the polygon and the clip region into the polygon list and into the clip region list; and

generating one or more clipped polygons based on navigating back and forth between the polygon list and the clip region list.

8. The computer-implemented method of claim 1 , wherein the set of polygons defines regions of a choropleth map wherein each region is shaded, patterned or colored in proportion to a number of data points that fall into the region.

9. The computer-implemented method of claim 1 , wherein the method further comprises:

obtaining data associated with the set of polygons from a set of events containing raw data associated with a time stamp; and

providing the associated data to the device to facilitate displaying the set of polygons.

10. The computer-implemented method of claim 1 , wherein the method further comprises:

receiving a query to be processed;

using a data-retrieval specification generated from the query to obtain data associated with the set of polygons from a set of events containing raw data associated with a time stamp; and

providing the associated data to the device to facilitate displaying the set of polygons.

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;

looking up, from a storage grid, tiles that intersect the clip region to identify endpoints of a subset of line segments in the set of line segments for which the endpoints fall within the tiles;

using the subset of line segments 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.

12. The non-transitory computer-readable storage medium of claim 11 , wherein looking up the tiles comprises a forward scan of the storage grid that terminates when reaching a tile intersecting an edge of the clip region.

13. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises determining intersections between edges of the clip region and line segments in the set of line segments using the storage grid.

14. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises determining intersections between edges of the clip region and line segments in the set of line segments using the storage grid by:

maintaining the storage grid by keeping track of the set of line segments with respect to a tiled grid, wherein the tiled grid divides a region occupied by the set of polygons into a set of tiles and wherein each entry in the storage grid identifies line segments with endpoints that fall within a corresponding tile in the tiled grid;

identifying relevant tiles in the set of tiles that intersect or are contained within the clip region;

looking up the relevant tiles in the storage grid to identify line segments having endpoints that fall within the relevant tiles; and

winnowing the set of line segments to comprise only the identified line segments.

15. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises providing to the device, with the clipped polygons, polygons of the set of polygons that surround the clip region.

16. The non-transitory computer-readable storage medium of claim 11 , wherein using the subset of line segments to clip polygons comprises, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

inserting intersections between the polygon and the clip region into the polygon list; and

generating one or more clipped polygons based on the polygon list.

17. The non-transitory computer-readable storage medium of claim 11 , wherein using the subset of line segments to clip polygons comprises, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

maintaining a clip region list including vertices of the clip region;

inserting intersections between the polygon and the clip region into the polygon list and into the clip region list; and

generating one or more clipped polygons based on navigating back and forth between the polygon list and the clip region list.

18. The non-transitory computer-readable storage medium of claim 11 , wherein the set of polygons defines regions of a choropleth map wherein each region is shaded, patterned or colored in proportion to a number of data points that fall into the region.

19. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises:

obtaining data associated with the set of polygons from a set of timestamped events containing raw data; and

providing the associated data to the device to facilitate displaying the set of polygons.

20. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises:

receiving a query to be processed;

using a data-retrieval specification generated from the query to obtain data associated with the set of polygons from a set of events containing raw data associated with a time stamp; and

providing the associated data to the device to facilitate displaying the set of polygons.

21. A system that displays a set of polygons, 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:

obtain 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;

look up, from a storage grid, tiles that intersect the clip region to identify endpoints of a subset of line segments in the set of line segments for which the endpoints fall within the tiles;

use the subset of line segments 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.

22. The system of claim 21 , wherein the display mechanism is configured to look up the tiles by performing a forward scan of the storage grid that terminates when reaching a tile intersecting an edge of the clip region.

23. The system of claim 21 , wherein the display mechanism is configured to determine intersections between edges of the clip region and line segments in the set of line segments using the storage grid.

24. The system of claim 21 , wherein the display mechanism is configured to determine intersections between edges of the clip region and line segments in the set of line segments using the storage grid by:

maintaining the storage grid by keeping track of the set of line segments with respect to a tiled grid, wherein the tiled grid divides a region occupied by the set of polygons into a set of tiles and wherein each entry in the storage grid identifies line segments with endpoints that fall within a corresponding tile in the tiled grid;

identifying relevant tiles in the set of tiles that intersect or are contained within the clip region;

looking up the relevant tiles in the storage grid to identify line segments having endpoints that fall within the relevant tiles; and

winnowing the set of line segments to comprise only the identified line segments.

25. The system of claim 21 , wherein the display mechanism is configured to provide to the device, with the clipped polygons, polygons of the set of polygons that surround the clip region.

26. The system of claim 21 , wherein the display mechanism is configured to use the subset of line segments to clip polygons by, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

inserting intersections between the polygon and the clip region into the polygon list; and

generating one or more clipped polygons based on the polygon list.

27. The system of claim 21 , wherein the display mechanism is configured to use the subset of line segments to clip polygons by, for each polygon in a set of polygons intersected by the clip region:

maintaining a polygon list of vertices of the polygon comprising corresponding endpoints of the subset of line segments;

maintaining a clip region list including vertices of the clip region;

inserting intersections between the polygon and the clip region into the polygon list and into the clip region list; and

generating one or more clipped polygons based on navigating back and forth between the polygon list and the clip region list.

28. The system of claim 21 , wherein the set of polygons defines regions of a choropleth map wherein each region is shaded, patterned or colored in proportion to a number of data points that fall into the region.

29. The system of claim 21 , wherein the display mechanism is configured to:

obtain data associated with the set of polygons from a set of events containing raw data associated with a time stamp; and

provide the associated data to the device to facilitate displaying the set of polygons.

30. The system of claim 21 , wherein the display mechanism is configured to:

receive a query to be processed;

use a data-retrieval specification generated from the query to obtain data associated with the set of polygons from a set of events containing raw data associated with a time stamp; and

provide the associated data to the device to facilitate displaying the set of polygons.