SYSTEM AND METHOD FOR DETERMINING POSITION WITHIN OR WITHOUT A COMPLEX POLYGON GEOFENCE

• US 20090093958A1
• Filed: 10/05/2007
• Published: 04/09/2009
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: OCC Technologies LLC (Volkswagen AG)
• Original Assignee: International Truck Intellectual Property Co. LLC (Volkswagen AG)
• Inventors: Zeng, Xianguang, Wang, Zhengming
• Granted Patent: US 8,046,168 B2
• Time in Patent Office: Days
• US Class Current: 701/214
• CPC Class Codes: G01S 19/14 specially adapted for specific applications

Abstract

A geofence system which locates a position as within or without the complex polygon type geofence using a simplified algorithm. The algorithm obtains a position and compares it to the polygon by establishing a ray from the position constructed in a cardinal direction of the coordinate system. The “polarity” of the count of intersections between the ray and geofence indicates whether the position is inside the geofence or not.

Claims

1. A method of locating a position as being within or without a defined geographic area, the method comprising the steps of:

defining a geofence as a closed circuit of a plurality of straight line boundary segments in a rectangular Cartesian coordinate system to define the geographic area;

obtaining a position in the rectangular Cartesian coordinate system;

constructing a ray from the position within the rectangular Cartesian coordinate system;

locating intersections between the ray and the plurality of line segments;

counting the number of intersections and characterizing the position as within or without the geofence based on the count.

2. The method of claim 1, wherein the ray constructing step is done with the ray oriented in a cardinal direction of the rectangular Cartesian coordinate system.

3. The method of claim 2, wherein the rectangular Cartesian coordinate system is a system of latitude and longitude used for a globe.

4. The method of claim 3, comprising the further steps of:

defining boundary segments such that they include only end point vertex.

5. The method of claim 4, comprising the further steps of:

locating boundary segments parallel to the ray and excluding any intersections between the ray and parallel boundary segments from the count of intersections.

6. The method of claim 5, comprising the further steps of:

locating extreme dimensions of the geofence;

constructing a rectangle in the rectangular Cartesian space from four boundary segments oriented in the cardinal directions of the rectangular Cartesian space, including the extreme dimensions of the geofence and enclosing the geofence; and

characterizing as outside the geofence any point outside of the rectangle.

7. The method of claim 6, comprising the further step of:

following definition of the geofence, averaging the coordinate values of the vertices of the geofence; and

setting the average values as the origin of a new coordinate system and resetting all vertices in terms of the new origin.

8. The method of claim 6, wherein the step of counting further comprises characterizing the position as within the geofence if the count is odd and as without the geofence if the count is even.

9. A geofence system comprising:

a vehicle;

a source of a position for the vehicle;

a program executable allowing definition of one or more regions which the position relates to, the regions being demarcated by polygons comprised of border segments, with the program executable characterizing the position as being within or without the regions; and

the program executable providing for establishing a ray which has its source at the position and which extends in a cardinal direction, the program executable determining status of the position as within or without the regions based on the number of intersections occurring between the ray and border segments of the regions.

10. The system of claim 9 wherein a rectangular Cartesian coordinate system based on global latitude and longitude is used for defining position.

11. The system of claim 10, further comprising:

the polygons including boundary segments that include only one end point vertex.

12. The system of claim 11, further comprising:

the program executable ignoring boundary segments parallel to the ray in determining the count of intersections.

13. The system of claim 12, further comprising:

the program executable providing for constructing a rectangle from four boundary segments oriented in the cardinal directions of the rectangular Cartesian space, the rectanagle including the extreme dimensions of the polygons and enclosing the polygons and characterizing as outside the polygons any position outside of the rectangle.