System and method for determining position within or without a complex polygon geofence

• US 8,046,168 B2
• Filed: 10/05/2007
• Issued: 10/25/2011
• 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, Xianguan, Wang, Zhengming
• Primary Examiner(s): ALSOMIRI, ISAM A
• Application Number:
  US11/867,755
• Publication Number:
  US 20090093958A1
• Time in Patent Office: 1,481 Days
• Field of Search: 701/207, 701/214, 340/426.19, 340/426.22, 340/995.21
• 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, wherein the ray constructing step is done with the ray oriented in a cardinal direction of the rectangular Cartesian coordinate system, wherein the rectangular Cartesian coordinate system is a system of latitude and longitude used for a globe;

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

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

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;

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

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, 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.