Simplified point-in-polygon test for processing geographic data

1. A computer-implemented method for displaying geographic data, comprising:

receiving a query to be processed, wherein the query is associated with a set of geographic regions;

extracting a set of data points from raw machine data;

for each data point in the set of data points, performing simplified point in polygon (PIP) tests to determine zero or more geographic regions, in the set of geographic regions, that bound the data point, the simplified PIP tests using a coordinate of the data point to look up previously identified segments of the set of geographic regions that would intersect parallel rays cast from points in an identified range within which the coordinate falls; and

causing display of at least a subset of the set of geographic regions based on counts of the data points determined to fall within corresponding geographic regions.

2. The computer-implemented method of claim 1 , wherein the method further comprises identifying the previously identified segments of the set of geographic regions that would intersect parallel rays cast from the points in the identified range by, prior to receiving the query:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises segments that define a border of the polygon, and wherein each segment is defined by coordinates for two endpoints of the segment;

casting parallel rays from the endpoints of the segments of the set of polygons onto a reference line to form intersection points with the reference line and corresponding ranges; and

for each of the ranges, identifying the segments of the set of geographic regions that would intersect parallel rays cast from points in the range.

3. The computer-implemented method of claim 1 , wherein the simplified PIP tests comprise, for each data point in the set of data points, performing a crossing number (CN) operation, for each of the geographic regions in the set of geographic regions, by counting intersections between a test ray cast from the data point and the previously identified segments.

4. The computer-implemented method of claim 1 , wherein causing display of at least a subset of the set of geographic regions includes causing display of a choropleth map wherein each of the geographic regions is shaded, patterned or colored in proportion to a corresponding one of the counts for the geographic region.

5. The computer-implemented method of claim 1 , further comprising building an index that identifies sorted ranges and corresponding sets of the previously identified segments.

6. The computer-implemented method of claim 1 , further comprising building an index that identifies sorted ranges and corresponding sets of the previously identified segments, wherein the index identifies the sorted ranges and corresponding sets of the previously identified segments using a point data structure with an order field.

7. The computer-implemented method of claim 1 , wherein the previously identified segments are identified from an index that stores intersection lists modulo k.

8. The computer-implemented method of claim 1 , wherein the previously identified segments are identified from an index that stores intersection lists modulo k, and wherein the identified segments are identified from the index by:

identifying a nearest intersection list; and

updating the nearest intersection list to the identified range at runtime.

9. The computer-implemented method of claim 1 , wherein the previously identified segments are identified from an index that stores intersection lists modulo k, and wherein the previously identified segments are identified from the index by:

identifying a nearest intersection list using a binary search; and

updating the nearest intersection list to the identified range at runtime.

10. The computer-implemented method of claim 1 , wherein the query is received from a user through a user interface.

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 geographic data, the method comprising:

receiving a query to be processed, wherein the query is associated with a set of geographic regions;

extracting a set of data points from raw machine data;

for each data point in the set of data points, performing simplified point in polygon (PIP) tests to determine zero or more geographic region,s in the set of geographic regions, that bound the data point, the simplified PIP tests using a coordinate of the data point to look up previously identified segments of the set of geographic regions that would intersect parallel rays cast from points in an identified range within which the coordinate falls; and

causing display of at least a subset of the set of geographic regions based on counts of the data points determined to fall within corresponding geographic regions.

12. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises identifying the previously identified segments of the set of geographic regions that would intersect parallel rays cast from the points in the identified range by, prior to receiving the query:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises segments that define a border of the polygon, and wherein each segment is defined by coordinates for two endpoints of the segment;

casting parallel rays from the endpoints of the segments of the set of polygons onto a reference line to form intersection points with the reference line and corresponding ranges; and

for each of the ranges, identifying the segments of the set of geographic regions that would intersect parallel rays cast from points in the range.

13. The non-transitory computer-readable storage medium of claim 11 , wherein the simplified PIP tests comprise, for each data point in the set of data points, performing a crossing number (CN) operation, for each of the geographic regions in the set of geographic regions, by counting intersections between a test ray cast from the data point and the previously identified segments.

14. The non-transitory computer-readable storage medium of claim 11 , wherein causing display of at least a subset of the set of geographic regions includes causing display of a choropleth map wherein each of the geographic regions is shaded, patterned or colored in proportion to a corresponding one of the counts for the geographic region.

15. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises building an index that identifies sorted ranges and corresponding sets of the previously identified segments.

16. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises building an index that identifies sorted ranges and corresponding sets of the previously identified segments, wherein the index identifies the sorted ranges and corresponding sets of the previously identified segments using a point data structure with an order field.

17. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises identifying the previously identified segments from an index that stores intersection lists modulo k.

18. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises identifying the previously identified segments from an index that stores intersection lists modulo k by:

identifying a nearest intersection list; and

updating the nearest intersection list to the identified range at runtime.

19. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises identifying the previously identified segments from an index that stores intersection lists modulo k by:

identifying a nearest intersection list using a binary search; and

updating the nearest intersection list to the identified range at runtime.

20. The non-transitory computer-readable storage medium of claim 11 , wherein method further comprises receiving the query from a user through a user interface.

21. A system that displays geographic data, comprising:

at least one processor and at least one associated memory; and

a query-processing mechanism configured to execute on the at least one processor to perform operations comprising:

receive a query to be processed, wherein the query is associated with a set of geographic regions;

extract a set of data points from raw machine data;

for each data point in the set of data points, perform simplified point in polygon (PIP) tests to determine zero or more geographic regions, in the set of geographic regions, that bound the data point, the simplified PIP tests using a coordinate of the data point to look up previously identified segments of the set of geographic regions that would intersect parallel rays cast from points in an identified range within which the coordinate falls; and

cause display of at least a subset of the set of geographic regions based on counts of the data points determined to fall within corresponding geographic regions.

22. The system of claim 21 , wherein the query-processing mechanism is further configured to identify the previously identified segments of the set of geographic regions that would intersect parallel rays cast from the points in the identified range by, prior to receiving the query:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises segments that define a border of the polygon, and wherein each segment is defined by coordinates for two endpoints of the segment;

casting parallel rays from the endpoints of the segments of the set of polygons onto a reference line to form intersection points with the reference line and corresponding ranges; and

for each of the ranges, identifying the segments of the set of geographic regions that would intersect parallel rays cast from points in the range.

23. The system of claim 21 , wherein the simplified PIP tests comprise, for each data point in the set of data points, performing a crossing number (CN) operation, for each of the geographic regions in the set of geographic regions, by counting intersections between a test ray cast from the data point and the previously identified segments.

24. The system of claim 21 , wherein the query-processing mechanism is configured to cause, while causing display of at least a subset of the set of geographic regions, display of a choropleth map, wherein each geographic region is shaded, patterned or colored in proportion to a corresponding one of the counts for the geographic region.

25. The system of claim 21 , further comprising an index generator configured to build an index that identifies sorted ranges and corresponding sets of the previously identified segments.

26. The system of claim 21 , further comprising an index generator configured to build an index that identifies sorted ranges and corresponding sets of the previously identified segments, wherein the index identifies the sorted ranges and corresponding sets of the previously identified segments using a point data structure with an order field.

27. The system of claim 21 , wherein the query-processing mechanism is configured to identify the previously identified segments from an index that stores intersection lists modulo k.

28. The system of claim 21 , wherein the query-processing mechanism is configured to identify the previously identified segments from an index that stores intersection lists modulo k, wherein the query-processing mechanism is configured to identify the previously identified segments from the index by:

identifying a nearest intersection list; and

updating the nearest intersection list to the identified range at runtime.

29. The system of claim 21 , wherein the query-processing mechanism is configured to identify the previously identified segments from an index that stores intersection lists modulo k, wherein the query-processing mechanism is configured to identify the previously identified segments from the index by:

identifying a nearest intersection list using a binary search; and

updating the nearest intersection list to the identified range at runtime.

30. The system of claim 21 , wherein the query-processing mechanism is configured to receive the query from a user through a user interface.