Boundary detection algorithm for embedded devices

• US 7,680,590 B2
• Filed: 12/02/2003
• Issued: 03/16/2010
• Est. Priority Date: 11/22/2002
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Sanqunetti, Douglas R.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): SAMPLE, JONATHAN L
• Application Number:
  US10/726,278
• Publication Number:
  US 20040138808A1
• Time in Patent Office: 2,296 Days
• Field of Search: 701/207, 701/200, 701/300
• US Class Current: 701/207
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06T 3/60 Rotation of whole images or parts thereof
• CPC Class Codes: G07C 5/008 communicating information to a remotely located station transmission systems for measured values G08C
• CPC Class Codes: G08G 1/207 with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries

Abstract

Techniques for detecting boundary crossings may involve the use of rectangles that approximate a boundary. Data defining the rectangles may be retrieved, and a current location of a monitored device may be identified. The current location may be compared with the rectangles, and a determination that the current location is located within a rectangle may indicate a boundary crossing. To simplify the calculations on the monitored device, certain calculations may be performed in advance. For example, an angle between a selected side of a particular rectangle and an axis of the coordinate system may be determined, and the particular rectangle may be rotated by the angle to orient the rotated rectangle parallel to the axis of the coordinate system. Subsequently, location coordinates for a monitored device may be rotated and compared with a corresponding rotated rectangle to determine whether the monitored device is located within the particular rectangle.

Claims

1. A method for detecting a crossing of a boundary, the method comprising:

receiving a representation of a boundary within a coordinate system, wherein the boundary is defined by at least one rectangle;

receiving a set of coordinates associated with a location of a monitored device;

rotating, by a processor, the received set of coordinates by an angle between a selected side of a particular rectangle of the boundary and an axis of the coordinate system; and

comparing, by the processor, the rotated set of coordinates to a rotated rectangle to determine whether the location of the monitored device is located within the particular rectangle, wherein the particular rectangle is rotated by the angle to form the rotated rectangle such that the selected side of the rotated rectangle is oriented parallel to the axis of the coordinate system.

2. The method of claim 1 wherein a boundary crossing is detected if the location of the monitored device is located within the particular rectangle.

3. The method of claim 2 further comprising initiating a pre-selected response if a boundary crossing is detected.

4. The method of claim 3 wherein the pre-selected response includes

determining a new jurisdiction entered as a result of the boundary crossing;

loading a boundary for the new jurisdiction; and

detecting a crossing of the new jurisdiction boundary.

5. The method of claim 3 wherein the pre-selected response includes gathering information related to the boundary crossing.

6. The method of claim 5 wherein the monitored device comprises a vehicle and the gathered information includes at least one of a distance traveled and an amount of fuel used by the vehicle.

7. The method of claim 5 wherein the gathered information is sent over a wireless interface to a central server.

8. The method of claim 5 wherein the gathered information is stored on the device being monitored.

9. The method of claim 1 wherein the boundary is defined by a collection of overlapping rectangles, the method further comprising selecting a different rectangle of the collection of overlapping rectangles if the location of the monitored device is not located within the particular rectangle.

10. The method of claim 9 further comprising:

storing information representing the different rectangle rotated by an angle between a selected side of the different rectangle and an axis of the coordinate system such that the selected side of the rotated different rectangle is oriented parallel to the axis of the coordinate system;

rotating the received set of coordinates by the angle between the selected side of the different rectangle and the axis of the coordinate system to generate a second set of rotated coordinates; and

comparing the second set of rotated coordinates to the rotated different rectangle to determine whether the location of the monitored device is located within the different rectangle.

11. The method of claim 1 wherein:

the particular rectangle is defined by coordinates of two opposite corners of the rectangle;

the rotated rectangle is generated by rotating the coordinates of the two opposite corners of the rectangle by the angle; and

comparing the rotated set of coordinates to the rotated rectangle comprises comparing the rotated set of coordinates to the rotated coordinates of the two opposite corners of the rectangle.

12. The method of claim 1 wherein the defined boundary represents a border between a first jurisdiction and a second adjacent jurisdiction.

13. The method of claim 1 wherein the defined boundary is stored as a file by the monitored device.

14. The method of claim 1 wherein the particular rectangle has an associated indicator of a jurisdiction that is occupied if the location of the monitored device is located within the particular rectangle, the method further comprising loading a boundary for the jurisdiction that is occupied if the location of the monitored device lies within the particular rectangle.

15. The method of claim 1 wherein defining the boundary, determining the angle, and rotating the particular rectangle are performed by a central server.

16. The method of claim 1 wherein receiving the set of coordinate associated with the location, rotating the received set of coordinates, and comparing the rotated set of coordinates to the rotated rectangle are performed by the monitored device.

17. A method for detecting a crossing of a border between different jurisdictions, the method comprising:

retrieving data defining at least one rectangle that represents the border between the different jurisdictions;

receiving information relating to a current location of a monitored device; and

comparing, by a processor, the current location with the at least one rectangle using the data defining the at least one rectangle, wherein a determination that the current location is located within the at least one rectangle indicates a border crossing by the monitored device between the different jurisdictions.

18. The method of claim 17 wherein retrieving data defining the at least one rectangle receiving information relating to the current location of the monitored device, and comparing the current location to the at least one rectangle are performed by the monitored device.

19. The method of claim 17 wherein the monitored device comprises a vehicle.

20. The method of claim 17 further comprising determining a distance covered by the monitored device within one of the jurisdictions having the border.

21. The method of claim 17 further comprising determining an amount of fuel used by the monitored device within one of the jurisdictions having the border.

22. The method of claim 17 further comprising determining statistics related to one of the jurisdictions having the border.

23. The method of claim 17 further comprising retrieving adjacent jurisdiction boundary data when the border crossing is indicated, with the adjacent jurisdiction boundary data defining one or more rectangles associated with another border of an adjacent jurisdiction that is occupied by the monitored device after the boundary crossing.

24. The method of claim 17 wherein the at least one rectangle corresponds to the border of a current jurisdiction.

25. The method of claim 24 wherein rectangles defining borders of adjacent jurisdictions do not overlap the at least one rectangle corresponding to the border of the current jurisdiction.

26. The method of claim 17 wherein the data defining the at least one rectangle includes, for each rectangle, an angle of rotation for the respective rectangle and rotated coordinates of two opposite corners of the respective rectangle, with the rotated coordinates corresponding to coordinates of the respective rectangle that have been rotated by the angle of rotation.

27. The method of claim 17 wherein comparing the current location with the at least one rectangle comprises:

rotating a set of coordinates defining the current location by an angle of rotation associated with the at least one rectangle; and

comparing the rotated coordinates defining the current location to rotated coordinates of two opposite corners of the at least one rectangle.

28. A method for detecting movement across a boundary, the method comprising:

storing at least two sets of rotated coordinates associated with a predetermined rectangular boundary segment, the at least two sets of rotated coordinates corresponding to at least two sets of original coordinates that define the predetermined rectangular boundary segment in a coordinate system, wherein each of the sets of original coordinates is rotated by an angle of rotation to generate the corresponding set of rotated coordinates prior to storing each set of rotated coordinates, and the at least two sets of rotated coordinates define a rotated boundary segment having sides that are parallel to an axis of the coordinate system;

storing the angle of rotation, wherein the angle of rotation is defined by an angle between the axis of the coordinate system and a side of the predetermined rectangular boundary segment;

identifying a location of a monitored device;

rotating, by the monitored device, a set of coordinates representing the identified location of the monitored device by the angle of rotation to generate a rotated set of location coordinates; and

comparing, by the monitored device, the rotated set of location coordinates with the at least two sets of rotated coordinates to determine a position of the monitored device relative to the predetermined rectangular boundary segment.

29. The method of claim 28 wherein each set of coordinates identifies a longitudinal and a latitudinal position.

30. The method of claim 28 further comprising determining whether the boundary has been crossed based on the position of the monitored device relative to the predetermined rectangular boundary segment.

31. The method of claim 28 further comprising:

storing rotated coordinates associated with an additional rectangular boundary segment;

storing an angle of rotation for the additional rectangular boundary segment; and

responsive to a determination that the location of the monitored device is not located within the predetermined rectangular boundary segment;

rotating the set of coordinates representing the identified location of the monitored device by the angle of rotation for the additional rectangular boundary to generate a second rotated set of location coordinates; and

comparing the second rotated set of location coordinates with the rotated coordinates associated with the additional rectangular boundary to determine whether the location of the monitored device is located within the adjacent rectangular boundary segment.

32. The method of claim 28 further comprising initiating a pre-selected response if the location of the monitored device is located within the predetermined rectangular boundary segment.

33. The method of claim 28, wherein the predetermined rectangular boundary segment represents a border between different jurisdictions.