EFFICIENT POINT-IN-POLYGON INDEXING TECHNIQUE TO FACILITATE DISPLAYING GEOGRAPHIC DATA
First Claim
1. A computer-implemented method for displaying geographic data, comprising:
- obtaining a set of polygons that define a set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;
projecting rays from the endpoints of the line segments that comprise the set of polygons onto a reference line, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line;
for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval;
for each data point in a set of data points to be processed,identifying a relevant interval on the reference line that the data point projects onto,performing a crossing number (CN) operation by counting intersections between a ray projected from the data point and open line segments associated with the relevant interval to identify zero or more polygons that the data point falls into, andincrementing a count for each polygon that the data point falls into; and
displaying the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon.
1 Assignment
0 Petitions
Accused Products
Abstract
A system that displays geographic data is disclosed. The system obtains polygons that define a set of geographic regions. Then, the system projects rays from endpoints of the line segments that define the polygons onto a reference line to form intersection points. For each interval between pairs of consecutive intersection points on the reference line, the system keeps track of open line segments that project onto the interval. For each data point in a set of data points, the system identifies a relevant interval on the reference line that the data point projects onto, and performs a crossing number operation to identify polygons that the data point falls into, and the system increments a count for each polygon that the data point falls into. Finally, the system displays the set of geographic regions in a manner that indicates a number of data points that fall into each geographic region.
10 Citations
30 Claims
-
1. A computer-implemented method for displaying geographic data, comprising:
-
obtaining a set of polygons that define a set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment; projecting rays from the endpoints of the line segments that comprise the set of polygons onto a reference line, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line; for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval; for each data point in a set of data points to be processed, identifying a relevant interval on the reference line that the data point projects onto, performing a crossing number (CN) operation by counting intersections between a ray projected from the data point and open line segments associated with the relevant interval to identify zero or more polygons that the data point falls into, and incrementing a count for each polygon that the data point falls into; and displaying the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon. - 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 geographic data, the method comprising:
-
obtaining a set of polygons that define a set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment; projecting rays from the endpoints of the line segments that comprise the set of polygons onto a reference line, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line; for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval; for each data point in a set of data points to be processed, identifying a relevant interval on the reference line that the data point projects onto, performing a crossing number (CN) operation by counting intersections between a ray projected from the data point and open line segments associated with the relevant interval to identify zero or more polygons that the data point falls into, and incrementing a count for each polygon that the data point falls into; and displaying the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A system that displays geographic data, comprising:
-
at least one processor and at least one associated memory; and a display mechanism that executes on the at least one processor and is configured to; obtain a set of polygons that define a set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment; project rays from the endpoints of the line segments that comprise the set of polygons onto a reference line, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line; for each interval between pairs of consecutive intersection points on the reference line, keep track of open line segments that project onto the interval; for each data point in a set of data points to be processed, identify a relevant interval on the reference line that the data point projects onto, perform a crossing number (CN) operation by counting intersections between a ray projected from the data point and open line segments associated with the relevant interval to identify zero or more polygons that the data point falls into, and increment a count for each polygon that the data point falls into; and display the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
-
Specification