System and process for identifying objects and/or points nearby a given object or point
First Claim
1. A computer-implemented process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within a search area around the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest, said process comprising using a computer to perform the following process actions:
- dividing the geographic system defined by said geometric data into a plurality of zones;
identifying which zone each object or point in the database resides;
identifying every zone intersected by the search area; and
identifying the nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within the search area around the base point by initially considering only those objects and/or points that are identified as residing in the zones intersected by the search area.
8 Assignments
0 Petitions
Accused Products
Abstract
A system and process is presented that identifies nearby objects and/or points in relation to a base object or point. An object or point is nearby if it resides within a prescribed area around the base point. The identification is based on information accessed from a database of geometric data. The identification of nearby neighbors begins by dividing the geographic system defined by said geometric data into a plurality of zones. The zone in which each object or point resides and the zones intersected by the prescribed area are determined. The nearby objects and/or points of interest are then identified by initially considering only those that are identified as residing in the zones intersected by the prescribed area. The search for nearby neighbors can be further refined by limiting the objects and/or points considered to those with locations within the lateral extent and/or within the height of the prescribed area.
-
Citations
82 Claims
-
1. A computer-implemented process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within a search area around the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest, said process comprising using a computer to perform the following process actions:
-
dividing the geographic system defined by said geometric data into a plurality of zones;
identifying which zone each object or point in the database resides;
identifying every zone intersected by the search area; and
identifying the nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within the search area around the base point by initially considering only those objects and/or points that are identified as residing in the zones intersected by the search area. - View Dependent Claims (2, 3)
-
-
4. A computer-implemented process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within a search area around the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest, said process comprising the following process actions:
-
dividing the geographic system defined by said geometric data into a plurality of zones each forming a strip of the same prescribed zone height and assigning an integer zone number to each strip;
determining what zone each object or point in the database resides and assigning that zone number to the object or point;
identifying the zone number of every zone intersected by the search area; and
for each object or point associated with each zone number identified as intersected by the search area, determining whether a first coordinate of the object or point under consideration defining its location along the width of the strip in which it resides is within the range of the first coordinate of the base point less a distance defining the extent of the search area in a first direction along the width of the strip in which the base point resides and the first coordinate of the base point plus the same distance defining the extent of the search area in the opposite direction along the width of the strip in which the base point resides, whenever it is determined that the first coordinate of the object or point under consideration is within the specified range, designating said object or point as a nearby neighbor candidate, determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than said distance defining the extent of the search area in either direction along the width of the strip, and whenever it is ascertained that said actual distance is equal to or less than said distance defining the extent of the search area in either direction along the width of the strip, designating the candidate object or point as a nearby neighbor of the base point. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A system for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point having the spherical coordinates (“
- @ra”
, “
@dec”
) which resides within a search area of a prescribed radius (“
@r) from(around) the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of spherical system with spherical coordinates comprising the declination (dec) and right ascension (ra) of the object or point from the center of a sphere representing the spherical system, comprising;
a general purpose computing device;
a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, divide the sphere into a plurality of zones each forming a declination strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the south pole being designated as zone number 0;
determine what zone each object or point in the database resides and assigning that zone number to the object or point;
identify the zone number of every zone intersected by the search area; and
for each object or point associated with each zone number identified as intersected by the search area, determine whether the ra value of the object or point under consideration is between the range of @ra−
@r′ and
@ra+@r′
, where @r′
is @r corrected for right ascension compression corresponding to the dec value of the base point,whenever it is determined that the ra value of the object or point under consideration is between the range of @ra−
@r′ and
@ra+@r′
, designate said object or point as a nearby neighbor candidate,determine if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than @r, and whenever it is ascertained that said actual distance is equal to or less than @r, designate the candidate object or point as a nearby neighbor of the base point. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
- @ra”
-
27. A computer-readable medium having computer-executable instructions for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point having the spherical coordinates (“
- @ra”
, “
@dec”
) which resides within a search area of a prescribed radius (“
@r) from the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of spherical system with spherical coordinates comprising the declination (dec) and right ascension (ra) of the object or point from the center of a sphere representing the spherical system, said computer-executable instructions comprising;
dividing the sphere into a plurality of zones each forming a declination strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the south pole being designated as zone number 0;
determining what zone each object or point in the database resides and assigning that zone number to the object or point;
identifying the zone number of every zone intersected by the search area; and
for each object or point associated with each zone number identified as intersected by the search area, determining whether the ra value of the object or point under consideration is between the range of @ra−
x and @ra+x, wherein x is equal to @r corrected for right ascension compression corresponding to the dec value of the object or point under consideration whenever that object or point is in the same zone as the base point, and wherein x is equal to one half the width of the widest portion of the search area that intersects the zone containing the object or point under consideration whenever that object or point is not in the same zone as the base point,whenever it is determined that the ra value of the object or point under consideration is between the range of @ra−
x and @ra+x, designating said object or point as a nearby neighbor candidate,determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than @r, and whenever it is ascertained that said actual distance is equal to or less than @r, designating the candidate object or point as a nearby neighbor of the base point.
- @ra”
-
28. A computer-readable medium having computer-executable instructions for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point having rectangular coordinates which reside within a search area of a prescribed radius (@r) from the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of a planar system with rectangular coordinates (x,y) from a prescribed origin of a plane representing the planar system, said computer-executable instructions comprising:
-
dividing the plane into a plurality of zones each forming a lateral strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the bottommost zone being designated as zone number 0;
determining what zone each object or point in the database resides and assigning that zone number to the object or point;
identifying the zone number of every zone intersected by the search area; and
for each object or point associated with each zone number identified as intersected by the search area, adding a number equal to the absolute value of the maximum negative x coordinate value associated with the planar system of the database of geometric data to x coordinate values of any object or point taken from the database to produce a corrected x value, adding a number equal to the absolute value of the maximum negative y coordinate value associated with the planar system of the database of geometric data to y coordinate values of any object or point taken from the database to produce a corrected y value, determining whether the corrected x value of the object or point under consideration is between the range of @x−
a and @x+a, wherein @x is the x value of the base point corrected by adding a number equal to the absolute value of the maximum negative x coordinate value associated with the planar system of the database of geometric data if the x value of the base point is defined in terms of the planar system of the database, and wherein a is equal to @r whenever the object or point under consideration is in the same zone as the base point and to one half the width of the widest portion of the search area that intersects the zone containing the object or point under consideration whenever that object or point is not in the same zone as the base point,whenever it is determined that the corrected x value of the object or point under consideration is between the range of @x−
a and @x+a, designating said object or point as a nearby neighbor candidate,determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than @r, and whenever it is ascertained that said actual distance is equal to or less than @r, designating the candidate object or point as a nearby neighbor of the base point.
-
-
29. A computer-implemented process for identifying nearby neighbor objects and/or points of interest for each object or point of interest located in a plurality of zones of a sphere from information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of a spherical system with spherical coordinates comprising the declination (dec) and right ascension (ra) of the object or point from the center of said sphere which represents the spherical system, said process comprising using a computer to perform the following process actions:
-
dividing the sphere into said plurality of zones each forming a consecutive declination strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the southernmost zone being designated as zone number 0;
determining what objects and/or points in the database reside in said plurality of zones and assigning that zone number to the object or point; and
for each of said plurality of zones, (i) designating the zone under consideration as the base zone, (ii) selecting a previously unselected object or point residing in the currently designated base zone, (iii) identifying those zones of said plurality of zones that are located to the north of the currently designated base zone and which are at least partially traversed by a line (@r) of a prescribed length extending northward from the northern border of the currently designated base zone, if any, and identify those zones of said plurality of zones that are located to the south of the currently designated base zone and which are at least partially traversed by @r extending southward from the southern border of the currently designated base zone, if any, (iv) designating the identified northern and southern zones, as well as the currently designated base zone as neighbor zones;
(v) selecting a previously unselected neighbor zone, (vi) selecting a previously unselected object or point residing within the currently selected neighbor zone, (vii) determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′ and
the ra value of the selected base zone object or point+@r′
, where @r′
is @r corrected for right ascension compression corresponding to the dec value of the selected base zone object or point,(viii) whenever it is determined that the ra value of the selected neighbor zone object or point falls within said ra range, designating the selected neighbor zone object or point as a nearby neighbor candidate, (ix) determining if the candidate object or point is in a circular area centered on the selected base zone object or point and having a radius equal to @r by computing the actual distance between the selected base zone object or point and the candidate object or point, and ascertaining if said actual distance is equal to or less than @r, (x) whenever it is ascertained that said actual distance is equal to or less than @r, designating the candidate object or point as a nearby neighbor of the selected base zone object or point, (xi) repeating actions (vi) through (x) until no previously unselected objects and/or points residing within the currently selected neighbor zone remain, (xii) repeating actions (v) through(xi) until no previously unselected neighbor zones remain, and (xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 52)
-
-
46. A computer-implemented process for identifying nearby neighbor objects and/or points of interest for each object or point of interest located in a plurality of zones of a plane from information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of a planar system with rectangular coordinates (x, y) of the object or point from a prescribed origin of said plane which represents the planar system, said process comprising using a computer to perform the following process actions:
-
dividing the plane into said plurality of zones each forming a consecutive lateral strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the bottommost zone being designated as zone number 0;
determining what objects and/or points in the database reside in said plurality of zones and assigning that zone number to the object or point; and
for each of said plurality of zones, (i) designating the zone under consideration as the base zone, (ii) selecting a previously unselected object or point residing in the currently designated base zone, (iii) identifying those zones of said plurality of zones that are located above of the currently designated base zone and which are at least partially traversed by a line (@r) of a prescribed length extending upward from the top border of the currently designated base zone, if any, and identify those zones of said plurality of zones that are located below of the currently designated base zone and which are at least partially traversed by @r extending downward from the bottom border of the currently designated base zone, if any, (iv) designating the identified zones above and below the currently designated base zone, as well as the currently designated base zone itself, as neighbor zones, (v) selecting a previously unselected neighbor zone, (vi) selecting a previously unselected object or point residing within the currently selected neighbor zone, (vii) determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r, (viii) whenever it is determined that the x value of the selected neighbor zone object or point falls within said lateral range, designating the selected neighbor zone object or point as a nearby neighbor candidate, (ix) determining if the candidate object or point is in a region centered on the selected base zone object or point by computing the actual distance between the selected base zone object or point and the candidate object or point, (x) whenever it is ascertained that said actual distance is in the region centered on the selected base zone object or point, designating the candidate object or point as a nearby neighbor of the selected base zone object or point, (xi) repeating actions (vi) through (x) until no previously unselected objects and/or points residing within the currently selected neighbor zone remain, (xii) repeating actions (v) through(xi) until no previously unselected neighbor zones remain, and (xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain. - View Dependent Claims (47, 48, 49, 50, 51, 53, 54, 55, 56, 57)
-
-
58. A computer-implemented process for identifying nearby neighbor objects and/or points for objects and/or points in a database which includes a set of parameters for each object and point, said process comprising the following process actions:
-
identifying a range of a pre-selected one of said set of parameters into which that parameter of each of the objects and/or points in the database falls and dividing the database into a plurality of zones each forming an equal sized sub-range of the identified range;
assigning an integer zone number to each sub-range in a bottom to top sequence starting with the bottommost zone, which is the sub-range having the smallest values for the pre-selected parameter, being designated as zone number 0;
determining what zone each object or point in the database is associated with and assigning the zone number of that zone to the object or point;
for each of said plurality of zones, (i) designating the zone under consideration as the base zone, (ii) selecting a previously unselected object or point associated with the currently designated base zone, (iii) identifying those zones of said plurality of zones that correspond to a sub-range having values of the pre-selected parameter that are larger than those of the currently designated base zone and which are equal to or less than a prescribed upper limit of said pre-selected parameter, and identifying those zones of said plurality of zones that correspond to a sub-range having values of the pre-selected parameter that are smaller than those of the currently designated base zone and which are equal to or greater than a prescribed lower limit of said pre-selected parameter, (iv) designating the identified zones above and below the currently designated base zone, as well as the currently designated base zone itself, as neighbor zones, (v) selecting a previously unselected neighbor zone, (vi) selecting a previously unselected object or point associated with the currently selected neighbor zone, (vii) determining whether a second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value, (viii) whenever it is determined that the second parameter of the selected neighbor zone object or point is within the specified second parameter range, designating said object or point as a nearby neighbor candidate, (ix) determining if the candidate object or point within a prescribed degree of similarity between it and the selected base zone object or point by computing the actual divergence between them in regard to their first and second parameters, (x) whenever it is ascertained that said actual divergence is within the prescribed degree of similarity, designating the candidate object or point as a nearby neighbor of the selected base zone object or point, (xi) repeating actions (vi) through (x) until no previously unselected objects and/or points associated with the currently selected neighbor zone remain, (xii) repeating actions (v) through(xi) until no previously unselected neighbor zones remain, and (xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain. - View Dependent Claims (59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72)
-
-
73. A computer-implemented process for identifying all nearby neighbor objects and/or points in relation to a user-specified base point based on information accessed from a database which includes a set of parameters for each object and point, said process comprising the following process actions:
-
identifying a range of a first pre-selected one of said set of parameters into which that parameter of each of the objects and/or points in the database falls and dividing the database into a plurality of zones each forming an equal sized sub-range of the identified range;
assigning an integer zone number to each sub-range in a bottom to top sequence starting with the bottommost zone, which is the sub-range having the smallest values for the pre-selected parameter, being designated as zone number 0;
determining what zone each object or point in the database is associated with and assigning the zone number of that zone to the object or point;
identifying the zone number of every zone intersected by a search area defined by at least a prescribed search range of said first pre-selected parameter centered on the value of the first parameter of the base point and a prescribed search range of a second pre-selected one of said set of parameters centered on the value of the second parameter of the base point; and
for each object or point associated with each zone number identified as intersected by the search area, determining whether the second parameter of the object or point under consideration falls within a range defined by the second parameter of the base point less a prescribed value and the second parameter of the base point plus the prescribed value, whenever it is determined that second parameter of the object or point under consideration falls within the specified range, designating said object or point as a nearby neighbor candidate, determining if the candidate object or point is in the search area by computing the actual divergence between the base point and the candidate object or point in regard to their first and second parameters and ascertaining if said actual divergence places that the candidate object or point within the bounds of the search area, and whenever it is ascertained that said actual divergence places that the candidate object or point within the bounds of the search area, designating the candidate object or point as a nearby neighbor of the base point. - View Dependent Claims (74, 75, 76, 77, 78, 79, 80, 81, 82)
-
Specification