Data processing: measuring – calibrating – or testing – Measurement system – Dimensional determination
Reexamination Certificate
2001-07-24
2003-05-27
Barlow, John (Department: 2863)
Data processing: measuring, calibrating, or testing
Measurement system
Dimensional determination
C702S150000, C701S214000
Reexamination Certificate
active
06571195
ABSTRACT:
FIELD OF THE INVENTION
The present application relates generally to a method for calculating the distance between two points. The method is particularly useful to the field of navigation systems wherein the accurate and efficient calculation of distances is required.
BACKGROUND OF THE INVENTION
Navigation systems are available for vehicles (such as automobiles, trucks, buses, etc.) that travel on roads. These in-vehicle navigation systems provide end users (such as drivers and/or passengers of the vehicles in which the navigation systems are installed) with various useful navigation features. For example, some navigation systems are able to determine an optimum route to be traveled by roads between locations in a geographic region. Using input from an end user and optionally from equipment that can determine one's physical location (such as a GPS system), programming in the navigation system can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation system may then provide the end user with information about the optimum route in the form of instructions that identify the driving maneuvers required to be taken by the end user to travel from the starting location to the destination location. The instructions may take the form of visual and/or audio instructions that are provided along the way as the end user is travelling the route.
On computer displays that are part of the navigation system hardware, some navigation systems are able to show detailed maps highlighting routes to destinations, the types of maneuvers to be taken along various locations along the routes, the location of certain types of establishments and/or features, etc.
In order to provide these types of features, navigation systems use geographic data. The geographic data may be in the form of one or more databases that include data that represent physical features in a geographic region. The geographic databases include data representing the roads and intersections in a geographic region and also include information relating to the represented roads and intersections, such as turn restrictions at intersections, speed limits along the roads, street name of various roads, address ranges along the roads, etc.
Although navigation systems provide many useful and important features, there continues to be room for improvements in these features. One such area in which there is room for improvement is to use a simplified method of determining the distance between two points accurately and consistently. Difficulties arise in calculating the distance between two points because the earth is not spherical in shape, but instead has an ellipsoidal geometry upon which the navigation databases are based.
Conventional distance calculation techniques include utilizing geodetic formulas that can provide an accurate distance calculation between two points. For example, certain data representing roads and intersections may be expressed in angular units in the WGS84 ellipsoidal coordinates system. Given the latitude and longitude of two points (&phgr;
1
, &lgr;
1
), and (&phgr;
2
, &lgr;
2
), accuracy in distance of the order of a few millimeters for a line length as long as 200 kilometers can be obtained using the equations 1-12 listed below, and which can be found in the following publication: Geometric Geodesy I, Richard H. Rapp, The Ohio State University, Apr. 1991, pp. 114-115. Equation 12 yields the desired distance between two points after evaluating different quantities as shown in equations 1-11. The notation “a” refers to the semi-major axis of the ellipsoid, while notation “e” refers to the eccentricity of the ellipsoid, wherein the remainder of the notations are self-explanatory, with e
s
, A, B, C, W, E, F and D in equations 8, 9 and 10 being intermediate quantities present in the following equations and D in equation representing distance between points.
e
s
2
=
e
2
1
-
e
2
(
1
)
A
=
1
+
(
e
s
2
cos
4
φ
1
)
(
2
)
B
=
1
+
(
e
s
2
cos
4
φ
2
)
(
3
)
C
=
1
+
(
e
s
2
(
4
)
w
=
A
(
λ
2
-
λ
1
)
2
(
5
)
Δ
φ
=
φ
2
-
φ
1
(
6
)
Δ
λ
=
λ
2
-
λ
1
(
7
)
D
=
Δ
φ
2
B
[
1
+
3
e
s
2
4
B
2
Δ
φ
sin
(
2
φ
1
+
2
3
Δ
φ
)
]
(
8
)
E
=
sin
(
D
)
cos
(
w
)
(
9
)
F
=
1
A
sin
(
w
)
[
B
cos
φ
1
cos
D
-
sin
φ
1
sin
D
]
(
10
)
sin
σ
2
=
E
2
+
F
2
(
11
)
D
=
a
C
σ
B
2
(
12
)
As shown above, the equations 1-12 require the evaluation of many non-linear mathematical functions to compute the distance between points. It may not be feasible to perform the evaluation of these non-linear mathematical functions repeatedly where the latitude and longitude of points are constantly changing in certain applications, such as in navigation systems. Also, it is typically not necessary to calculate the distance between points within a few millimeters of accuracy in such applications. Instead, the only requirement is that the distance should be sufficiently accurate for navigation system applications, and that the calculation of such distance should be efficient.
For efficiency, it is necessary to reduce the use of non-linear mathematical functions to the extent possible. As the distances to be determined in conventional navigational system applications are typically not very long, the use of simple formulas and the Pythagorean theorem have been and can be used and still maintain the required level of efficiency and accuracy. Such simple formulas are given below in equations 13-15, although there are certain drawbacks to using these equations as well, which will be discussed below.
D
E
=N cos &phgr;&Dgr;&lgr; (13)
D
N
=M&Dgr;&phgr; (14)
D
={square root over (
D
E
2
+D
N
N
2
)} (15)
wherein
φ
=
φ
1
+
φ
2
2
(
mean
latitude
)
(
16
)
N
=
a
1
-
e
2
sin
2
φ
(
17
)
M
=
a
(
1
-
e
2
)
(
1
-
e
2
sin
2
φ
)
3
(
18
)
D
E
and D
N
are east and north components of the distance D between the two points (&phgr;
1
,&lgr;
1
), and (&phgr;
2
,&lgr;
2
), &Dgr;&phgr; is the difference in the latitude given in equation 6 above, and &Dgr;&lgr; is the difference in the longitude given in equation 7 above. The prime vertical radius of curvature (N) and the meridian radius of curvature (M) are obtained from equations 17 and 18 and, as a result, it is assumed that the earth has an ellipsoidal geometry for the latitude and longitude values in the above formulas. This is required because the latitude and longitude values for a given set of points are based upon the earth having an ellipsoidal geometry. Evaluations of radii of curvature for prime vertical (N) and meridian (M) therefore are performed for the given points in the above formulas. Again, the notation “a” refers to the semi-major axis of the ellipsoid, while notation “e” refers to the eccentricity of the ellipsoid. The prime vertical radius of curvature (N) and the meridian radius of curvature (M) are a function of latitude, and their variations from 0 to 90 degrees is shown in FIG.
1
. As a result, equations 13 and 14 cannot be replaced with a model of the earth having a spherical geometry. Moreover, as shown in equation 13, an evaluation for cosine also has to be done, as its value is necessary to determine the east component of the distance between the two points. These values are needed every time the latitude coordinate changes, a
Phuyal Bishnu P.
Smith Nicholas E.
Barlow John
Cherry Stephen J.
Kaplan Laurence M.
Kozak Frank J.
Navigation Technologies Corporation
LandOfFree
Method for calculating distance using piece-wise linear... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for calculating distance using piece-wise linear..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for calculating distance using piece-wise linear... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004454