US-12627944-B2 - High throughput geofence break detection

Abstract

Detecting geofence break events is provided. The method comprises defining a geofence boundary according to a triangle comprising two lines from the center of the earth to two vertices above the earth's surface, and a third line between the vertices above the earth's surface. The geofence boundary is defined by a vector between respective intersection points of the first two lines with the earth's surface. This vector represents a great arc when projected to the curvature of the earth's surface. Origin and destination coordinates for a vehicle are received, wherein a second vector between the origin and destination coordinates represents a great arc defining a path of the vehicle. Responsive to a determination that the second vector intersects the plane of the triangle, a geofence break event notice is sent to a number of downstream consumers.

Inventors

• Barnaby Scott Parker
• Julian Krąbel
• Garrett Dale Reddish

Assignees

• S&P GLOBAL INC.

Dates

Publication Date

20260512

Application Date

20231218

Claims (20)

1. 1 . A computer-implemented method of detecting geofence break events, the method comprising: defining a geofence boundary according to a triangle comprising: a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface; a second segment between the first vertex and a third vertex above the earth's surface; and a third segment between the second and third vertices, wherein the third segment remains above the earth's surface at the segment midpoint; wherein the geofence boundary is defined by a first vector between respective intersection points of the first and second segments with the earth's surface, wherein the first vector represents a great arc when projected to the curvature of the earth's surface; receiving origin coordinates and destination coordinates for a vehicle, wherein a second vector between the origin coordinates and destination coordinates represent a great arc defining a path of the vehicle when projected to the curvature of the earth's surface; determining whether the second vector intersects the plane defined by the triangle, wherein an intersection of the plane represents a geofence break; and responsive to a determination that the second vector intersects the plane, sending a geofence break event notice to a number of downstream consumers.
2. 2 . The method of claim 1 , wherein the triangle is one of three or more triangles that define respective geofence boundaries enclosing a geofenced area on the earth's surface.
3. 3 . The method of claim 2 , further comprising defining a buffer zone around the geofenced area, wherein the buffer zone comprises outer boundaries that match the geofenced area in contour.
4. 4 . The method of claim 3 , wherein a geofence break event notice is sent only when the path of the vehicle intersects both a geofence boundary of the geofenced area and an outer boundary of the buffer zone.
5. 5 . The method of claim 2 , wherein a number of the geofence boundaries fall within multiple spatial bins on the earth's surface, wherein the spatial bins are defined by a global three-dimensional mesh of polyhedrons.
6. 6 . The method of claim 5 , further comprising, responsive to a determination that the origin coordinates and destination coordinates are located within a single spatial bin, testing only geofence boundaries within that spatial bin for intersection with the path of the vehicle.
7. 7 . The method of claim 5 , further comprising, responsive to a determination that the origin coordinates and destination coordinates are located in different spatial bins, testing all geofence boundaries for intersection with the path of the vehicle.
8. 8 . The method of claim 5 , further comprising reducing the coordinates of all points falling within a given spatial bin to a single shared identifying key value according to a deterministic function, wherein the origin coordinates and destination coordinates of the vehicle are translated into a key value to retrieve geofence boundaries associated with the spatial bin that maps to that key value in a lookup-optimized data structure.
9. 9 . The method of claim 8 , further comprising converting the true latitude or longitude into grid normalized latitude or longitude to match the edges of the spatial bins to the curvature of the earth.
10. 10 . A system for detecting geofence break events, the system comprising: a storage device that stores program instructions; one or more processors operably connected to the storage device and configured to execute the program instructions to cause the system to: define a geofence boundary according to a triangle comprising: a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface; a second segment between the first vertex and a third vertex above the earth's surface; and a third segment between the second and third vertices, wherein the third segment remains above the earth's surface at the segment midpoint; wherein the geofence boundary is defined by a first vector between respective intersection points of the first and second segments with the earth's surface, wherein the first vector represents a great arc when projected to the curvature of the earth's surface; receive origin coordinates and destination coordinates for a vehicle, wherein a second vector between the origin coordinates and destination coordinates represent a great arc defining a path of the vehicle when projected to the curvature of the earth's surface; determine whether the second vector intersects the plane defined by the triangle, wherein an intersection of the plane represents a geofence break; and responsive to a determination that the second vector intersects the plane, send a geofence break event notice to a number of downstream consumers.
11. 11 . The system of claim 10 , wherein the triangle is one of three or more triangles that define respective geofence boundaries enclosing a geofenced area on the earth's surface.
12. 12 . The system of claim 11 , wherein the processors further executed instructions to define a buffer zone around the geofenced area, wherein the buffer zone comprises outer boundaries that match the geofenced area in contour.
13. 13 . The system of claim 12 , wherein a geofence break event notice is sent only when the path of the vehicle intersects both a geofence boundary of the geofenced area and an outer boundary of the buffer zone.
14. 14 . The system of claim 11 , wherein a number of the geofence boundaries fall within multiple spatial bins on the earth's surface, wherein the spatial bins are defined by a global three-dimensional mesh of polyhedrons.
15. 15 . The system of claim 14 , wherein the processors further executed instructions to, responsive to a determination that the origin coordinates and destination coordinates are located within a single spatial bin, test only geofence boundaries within that spatial bin for intersection with the path of the vehicle.
16. 16 . The system of claim 14 , wherein the processors further executed instructions to, responsive to a determination that the origin coordinates and destination coordinates are located in different spatial bins, test all geofence boundaries for intersection with the path of the vehicle.
17. 17 . The system of claim 14 , wherein the processors further executed instructions to reduce the coordinates of all points falling within a given spatial bin to a single shared identifying key value according to a deterministic function, wherein the origin coordinates and destination coordinates of the vehicle are translated into a key value to retrieve geofence boundaries associated with the spatial bin that maps to that key value in a lookup-optimized data structure.
18. 18 . The system of claim 17 , wherein the processors further executed instructions to convert the true latitude or longitude into grid normalized latitude or longitude to match the edges of the spatial bins to the curvature of the earth.
19. 19 . A computer program product for detecting geofence break events, the computer program product comprising: a non-transitory computer-readable storage medium having program instructions embodied thereon to perform the steps of: defining a geofence boundary according to a triangle comprising: a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface; a second segment between the first vertex and a third vertex above the earth's surface; and a third segment between the second and third vertices, wherein the third segment remains above the earth's surface at the segment midpoint; wherein the geofence boundary is defined by a first vector between respective intersection points of the first and second segments with the earth's surface, wherein the first vector represents a great arc when projected to the curvature of the earth's surface; receiving origin coordinates and destination coordinates for a vehicle, wherein a second vector between the origin coordinates and destination coordinates represent a great arc defining a path of the vehicle when projected to the curvature of the earth's surface; determining whether the second vector intersects the plane defined by the triangle, wherein an intersection of the plane represents a geofence break; and responsive to a determination that the second vector intersects the plane, sending a geofence break event notice to a number of downstream consumers.
20. 20 . The computer program product of claim 19 , wherein the triangle is one of three or more triangles that define respective geofence boundaries enclosing a geofenced area on the earth's surface.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application is related to the following U.S. patent application entitled “Dynamic Down Sampling of Position Tracking Data,” Ser. No. 18/543,907, filed Dec. 18, 2023, now U.S. Pat. No. 12,535,599, assigned to the same assignee, and incorporated herein by reference in its entirety. BACKGROUND INFORMATION 1. Field The present disclosure relates generally to tracking and communications system, and more specifically to vessel tracking services. 2. Background Tracking systems such as Automatic Identification System (AIS) allow ships and other vessels to exchange real-time information such as identity, position, course, heading, and speed. Transceivers onboard ships transmit this information, which can be received by other vessels, shore-based stations, and satellites. Such tracking systems allow vessels and authorities to monitor vessel movements and reduce the risk of collisions at sea by improving situational awareness. Tracking systems such as AIS can be used in conjunction with geofencing technology. Geofencing comprises the creation of virtual geographic boundaries or zones defined around a specific geographic area such as a city or port. Geofencing utilizes location-based communications technologies such as GPS (Global Positioning System), RFID (radio-frequency identification), cellular data, etc., to trigger actions when an object such as a vessel enters or exits the area encompassed by a geofence. SUMMARY An illustrative embodiment provides a computer-implemented method of detecting geofence break events. The method comprises defining a geofence boundary according to a triangle comprising a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface, a second segment between the first vertex and a third vertex above the earth's surface, and a third segment between the second and third vertices, wherein the third segment remains above the earth's surface at the segment midpoint. The geofence boundary is defined by a first vector between respective intersection points of the first and second segments with the earth's surface, wherein the first vector represents a great arc when projected to the curvature of the earth's surface. Origin coordinates and destination coordinates for a vehicle are received, wherein a second vector between the origin coordinates and destination coordinates represent a great arc defining a path of the vehicle when projected to the curvature of the earth's surface. The method determines whether the second vector intersects the plane defined by the triangle, wherein an intersection of the plane represents a geofence break. Responsive to a determination that the second vector intersects the plane, a geofence break event notice is sent to a number of downstream consumers. Another illustrative embodiment provides a system for detecting geofence break events. The system comprises a storage device that stores program instructions and one or more processors operably connected to the storage device and configured to execute the program instructions to cause the system to: define a geofence boundary according to a triangle comprising: a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface; a second segment between the first vertex and a third vertex above the earth's surface; and a third segment between the second and third vertices, wherein the third segment remains above the earth's surface at the segment midpoint; wherein the geofence boundary is defined by a first vector between respective intersection points of the first and second segments with the earth's surface, wherein the first vector represents a great arc when projected to the curvature of the earth's surface; receive origin coordinates and destination coordinates for a vehicle, wherein a second vector between the origin coordinates and destination coordinates represent a great arc defining a path of the vehicle when projected to the curvature of the earth's surface; determine whether the second vector intersects the plane defined by the triangle, wherein an intersection of the plane represents a geofence break; and responsive to a determination that the second vector intersects the plane, send a geofence break event notice to a number of downstream consumers. Another illustrative embodiment provides a computer program product for detecting geofence break events. The computer program product comprises a computer-readable storage medium having program instructions embodied thereon to perform the steps of: defining a geofence boundary according to a triangle comprising: a first segment between a first vertex at the center of the earth and a second vertex above the earth's surface; a second segment between the first vertex and a third vertex above the earth's surface; and a third segment between the second and third vertices, wherein the third segment remains above the earth's surfac