Efficient point-in-polygon indexing technique for facilitating geofencing operations

• US 9,916,326 B2
• Filed: 01/27/2015
• Issued: 03/13/2018
• Est. Priority Date: 01/27/2015
• Status: Active Grant

• Current Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Original Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Inventors: Hendrey, Geoffrey R.
• Primary Examiner(s): Nguyen, Phong H
• Application Number:
  US14/606,407
• Publication Number:
  US 20160217152A1
• Time in Patent Office: 1,141 Days
• Field of Search: 707743
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

A system that facilitates a geofencing operation 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 performs a geofencing operation for the location-aware device based on the identified polygons that the data point falls into.

Claims

1. A computer-implemented method for performing a geofencing operation, 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 of the set of polygons onto a reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in an index;

for each interval between pairs of consecutive intersection points on the reference line, keeping track in the index of open line segments that project onto the interval;

for a data point to be processed that specifies a position of a location-aware device, 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, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval, to identify zero or more polygons that the data point falls into; and

performing a geofencing operation for the location-aware device based on the identified zero or more polygons that the data point falls into.

2. The computer-implemented method of claim 1, wherein the reference line is an X coordinate axis.

3. The computer-implemented method of claim 1, wherein the reference line is a Y coordinate axis.

4. The computer-implemented method of claim 1, wherein determining the relevant interval for the data point includes performing a binary search through an array containing the intersection points on the reference line.

5. The computer-implemented method of claim 1, wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line.

6. The computer-implemented method of claim 1,

wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line;

and

wherein identifying a relevant interval for a data point includes obtaining a list of open intervals for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

7. The computer-implemented method of claim 1,

wherein prior to performing the CN operation for each data point, the set of data points is sorted based on an ordering of projections of the set of data points on the reference line;

and

wherein the set of data points are processed in the sorted order to facilitate reducing an average amount of time required to identify a relevant interval for each data points.

8. The computer-implemented method of claim 1, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a notification about the crossing of the geofence to an entity associated with the location-aware device.

9. The computer-implemented method of claim 1, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geofence, generating a log entry about the crossing of the geofence by the location-aware device.

10. The computer-implemented method of claim 1, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a message to be displayed to a user of the location-aware device.

11. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing a geofencing operation, 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 of the set of polygons onto a reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in an index;

for each interval between pairs of consecutive intersections points on the reference like, keeping track in the index of open line segments that project onto the interval;

for a data point to be processed that specifies a position of a location-aware device, 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, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval, to identify zero or more polygons that the data point falls into; and

performing a geofencing operation for the location-aware device based on the identified zero or more polygons that the data point falls into.

12. The non-transitory computer-readable storage medium of claim 11, wherein the reference line is a Y coordinate axis.

13. The non-transitory computer-readable storage medium of claim 11, wherein determining the relevant interval for the data point includes performing a binary search through an array containing the intersection points on the reference line.

14. The non-transitory computer-readable storage medium of claim 11, wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line.

15. The non-transitory computer-readable storage medium of claim 11, wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line;

and

wherein identifying a relevant interval for a data point includes obtaining a list of open intervals for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

16. The non-transitory computer-readable storage medium of claim 11, wherein prior to performing the CN operation for each data point, the set of data points is sorted based on an ordering of projections of the set of data points on the reference line;

and

wherein the set of data points are processed in the sorted order to facilitate reducing an average amount of time required to identify a relevant interval for each data point.

17. The non-transitory computer-readable storage medium of claim 11, wherein geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a notification about the crossing of the geofence to an entity associated with the location-aware device.

18. The non-transitory computer-readable storage medium of claim 11, wherein the reference line is an X coordinate axis.

19. The non-transitory computer-readable storage medium of claim 11, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, generating a log entry about the crossing of the geofence by the location-aware device.

20. The non-transitory computer-readable storage medium of claim 11, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a message to be displayed to a user of the location-aware device.

21. A system that performs a geofencing operation, comprising:

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

a geofencing 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 of the set of polygons onto a reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and store the intersection points in an index;

for each interval between pairs of consecutive intersection points on the reference line, keep track in the index of open line segments that project onto the interval;

for a data point to be processed that specifies a position of a location-aware device, identifying 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, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval, to identify zero or more polygons that the data point falls into; and

perform a geofencing operation for the location-aware device based on the identified zero or more polygons that the data point falls into.

22. The system of claim 21, wherein the reference line is an X coordinate axis.

23. The system of claim 21, wherein the reference line is a Y coordinate axis.

24. The system of claim 21, wherein while determining the relevant interval for the data point, the geofencing mechanism is configured to perform a binary search through an array containing the intersection points on the reference line.

25. The system of claim 21, wherein while keeping track of the open line segments that project onto the intervals, the geofencing mechanism is configured to maintain a list of open line segments for every nth interval on the reference line.

26. The system of claim 21, wherein while keeping track of the open line segments that project onto the intervals, the geofencing mechanism is configured to maintain a list of open line segments for every nth interval on the reference line;

and

wherein while identifying a relevant interval for a data point, the geofencing mechanism is configured to obtain a list of open intervals for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

27. The system of claim 21, wherein prior to performing the CN operation for each data point, the set of data points is sorted based on an ordering of projections of the set of data points on the reference line;

and

wherein the set of data points are processed in the sorted order to facilitate reducing an average amount of time required to identify a relevant interval for each data point.

28. The system of claim 21, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a notification about the crossing of the geofence to an entity associated with the location-aware device.

29. The system of claim 21, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, generating a log entry about the crossing of the geofence by the location-aware device.

30. The system of claim 21, wherein the geofencing operation includes:

determining whether the position of the location-aware device indicates that the location-aware device has crossed a geofence associated with a boundary of a geographic region; and

if the location-aware device has crossed the geo-fence, sending a message to be displayed to a user of the location-aware device.