Method for determining if the location of a wireless communication device is within a specified area
First Claim
1. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined are of interest that is of substantially any shape, the method comprising:
- receiving a location associated with a wireless station;
providing a quadtree representation of an area that includes a predetermined area of interest, wherein said guadtree representation includes;
level-1 through level-n, where n is an integer;
wherein level-1 has at least one level-1 node that represents a level-1 area;
wherein associated with each level-1 node is a level-1 location;
wherein level-x, where 1<
x≦
n, has a maximum of four level-x nodes for each level-(x−
1) node;
wherein each level-x node represent one of the four subsidiary areas of a level(x−
1) area associated with one of the level-(x−
1) nodes;
wherein associated with each level-x node is a level-x location;
wherein associated with each level-n node is an indicator of whether or not the level-n area represented by the level-n node is part of the predetermined area of interest; and
using said location associated with a wireless station and said quadtree representation to determine whether the wireless station is located within the predetermined area of interest.
5 Assignments
0 Petitions
Accused Products
Abstract
The present invention is directed to a method for determining whether a location associated with a wireless station, such as a cellular telephone, is located within an area of interest. The area of interest is defined using quadtree representation of an area that includes the area of interest and identifying nodes within the quadtree that represent the area of interest. By iterative comparison of the location associated with the wireless station to the locations associated with a node at each level of the quadtree, a determination can be made as to whether or not the location associated with the wireless station is within the area of interest.
271 Citations
14 Claims
-
1. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined are of interest that is of substantially any shape, the method comprising:
-
receiving a location associated with a wireless station;
providing a quadtree representation of an area that includes a predetermined area of interest, wherein said guadtree representation includes;
level-1 through level-n, where n is an integer;
wherein level-1 has at least one level-1 node that represents a level-1 area;
wherein associated with each level-1 node is a level-1 location;
wherein level-x, where 1<
x≦
n, has a maximum of four level-x nodes for each level-(x−
1) node;
wherein each level-x node represent one of the four subsidiary areas of a level(x−
1) area associated with one of the level-(x−
1) nodes;
wherein associated with each level-x node is a level-x location;
wherein associated with each level-n node is an indicator of whether or not the level-n area represented by the level-n node is part of the predetermined area of interest; and
using said location associated with a wireless station and said quadtree representation to determine whether the wireless station is located within the predetermined area of interest. - View Dependent Claims (2, 3, 4)
setting x equal to 1;
first identifying the level-1 node that represents the level-1 area that includes the location associated with the wireless station as the relevant level-x node;
comparing said location associated with a wireless station to a level-x location associated with the relevant level-x node, where 1≦
x<
n, to determine which level-(x+1) node represents the level-(x+1) area that includes the location associated with the wireless station;
second identifying the level-(x+1) node determined to represent the level-(x+1) area that includes the location associated with the wireless station as the relevant level-x node;
incrementing, following said step of comparing, the value of x by 1;
repeating, if x<
n, said steps of comparing, second identifying and incrementing;
transmitting, if x=n, the indicator associated with the level-n node that indicates whether or not the location of the wireless stations is within the predetermined area of interest.
-
-
3. A method, as claimed in claim 2, wherein said step of comparing includes:
-
determining whether the latitude of said location associated with a wireless station is greater than or less than the latitude associated with said level-x location;
determining whether the longitude of said location associated with a wireless station is greater than or less than the longitude associated with said level-x location.
-
-
4. A method, as claimed in claim 1, wherein said step of providing a quadtree includes;
storing a level of said quadtree on a disk drive.
-
5. A method for constructing a quadtree representation of an area that includes an area of interest and is suitable for use in high-speed, wireless telecommunication application that requires a determination of whether a location associated with a wireless station is within the area of interest, the method comprising:
-
receiving a map of an area of interest in a telecommunication application;
vectorizing the boundaries of the area of interest to define a polygon defined by a plurality of edges that enclose an area;
establishing a quadtree level depth n, where n is an integer;
setting x equal to 1;
identifying a level-1 node that represents a level-1 area that includes the polygon;
defining, if an edge of said polygon is located within a level-(x+1) area that is one of four subsidiary areas of said level-x area, as a level-(x+1) node;
incrementing the value of x by 1;
repeating, if x<
n, said steps of defining and incrementing;
establishing, if x=n, an indicator for each level-n node that identifies the polygon;
wherein said identifier can subsequently be used to determine if the location associated with a wireless station is within said polygon. - View Dependent Claims (6, 7, 8, 9, 10)
determining if four nodes at level-n that represent the four subsidiary areas of a level-(n−
1) area have the indicator;
establishing, if all four nodes at level-n have the indicator, the indicator in the level-(n−
1) node that has the level-(n−
1) area that includes the four subsidiary areas associated with the four nodes at level n; and
removing, if all four nodes at level-n have the indicator, the four nodes at level-n from the quadtree.
-
-
7. A method, as claimed in claim 6, wherein said step of establishing includes:
repeating said steps of determining, removing and establishing for all the groups of four nodes at level-n that represent four subsidiary areas of a level-(n−
1) area that have the indicator.
-
8. A method, as claimed in claim 7, wherein said step of establishing includes:
repeating said step of determining, removing and establishing for each level.
-
9. A method, as claimed in claim 5, wherein said step of establishing includes:
-
setting x equal to n;
determining for all groups of four nodes at level-x that represent the four subsidiary areas of a level-(x−
1) area if all four nodes of a group have the indicator;
establishing, for all groups of four nodes have the indicator, the indicator in the level-(x−
1) node that has the level-(x−
1) area that includes the four subsidiary areas associated with the four nodes at level x;
removing, for all groups of four nodes that have the indicator, the four nodes in each group from the quadtree; and
decrementing x by 1;
repeating, if x≧
1, said steps of determining, removing and establishing.
-
-
10. A method, as claimed in claim 5, further comprising:
-
inserting a second node to replace an existing, first node;
wherein said second node has either removed or inserted an indicator relative to the existing first, node;
removing, following said step of inserting, said existing, first node.
-
-
11. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined area of interest that is of substantially any shape, the method comprising:
-
receiving a location associated with a wireless station;
providing a quadtree representation of an area that includes a predetermined area of interest wherein said quadtree representation includes;
level-1 through level-n, where n is an integer;
wherein level-1 has at least one level-1 node that represents a level-1 area;
wherein associated with each level-1 node is a level-1 location;
wherein level-x, where 1<
x≦
n, has a number of level-x nodes that is a multiple of four, where the multiplier is a value from 0 to the number of level-(x−
1) nodes;
wherein each level-x node represents one of the four subsidiary areas of a level-(x−
1) area associated with one of the level-(x−
1) nodes;
wherein associated with each level-x node is a level-x location;
wherein associated with each level-n node is an indicator of whether or not the level-n area represented by the level-n node is part of the predetermined area of interest; and
using said location associated with a wireless station and said quadtree representation to determine whether the wireless station is located within the predetermined area of interest. - View Dependent Claims (12, 13)
setting x equal to 1;
first identifying the level-1 node that represents the level-1 area that includes the location associated with the wireless station as the relevant level-x node;
comparing said location associated with a wireless station to a level-x location associated with the relevant level-x node, where 1≦
x<
n , to determine which level-(x+1) node represents the level-(x+1) area that includes the location associated with the wireless station;
second identifying the level-(x+1) node determined to represent the level-(x+1) area that includes the location associated with the wireless station as the relevant level-x node;
incrementing, following said step of comparing, the value of x by 1;
repeating, if x<
n, said steps of comparing, second identifying and incrementing;
transmitting, if x=n, the indicator associated with the level-n node that indicates whether or note the location of the wireless stations is within the predetermined area of interest.
-
-
13. A method, as claimed in claim 12, wherein said step of comparing includes;
-
determining whether the latitude of said location associated with a wireless station is greater than or less than the latitude associated with said level-x location;
determining whether the longitude of said location associated with a wireless station is greater than or less than the longitude associated with said level-x location.
-
-
14. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined area of interest that is of substantially any shape, the method comprising:
-
receiving a location associated with a wireless station;
providing a quadtree representation of an area that includes a predetermined area of interest; and
using said location associated with a wireless station and said quadtree representation to make a determination as to whether the wireless station is located within the predetermined area of interest;
said method further comprising the steps of;
establishing a definition of said area of interest in terms of area elements of said quadtree data structure and storing said first definition for use by a platform of said wireless telecommunication system for making said determination;
receiving a modification regarding said area of interest said modification affecting an affected portion less than the whole of said definition of said area of interest;
establishing modification information reflecting said modification affecting said affected portion of said definition of said area of interest;
storing said modification information for use by said platform of said wireless telecommunication system for making said determination; and
after said step of storing said modification information, deleting information related to said affected portion from said definition of said area of interest;
wherein said definition of said area of interest is modified with little effect on said wireless telecommunication system.
-
Specification