idnits 2.17.1
draft-thomson-geopriv-uncertainty-06.txt:
Checking boilerplate required by RFC 5378 and the IETF Trust (see
https://trustee.ietf.org/license-info):
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/checklist :
----------------------------------------------------------------------------
** The document seems to lack an IANA Considerations section. (See Section
2.2 of https://www.ietf.org/id-info/checklist for how to handle the case
when there are no actions for IANA.)
Miscellaneous warnings:
----------------------------------------------------------------------------
== The copyright year in the IETF Trust and authors Copyright Line does not
match the current year
-- The document seems to lack a disclaimer for pre-RFC5378 work, but may
have content which was first submitted before 10 November 2008. If you
have contacted all the original authors and they are all willing to grant
the BCP78 rights to the IETF Trust, then this is fine, and you can ignore
this comment. If not, you may need to add the pre-RFC5378 disclaimer.
(See the Legal Provisions document at
https://trustee.ietf.org/license-info for more information.)
-- The document date (March 10, 2011) is 4767 days in the past. Is this
intentional?
Checking references for intended status: Informational
----------------------------------------------------------------------------
-- Looks like a reference, but probably isn't: '1' on line 1215
-- Looks like a reference, but probably isn't: '2' on line 532
-- Looks like a reference, but probably isn't: '3' on line 532
== Missing Reference: '2d' is mentioned on line 673, but not defined
== Missing Reference: '3d' is mentioned on line 673, but not defined
-- Looks like a reference, but probably isn't: '0' on line 1215
== Unused Reference: 'I-D.ietf-geopriv-policy' is defined on line 1075, but
no explicit reference was found in the text
== Unused Reference: 'RFC3694' is defined on line 1098, but no explicit
reference was found in the text
== Outdated reference: A later version (-27) exists of
draft-ietf-geopriv-policy-22
== Outdated reference: A later version (-03) exists of
draft-thomson-geopriv-location-obscuring-02
-- Obsolete informational reference (is this intentional?): RFC 3825
(Obsoleted by RFC 6225)
Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 7 comments (--).
Run idnits with the --verbose option for more detailed information about
the items above.
--------------------------------------------------------------------------------
2 GEOPRIV M. Thomson
3 Internet-Draft J. Winterbottom
4 Intended status: Informational Andrew Corporation
5 Expires: September 11, 2011 March 10, 2011
7 Representation of Uncertainty and Confidence in PIDF-LO
8 draft-thomson-geopriv-uncertainty-06
10 Abstract
12 The key concepts of uncertainty and confidence as they pertain to
13 location information are defined. Methods for the manipulation of
14 location estimates that include uncertainty information are outlined.
16 Status of this Memo
18 This Internet-Draft is submitted in full conformance with the
19 provisions of BCP 78 and BCP 79.
21 Internet-Drafts are working documents of the Internet Engineering
22 Task Force (IETF). Note that other groups may also distribute
23 working documents as Internet-Drafts. The list of current Internet-
24 Drafts is at http://datatracker.ietf.org/drafts/current/.
26 Internet-Drafts are draft documents valid for a maximum of six months
27 and may be updated, replaced, or obsoleted by other documents at any
28 time. It is inappropriate to use Internet-Drafts as reference
29 material or to cite them other than as "work in progress."
31 This Internet-Draft will expire on September 11, 2011.
33 Copyright Notice
35 Copyright (c) 2011 IETF Trust and the persons identified as the
36 document authors. All rights reserved.
38 This document is subject to BCP 78 and the IETF Trust's Legal
39 Provisions Relating to IETF Documents
40 (http://trustee.ietf.org/license-info) in effect on the date of
41 publication of this document. Please review these documents
42 carefully, as they describe your rights and restrictions with respect
43 to this document. Code Components extracted from this document must
44 include Simplified BSD License text as described in Section 4.e of
45 the Trust Legal Provisions and are provided without warranty as
46 described in the Simplified BSD License.
48 Table of Contents
50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
51 1.1. Conventions and Terminology . . . . . . . . . . . . . . . 3
52 2. A General Definition of Uncertainty . . . . . . . . . . . . . 3
53 2.1. Uncertainty as a Probability Distribution . . . . . . . . 4
54 2.2. Deprecation of the Terms Precision and Resolution . . . . 6
55 2.3. Accuracy as a Qualitative Concept . . . . . . . . . . . . 7
56 3. Uncertainty in Location . . . . . . . . . . . . . . . . . . . 7
57 3.1. Representation of Uncertainty and Confidence in PIDF-LO . 7
58 3.2. Uncertainty and Confidence for Civic Addresses . . . . . . 8
59 3.3. DHCP Location Configuration Information and Uncertainty . 9
60 4. Manipulation of Uncertainty . . . . . . . . . . . . . . . . . 9
61 4.1. Reduction of a Location Estimate to a Point . . . . . . . 10
62 4.1.1. Centroid Calculation . . . . . . . . . . . . . . . . . 10
63 4.1.1.1. Arc-Band Centroid . . . . . . . . . . . . . . . . 11
64 4.1.1.2. Polygon Centroid . . . . . . . . . . . . . . . . . 11
65 4.2. Conversion to Circle or Sphere . . . . . . . . . . . . . . 14
66 4.3. Three-Dimensional to Two-Dimensional Conversion . . . . . 15
67 4.4. Increasing and Decreasing Uncertainty and Confidence . . . 15
68 4.4.1. Rectangular Distributions . . . . . . . . . . . . . . 16
69 4.4.2. Normal Distributions . . . . . . . . . . . . . . . . . 16
70 4.5. Determining Whether a Location is Within a Given Region . 17
71 4.5.1. Determining the Area of Overlap for Two Circles . . . 18
72 4.5.2. Determining the Area of Overlap for Two Polygons . . . 19
73 5. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
74 5.1. Reduction to a Point or Circle . . . . . . . . . . . . . . 19
75 5.2. Increasing and Decreasing Confidence . . . . . . . . . . . 23
76 5.3. Matching Location Estimates to Regions of Interest . . . . 23
77 6. Security Considerations . . . . . . . . . . . . . . . . . . . 24
78 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24
79 8. Informative References . . . . . . . . . . . . . . . . . . . . 24
80 Appendix A. Conversion Between Cartesian and Geodetic
81 Coordinates in WGS84 . . . . . . . . . . . . . . . . 25
82 Appendix B. Calculating the Upward Normal of a Polygon . . . . . 27
83 B.1. Checking that a Polygon Upward Normal Points Up . . . . . 27
84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28
86 1. Introduction
88 Location information represents an estimation of the position of a
89 Target. Under ideal circumstances, a location estimate precisely
90 reflects the actual location of the Target. In reality, there are
91 many factors that introduce errors into the measurements that are
92 used to determine location estimates.
94 The process by which measurements are combined to generate a location
95 estimate is outside of the scope of work within the IETF. However,
96 the results of such a process are carried in IETF data formats and
97 protocols. This document outlines how uncertainty, and its
98 associated datum, confidence, are expressed and interpreted.
100 This document provides a common nomenclature for discussing
101 uncertainty and confidence as they relate to location information.
103 This document also provides guidance on how to manage location
104 information that includes uncertainty. Methods for expanding or
105 reducing uncertainty to obtain a required level of confidence are
106 described. Methods for determining the probability that a Target is
107 within a specified region based on their location estimate are
108 described. These methods are simplified by making certain
109 assumptions about the location estimate and are designed to be
110 applicable to location estimates in a relatively small area.
112 1.1. Conventions and Terminology
114 This document assumes a basic understanding of the principles of
115 mathematics, particularly statistics and geometry.
117 Some terminology is borrowed from [RFC3693] and
118 [I-D.ietf-geopriv-arch].
120 Mathematical formulae are presented using the following notation: add
121 "+", subtract "-", multiply "*", divide "/", power "^" and absolute
122 value "|x|". Precedence is indicated using parentheses.
123 Mathematical functions are represented by common abbreviations:
124 square root "sqrt(x)", sine "sin(x)", cosine "cos(x)", inverse cosine
125 "acos(x)", tangent "tan(x)", inverse tangent "atan(x)", error
126 function "erf(x)", and inverse error function "erfinv(x)".
128 2. A General Definition of Uncertainty
130 Uncertainty results from the limitations of measurement. In
131 measuring any observable quantity, errors from a range of sources
132 affect the result. Uncertainty is a quantification of what is known
133 about the observed quantity, either through the limitations of
134 measurement or through inherent variability of the quantity.
136 Uncertainty is most completely described by a probability
137 distribution. A probability distribution assigns a probability to
138 possible values for the quantity.
140 A probability distribution describing a measured quantity can be
141 arbitrarily complex and so it is desirable to find a simplified
142 model. One approach commonly taken is to reduce the probability
143 distribution to a confidence interval. Many alternative models are
144 used in other areas, but study of those is not the focus of this
145 document.
147 In addition to the central estimate of the observed quantity, a
148 confidence interval is succintly described by two values: an error
149 range and a confidence. The error range describes an interval and
150 the confidence describes an estimated upper bound on the probability
151 that a "true" value is found within the extents defined by the error.
153 In the following example, a measurement result for a length is shown
154 as a nominal value with additional information on error range (0.0043
155 meters) and confidence (95%).
157 e.g. x = 1.00742 +/- 0.0043 meters at 95% confidence
159 This result indicates that the measurement indicates that the value
160 of "x" between 1.00312 and 1.01172 meters with 95% probability. No
161 other assertion is made: in particular, this does not assert that x
162 is 1.00742.
164 This document uses the term _uncertainty_ to refer in general to the
165 concept as well as more specifically to refer to the error increment.
167 Uncertainty and confidence for location estimates can be derived in a
168 number of ways. This document does not attempt to enumerate the many
169 methods for determining uncertainty. [ISO.GUM] and [NIST.TN1297]
170 provide a set of general guidelines for determining and manipulating
171 measurement uncertainty. This document applies that general guidance
172 for consumers of location information.
174 2.1. Uncertainty as a Probability Distribution
176 The Probability Density Function (PDF) that is described by
177 uncertainty indicates the probability that the "true" value lies at
178 any one point. The shape of the probability distribution can vary
179 depending on the method that is used to determine the result. The
180 two probability density functions most generally applicable most
181 applicable to location information are considered in this document:
183 o The normal PDF (also referred to as a Gaussian PDF) is used where
184 a large number of small random factors contribute to errors. The
185 value used for the error range in a normal PDF is related to the
186 standard deviation of the distribution.
188 o A rectangular PDF is used where the errors are known to be
189 consistent across a limited range. A rectangular PDF can occur
190 where a single error source, such as a rounding error, is
191 significantly larger than other errors. A rectangular PDF is
192 often described by the half-width of the distribution; that is,
193 half the width of the distribution.
195 Each of these probability density functions can be characterized by
196 its center point, or mean, and its width. For a normal distribution,
197 uncertainty and confidence together are related to the standard
198 deviation (see Section 4.4). For a rectangular distribution, half of
199 the width of the distribution is used.
201 Figure 1 shows a normal and rectangular probability density function
202 with the mean (m) and standard deviation (s) labelled. The half-
203 width (h) of the rectangular distribution is also indicated.
205 ***** *** Normal PDF
206 ** : ** --- Rectangular PDF
207 ** : **
208 ** : **
209 .---------*---------------*---------.
210 | ** : ** |
211 | ** : ** |
212 | * <-- s -->: * |
213 | * : : : * |
214 | ** : ** |
215 | * : : : * |
216 | * : * |
217 |** : : : **|
218 ** : **
219 *** | : : : | ***
220 ***** | :<------ h ------>| *****
221 .****-------+.......:.........:.........:.......+-------*****.
222 m
224 Figure 1: Normal and Rectangular Probability Density Functions
226 For a given PDF, the value of the PDF describes the probability that
227 the "true" value is found at that point. Confidence for any given
228 interval is the total probability of the "true" value being in that
229 range, defined as the integral of the PDF over the interval.
231 The probability of the "true" value falling between two points is
232 found by finding the area under the curve between the points (that
233 is, the integral of the curve between the points). For any given
234 PDF, the area under the curve for the entire range from negative
235 infinity to positive infinity is 1 or (100%). Therefore, the
236 confidence over any interval of uncertainty is always less than
237 100%.
239 Figure 2 shows how confidence is determined for a normal
240 distribution. The area of the shaded region gives the confidence (c)
241 for the interval between "m-u" and "m+u".
243 *****
244 **:::::**
245 **:::::::::**
246 **:::::::::::**
247 *:::::::::::::::*
248 **:::::::::::::::**
249 **:::::::::::::::::**
250 *:::::::::::::::::::::*
251 *:::::::::::::::::::::::*
252 **:::::::::::::::::::::::**
253 *:::::::::::: c ::::::::::::*
254 *:::::::::::::::::::::::::::::*
255 **|:::::::::::::::::::::::::::::|**
256 ** |:::::::::::::::::::::::::::::| **
257 *** |:::::::::::::::::::::::::::::| ***
258 ***** |:::::::::::::::::::::::::::::| *****
259 .****..........!:::::::::::::::::::::::::::::!..........*****.
260 | | |
261 (m-u) m (m+u)
263 Figure 2: Confidence as the Integral of a PDF
265 In Section 4.4, methods are described for manipulating uncertainty if
266 the shape of the PDF is known.
268 2.2. Deprecation of the Terms Precision and Resolution
270 The terms _Precision_ and _Resolution_ are defined in RFC 3693
271 [RFC3693]. These definitions were intended to provide a common
272 nomenclature for discussing uncertainty; however, these particular
273 terms have many different uses in other fields and their definitions
274 are not sufficient to avoid confusion about their meaning. These
275 terms are unsuitable for use in relation to quantitative concepts
276 when discussing uncertainty and confidence in relation to location
277 information.
279 2.3. Accuracy as a Qualitative Concept
281 Uncertainty is a quantitative concept. The term _accuracy_ is useful
282 in describing, qualitatively, the general concepts of location
283 information. Accuracy is generally useful when describing
284 qualitative aspects of location estimates. Accuracy is not a
285 suitable term for use in a quantitative context.
287 For instance, it could be appropriate to say that a location estimate
288 with uncertainty "X" is more accurate than a location estimate with
289 uncertainty "2X" at the same confidence. It is not appropriate to
290 assign a number to "accuracy", nor is it appropriate to refer to any
291 component of uncertainty or confidence as "accuracy". That is, to
292 say that the "accuracy" for the first location estimate is "X" would
293 be an erroneous use of this term.
295 3. Uncertainty in Location
297 A _location estimate_ is the result of location determination. A
298 location estimate is subject to uncertainty like any other
299 observation. However, unlike a simple measure of a one dimensional
300 property like length, a location estimate is specified in two or
301 three dimensions.
303 Uncertainty in 2- or 3-dimensional locations can be described using
304 confidence intervals. The confidence interval for a location
305 estimate in two or three dimensional space is expressed as a subset
306 of that space. This document uses the term _region of uncertainty_
307 to refer to the area or volume that describes the confidence
308 interval.
310 Areas or volumes that describe regions of uncertainty can be formed
311 by the combination of two or three one-dimensional ranges, or more
312 complex shapes could be described.
314 3.1. Representation of Uncertainty and Confidence in PIDF-LO
316 A set of shapes suitable for the expression of uncertainty in
317 location estimates in the Presence Information Data Format - Location
318 Object (PIDF-LO) are described in [GeoShape]. These shapes are the
319 recommended form for the representation of uncertainty in PIDF-LO
320 [RFC4119] documents.
322 The PIDF-LO does not include an indication of confidence, but that
323 confidence is 95%, by definition in [RFC5491]. Similarly, the
324 PIDF-LO format does not provide an indication of the shape of the
325 PDF.
327 Absence of uncertainty information in a PIDF-LO document does not
328 indicate that there is no uncertainty in the location estimate.
329 Uncertainty might not have been calculated for the estimate, or it
330 may be withheld for privacy purposes.
332 If the Point shape is used, confidence and uncertainty are unknown; a
333 receiver can either assume a confidence of 0% or infinite
334 uncertainty. The same principle applies on the altitude axis for
335 two-dimension shapes like the Circle.
337 3.2. Uncertainty and Confidence for Civic Addresses
339 Civic addresses [RFC5139] inherently include uncertainty, based on
340 the area of the most precise element that is specified. Uncertainty
341 is effectively defined by the presence or absence of elements --
342 elements that are not present are deemed to be uncertain.
344 To apply the concept of uncertainty to civic addresses, it is helpful
345 to unify the conceptual models of civic address with geodetic
346 location information.
348 Note: This view is one perspective on the process of geo-coding -
349 the translation of a civic address to a geodetic location.
351 In the unified view, a civic address defines a series of (sometimes
352 non-orthogonal) spatial partitions. The first is the implicit
353 partition that identifies the surface of the earth and the space near
354 the surface. The second is the country. Each label that is included
355 in a civic address provides information about a different set of
356 spatial partitions. Some partions require slight adjustments from a
357 standard interpretation: for instance, a road includes all properties
358 that adjoin the street. Each label might need to be interpreted with
359 other values to provide context.
361 As a value at each level is interpreted, one or more spatial
362 partitions at that level are selected, and all other partitions of
363 that type are excluded. For non-orthogonal partitions, only the
364 portion of the partition that fits within the existing space is
365 selected. This is what distinguishes King Street in Sydney from King
366 Street in Melbourne. Each defined element selects a partition of
367 space. The resulting location is the intersection of all selected
368 spaces.
370 The resulting spatial partition can be considered to represent a
371 region of uncertainty. At no stage does this process select a point;
372 although, as spaces get smaller this distinction might have no
373 practical significance and an approximation if a point could be used.
375 Uncertainty in civic addresses can be increased by removing elements.
376 This doesn't necessarily improve confidence in the same way that
377 arbitrarily increasing uncertainty in a geodetic location doesn't
378 increase confidence.
380 3.3. DHCP Location Configuration Information and Uncertainty
382 Location information is often measured in two or three dimensions;
383 expressions of uncertainty in one dimension only are rare. The
384 "resolution" parameters in [RFC3825] provide an indication of
385 uncertainty in one dimension.
387 [RFC3825] defines a means for representing uncertainty, but a value
388 for confidence is not specified. A default value of 95% confidence
389 can be assumed for the combination of the uncertainty on each axis.
390 That is, the confidence of the resultant rectangular polygon or prism
391 is 95%.
393 4. Manipulation of Uncertainty
395 This section deals with manipulation of location information that
396 contains uncertainty.
398 The following rules generally apply when manipulating location
399 information:
401 o Where calculations are performed on coordinate information, these
402 should be performed in Cartesian space and the results converted
403 back to latitude, longitude and altitude. A method for converting
404 to and from Cartesian coordinates is included in Appendix A.
406 While some approximation methods are useful in simplifying
407 calculations, treating latitude and longitude as Cartesian axes
408 is never advisable. The two axes are not orthogonal. Errors
409 can arise from the curvature of the earth and from the
410 convergence of longitude lines.
412 o Normal rounding rules do not apply when rounding uncertainty.
413 When rounding, the region of uncertainty always increases (that
414 is, errors are rounded up) and confidence is always rounded down
415 (see [NIST.TN1297]). This means that any manipulation of
416 uncertainty is a non-reversible operation; each manipulation can
417 result in the loss of some information.
419 4.1. Reduction of a Location Estimate to a Point
421 Manipulating location estimates that include uncertainty information
422 requires additional complexity in systems. In some cases, systems
423 only operate on definitive values, that is, a single point.
425 This section describes algorithms for reducing location estimates to
426 a simple form without uncertainty information. Having a consistent
427 means for reducing location estimates allows for interaction between
428 applications that are able to use uncertainty information and those
429 that cannot.
431 Note: Reduction of a location estimate to a point constitutes a
432 reduction in information. Removing uncertainty information can
433 degrade results in some applications. Also, there is a natural
434 tendency to misinterpret a point location as representing a
435 location without uncertainty. This could lead to more serious
436 errors. Therefore, these algorithms should only be applied where
437 necessary.
439 Several different approaches can be taken when reducing a location
440 estimate to a point. Different methods each make a set of
441 assumptions about the properties of the PDF and the selected point;
442 no one method is more "correct" than any other. For any given region
443 of uncertainty, selecting an arbitrary point within the area could be
444 considered valid; however, given the aforementioned problems with
445 point locations, a more rigorous approach is appropriate.
447 Given a result with a known distribution, selecting the point within
448 the area that has the highest probability is a more rigorous method.
449 Alternatively, a point could be selected that minimizes the overall
450 error; that is, it minimises the expected value of the difference
451 between the selected point and the "true" value.
453 If a rectangular distribution is assumed, the centroid of the area or
454 volume minimizes the overall error. Minimizing the error for a
455 normal distribution is mathematically complex. Therefore, this
456 document opts to select the centroid of the region of uncertainty
457 when selecting a point.
459 4.1.1. Centroid Calculation
461 For regular shapes, such as Circle, Sphere, Ellipse and Ellipsoid,
462 this approach equates to the center point of the region. For regions
463 of uncertainty that are expressed as regular Polygons and Prisms the
464 center point is also the most appropriate selection.
466 For the Arc-Band shape and non-regular Polygons and Prisms, selecting
467 the centroid of the area or volume minimizes the overall error. This
468 assumes that the PDF is rectangular.
470 Note: The centroid of a concave Polygon or Arc-Band shape is not
471 necessarily within the region of uncertainty.
473 4.1.1.1. Arc-Band Centroid
475 The centroid of the Arc-Band shape is found along a line that bisects
476 the arc. The centroid can be found at the following distance from
477 the starting point of the arc-band (assuming an arc-band with an
478 inner radius of "r", outer radius "R", start angle "a", and opening
479 angle "o"):
481 d = 4 * sin(o/2) * (R*R + R*r + r*r) / (3*o*(R + r))
483 This point can be found along the line that bisects the arc; that is,
484 the line at an angle of "a + (o/2)". Negative values are possible if
485 the angle of opening is greater than 180 degrees; negative values
486 indicate that the centroid is found along the angle
487 "a + (o/2) + 180".
489 4.1.1.2. Polygon Centroid
491 Calculating a centroid for the Polygon and Prism shapes is more
492 complex. Polygons that are specified using geodetic coordinates are
493 not necessarily coplanar. For Polygons that are specified without an
494 altitude, choose a value for altitude before attempting this process;
495 an altitude of 0 is acceptable.
497 The method described in this section is simplified by assuming
498 that the surface of the earth is locally flat. This method
499 degrades as polygons become larger; see [GeoShape] for
500 recommendations on polygon size.
502 The polygon is translated to a new coordinate system that has an x-y
503 plane roughly parallel to the polygon. This enables the elimination
504 of z-axis values and calculating a centroid can be done using only x
505 and y coordinates. This requires that the upward normal for the
506 polygon is known.
508 To translate the polygon coordinates, apply the process described in
509 Appendix B to find the normal vector "N = [Nx,Ny,Nz]". This value
510 should be made a unit vector to ensure that the transformation matrix
511 is a special orthogonal matrix. From this vector, select two vectors
512 that are perpendicular to this vector and combine these into a
513 transformation matrix.
515 If "Nx" and "Ny" are non-zero, the matrices in Figure 3 can be used,
516 given "p = sqrt(Nx^2 + Ny^2)". More transformations are provided
517 later in this section for cases where "Nx" or "Ny" are zero.
519 [ -Ny/p Nx/p 0 ] [ -Ny/p -Nx*Nz/p Nx ]
520 T = [ -Nx*Nz/p -Ny*Nz/p p ] T' = [ Nx/p -Ny*Nz/p Ny ]
521 [ Nx Ny Nz ] [ 0 p Nz ]
522 (Transform) (Reverse Transform)
524 Figure 3: Recommended Transformation Matrices
526 To apply a transform to each point in the polygon, form a matrix from
527 the ECEF coordinates and use matrix multiplication to determine the
528 translated coordinates.
530 [ -Ny/p Nx/p 0 ] [ x[1] x[2] x[3] ... x[n] ]
531 [ -Nx*Nz/p -Ny*Nz/p p ] * [ y[1] y[2] y[3] ... y[n] ]
532 [ Nx Ny Nz ] [ z[1] z[2] z[3] ... z[n] ]
534 [ x'[1] x'[2] x'[3] ... x'[n] ]
535 = [ y'[1] y'[2] y'[3] ... y'[n] ]
536 [ z'[1] z'[2] z'[3] ... z'[n] ]
538 Figure 4: Transformation
540 Alternatively, direct multiplication can be used to achieve the same
541 result:
543 x'[i] = -Ny * x[i] / p + Nx * y[i] / p
545 y'[i] = -Nx * Nz * x[i] / p - Ny * Nz * y[i] / p + p * z[i]
547 z'[i] = Nx * x[i] + Ny * y[i] + Nz * z[i]
549 The first and second rows of this matrix ("x'" and "y'") contain the
550 values that are used to calculate the centroid of the polygon. To
551 find the centroid of this polygon, first find the area using:
553 A = sum from i=1..n of (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / 2
555 For these formulae, treat each set of coordinates as circular, that
556 is "x'[0] == x'[n]" and "x'[n+1] == x'[1]". Based on the area, the
557 centroid along each axis can be determined by:
559 Cx' = sum (x'[i]+x'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A)
561 Cy' = sum (y'[i]+y'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A)
563 Note: The formula for the area of a polygon will return a negative
564 value if the polygon is specified in clockwise direction. This
565 can be used to determine the orientation of the polygon.
567 The third row contains a distance from a plane parallel to the
568 polygon. If the polygon is coplanar, then the values for "z'" are
569 identical; however, the constraints recommended in [RFC5491] mean
570 that this is rarely the case. To determine "Cz'", average these
571 values:
573 Cz' = sum z'[i] / n
575 Once the centroid is known in the transformed coordinates, these can
576 be transformed back to the original coordinate system. The reverse
577 transformation is shown in Figure 5.
579 [ -Ny/p -Nx*Nz/p Nx ] [ Cx' ] [ Cx ]
580 [ Nx/p -Ny*Nz/p Ny ] * [ Cy' ] = [ Cy ]
581 [ 0 p Nz ] [ sum of z'[i] / n ] [ Cz ]
583 Figure 5: Reverse Transformation
585 The reverse transformation can be applied directly as follows:
587 Cx = -Ny * Cx' / p - Nx * Nz * Cy' / p + Nx * Cz'
589 Cy = Nx * Cx' / p - Ny * Nz * Cy' / p + Ny * Cz'
591 Cz = p * Cy' + Nz * Cz'
593 The ECEF value "[Cx,Cy,Cz]" can then be converted back to geodetic
594 coordinates. Given a polygon that is defined with no altitude or
595 equal altitudes for each point, the altitude of the result can either
596 be ignored or reset after converting back to a geodetic value.
598 The centroid of the Prism shape is found by finding the centroid of
599 the base polygon and raising the point by half the height of the
600 prism. This can be added to altitude of the final result;
601 alternatively, this can be added to "Cz'", which ensures that
602 negative height is correctly applied to polygons that are defined in
603 a "clockwise" direction.
605 The recommended transforms only apply if "Nx" and "Ny" are non-zero.
606 If the normal vector is "[0,0,1]" (that is, along the z-axis), then
607 no transform is necessary. Similarly, if the normal vector is
608 "[0,1,0]" or "[1,0,0]", avoid the transformation and use the x and z
609 coordinates or y and z coordinates (respectively) in the centroid
610 calculation phase. If either "Nx" or "Ny" are zero, the alternative
611 transform matrices in Figure 6 can be used. The reverse transform is
612 the transpose of this matrix.
614 if Nx == 0: | if Ny == 0:
615 [ 0 -Nz Ny ] [ 0 1 0 ] | [ -Nz 0 Nx ]
616 T = [ 1 0 0 ] T' = [ -Nz 0 Ny ] | T = T' = [ 0 1 0 ]
617 [ 0 Ny Nz ] [ Ny 0 Nz ] | [ Nx 0 Nz ]
619 Figure 6: Alternative Transformation Matrices
621 4.2. Conversion to Circle or Sphere
623 The Circle or Sphere are simple shapes that suit a range of
624 applications. A circle or sphere contains fewer units of data to
625 manipulate, which simplifies operations on location estimates.
627 The simplest method for converting a location estimate to a Circle or
628 Sphere shape is to determine the centroid and then find the longest
629 distance to any point in the region of uncertainty to that point.
630 This distance can be determined based on the shape type:
632 Circle/Sphere: No conversion necessary.
634 Ellipse/Ellipsoid: The greater of either semi-major axis or altitude
635 uncertainty.
637 Polygon/Prism: The distance to the furthest vertex of the polygon
638 (for a Prism, it is only necessary to check points on the base).
640 Arc-Band: The furthest length from the centroid to the points where
641 the inner and outer arc end. This distance can be calculated by
642 finding the larger of the two following formulae:
644 X = sqrt( d*d + R*R - 2*d*R*cos(o/2) )
646 x = sqrt( d*d + r*r - 2*d*r*cos(o/2) )
648 Once the Circle or Sphere shape is found, the associated confidence
649 can be increased if the result is known to follow a normal
650 distribution. However, this is a complicated process and provides
651 limited benefit. In many cases it also violates the constraint that
652 confidence in each dimension be the same. Confidence should be
653 unchanged when performing this conversion.
655 Two dimensional shapes are converted to a Circle; three dimensional
656 shapes are converted to a Sphere.
658 4.3. Three-Dimensional to Two-Dimensional Conversion
660 A three-dimensional shape can be easily converted to a two-
661 dimensional shape by removing the altitude component. A sphere
662 becomes a circle; a prism becomes a polygon; an ellipsoid becomes an
663 ellipse. Each conversion is simple, requiring only the removal of
664 those elements relating to altitude.
666 The altitude is unspecified for a two-dimensional shape and therefore
667 has unlimited uncertainty along the vertical axis. The confidence
668 for the two-dimensional shape is thus higher than the three-
669 dimensional shape. Assuming equal confidence on each axis, the
670 confidence of the circle can be increased using the following
671 approximate formula:
673 C[2d] >= C[3d] ^ (2/3)
675 "C[2d]" is the confidence of the two-dimensional shape and "C[3d]" is
676 the confidence of the three-dimensional shape. For example, a Sphere
677 with a confidence of 95% can be simplified to a Circle of equal
678 radius with confidence of 96.6%.
680 4.4. Increasing and Decreasing Uncertainty and Confidence
682 The combination of uncertainty and confidence provide a great deal of
683 information about the nature of the data that is being measured. If
684 both uncertainty, confidence and PDF are known, certain information
685 can be extrapolated. In particular, the uncertainty can be scaled to
686 meet a desired confidence or the confidence for a particular region
687 of uncertainty can be found.
689 In general, confidence decreases as the region of uncertainty
690 decreases in size and confidence increases as the region of
691 uncertainty increases in size. However, this depends on the PDF;
692 expanding the region of uncertainty for a rectangular distribution
693 has no effect on confidence without additional information. If the
694 region of uncertainty is increased during the process of obfuscation
695 (see [I-D.thomson-geopriv-location-obscuring]), then the confidence
696 cannot be increased.
698 A region of uncertainty that is reduced in size always has a lower
699 confidence.
701 A region of uncertainty that has an unknown PDF shape cannot be
702 reduced in size reliably. The region of uncertainty can be expanded,
703 but only if confidence is not increased.
705 This section makes the simplifying assumption that location
706 information is symmetrically and evenly distributed in each
707 dimension. This is not necessarily true in practice. If better
708 information is available, alternative methods might produce better
709 results.
711 4.4.1. Rectangular Distributions
713 Uncertainty that follows a rectangular distribution can only be
714 decreased in size. Since the PDF is constant over the region of
715 uncertainty, the resulting confidence is determined by the following
716 formula:
718 Cr = Co * Ur / Uo
720 Where "Uo" and "Ur" are the sizes of the original and reduced regions
721 of uncertainty (either the area or the volume of the region); "Co"
722 and "Cb" are the confidence values associated with each region.
724 Information is lost by decreasing the region of uncertainty for a
725 rectangular distribution. Once reduced in size, the uncertainty
726 region cannot subsequently be increased in size.
728 4.4.2. Normal Distributions
730 Uncertainty and confidence can be both increased and decreased for a
731 normal distribution. However, the process is more complicated.
733 For a normal distribution, uncertainty and confidence are related to
734 the standard deviation of the function. The following function
735 defines the relationship between standard deviation, uncertainty and
736 confidence along a single axis:
738 S[x] = U[x] / ( sqrt(2) * erfinv(C[x]) )
740 Where "S[x]" is the standard deviation, "U[x]" is the uncertainty and
741 "C[x]" is the confidence along a single axis. "erfinv" is the inverse
742 error function.
744 Scaling a normal distribution in two dimensions requires several
745 assumptions. Firstly, it is assumed that the distribution along each
746 axis is independent. Secondly, the confidence for each axis is the
747 same. Therefore, the confidence along each axis can be assumed to
748 be:
750 C[x] = Co ^ (1/n)
752 Where "C[x]" is the confidence along a single axis and "Co" is the
753 overall confidence and "n" is the number of dimensions in the
754 uncertainty.
756 Therefore, to find the uncertainty for each axis at a desired
757 confidence, "Cd", apply the following formula:
759 Ud[x] <= U[x] * (erfinv(Cd ^ (1/n)) / erfinv(Co ^ (1/n)))
761 For regular shapes, this formula can be applied as a scaling factor
762 in each dimension to reach a required confidence.
764 4.5. Determining Whether a Location is Within a Given Region
766 A number of applications require that a judgement be made about
767 whether a Target is within a given region of interest. Given a
768 location estimate with uncertainty, this judgement can be difficult.
769 A location estimate represents a probability distribution, and the
770 true location of the Target cannot be definitively known. Therefore,
771 the judgement relies on determining the probability that the Target
772 is within the region.
774 The probability that the Target is within a particular region is
775 found by integrating the PDF over the region. For a normal
776 distribution, there are no analytical methods that can be used to
777 determine the integral of the two or three dimensional PDF over an
778 arbitrary region. The complexity of numerical methods is also too
779 great to be useful in many applications; for example, finding the
780 integral of the PDF in two or three dimensions across the overlap
781 between the uncertainty region and the target region. If the PDF is
782 unknown, no determination can be made. When judging whether a
783 location is within a given region, uncertainties using these PDFs can
784 be assumed to be rectangular. If this assumption is made, the
785 confidence should be scaled to 95%, if possible.
787 Note: The selection of confidence has a significant impact on the
788 final result. Only use a different confidence if an uncertainty
789 value for 95% confidence cannot be found.
791 Given the assumption of a rectangular distribution, the probability
792 that a Target is found within a given region is found by first
793 finding the area (or volume) of overlap between the uncertainty
794 region and the region of interest. This is multiplied by the
795 confidence of the location estimate to determine the probability.
796 Figure 7 shows an example of finding the area of overlap between the
797 region of uncertainty and the region of interest.
799 _.-""""-._
800 .' `. _ Region of
801 / \ / Uncertainty
802 ..+-"""--.. |
803 .-' | :::::: `-. |
804 ,' | :: Ao ::: `. |
805 / \ :::::::::: \ /
806 / `._ :::::: _.X
807 | `-....-' |
808 | |
809 | |
810 \ /
811 `. .' \_ Region of
812 `._ _.' Interest
813 `--..___..--'
815 Figure 7: Area of Overlap Between Two Circular Regions
817 Once the area of overlap, "Ao", is known, the probability that the
818 Target is within the region of interest, "Pi", is:
820 Pi = Co * Ao / Au
822 Given that the area of the region of uncertainty is "Au" and the
823 confidence is "Co".
825 This probability is often input to a decision process that has a
826 limited set of outcomes; therefore, a threshold value needs to be
827 selected. Depending on the application, different threshold
828 probabilities might be selected. In the absence of specific
829 recommendations, this document suggests that the probability be
830 greater than 50% before a decision is made. If the decision process
831 selects between two or more regions, as is required by [RFC5222],
832 then the region with the highest probability can be selected.
834 4.5.1. Determining the Area of Overlap for Two Circles
836 Determining the area of overlap between two arbitrary shapes is a
837 non-trivial process. Reducing areas to circles (see Section 4.2)
838 enables the application of the following process.
840 Given the radius of the first circle "r", the radius of the second
841 circle "R" and the distance between their center points "d", the
842 following set of formulas provide the area of overlap "Ao".
844 o If the circles don't overlap, that is "d >= r+R", "Ao" is zero.
846 o If one of the two circles is entirely within the other, that is
847 "d <= |r-R|", the area of overlap is the area of the smaller
848 circle.
850 o Otherwise, if the circles partially overlap, that is "d < r+R" and
851 "d > |r-R|", find "Ao" using:
853 a = (r^2 - R^2 + d^2)/(2*d)
855 Ao = r^2*acos(a/r) + R^2*acos((d - a)/R) - d*sqrt(r^2 - a^2)
857 A value for "d" can be determined by converting the center points to
858 Cartesian coordinates and calculating the distance between the two
859 center points:
861 d = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2)
863 4.5.2. Determining the Area of Overlap for Two Polygons
865 A calculation of overlap based on polygons can give better results
866 than the circle-based method. However, efficient calculation of
867 overlapping area is non-trivial. Algorithms such as Vatti's clipping
868 algorithm [Vatti92] can be used.
870 For large polygonal areas, it might be that geodesic interpolation is
871 used. In these cases, altitude is also frequently omitted in
872 describing the polygon. For such shapes, a planar projection can
873 still give a good approximation of the area of overlap if the larger
874 area polygon is projected onto the local tangent plane of the
875 smaller. This is only possible if the only area of interest is that
876 contained within the smaller polygon. Where the entire area of the
877 larger polygon is of interest, geodesic interpolation is necessary.
879 5. Examples
881 This section presents some examples of how to apply the methods
882 described in Section 4.
884 5.1. Reduction to a Point or Circle
886 Alice receives a location estimate from her LIS that contains a
887 ellipsoidal region of uncertainty. This information is provided at
888 19% confidence with a normal PDF. A PIDF-LO extract for this
889 information is shown in Figure 8.
891
892
893
894 -34.407242 150.882518 34
895
896 7.7156
897
898
899 3.31
900
901
902 28.7
903
904
905 43
906
907
908
909
910
912 Figure 8
914 This information can be reduced to a point simply by extracting the
915 center point, that is [-34.407242, 150.882518, 34].
917 If some limited uncertainty were required, the estimate could be
918 converted into a circle or sphere. To convert to a sphere, the
919 radius is the largest of the semi-major, semi-minor and vertical
920 axes; in this case, 28.7 meters.
922 However, if only a circle is required, the altitude can be dropped as
923 can the altitude uncertainty (the vertical axis of the ellipsoid),
924 resulting in a circle at [-34.407242, 150.882518] of radius 7.7156
925 meters.
927 Bob receives a location estimate with a Polygon shape. This
928 information is shown in Figure 9.
930
931
932
933
934 -33.856625 151.215906 -33.856299 151.215343
935 -33.856326 151.214731 -33.857533 151.214495
936 -33.857720 151.214613 -33.857369 151.215375
937 -33.856625 151.215906
938
939
940
941
943 Figure 9
945 To convert this to a polygon, each point is firstly assigned an
946 altitude of zero and converted to ECEF coordinates (see Appendix A).
947 Then a normal vector for this polygon is found (see Appendix B). The
948 results of each of these stages is shown in Figure 10. Note that the
949 numbers shown are all rounded; no rounding is possible during this
950 process since rounding would contribute significant errors.
952 Polygon in ECEF coordinate space
953 (repeated point omitted and transposed to fit):
954 [ -4.6470e+06 2.5530e+06 -3.5333e+06 ]
955 [ -4.6470e+06 2.5531e+06 -3.5332e+06 ]
956 pecef = [ -4.6470e+06 2.5531e+06 -3.5332e+06 ]
957 [ -4.6469e+06 2.5531e+06 -3.5333e+06 ]
958 [ -4.6469e+06 2.5531e+06 -3.5334e+06 ]
959 [ -4.6469e+06 2.5531e+06 -3.5333e+06 ]
961 Normal Vector: n = [ -0.72782 0.39987 -0.55712 ]
963 Transformation Matrix:
964 [ -0.48152 -0.87643 0.00000 ]
965 t = [ -0.48828 0.26827 0.83043 ]
966 [ -0.72782 0.39987 -0.55712 ]
968 Transformed Coordinates:
969 [ 8.3206e+01 1.9809e+04 6.3715e+06 ]
970 [ 3.1107e+01 1.9845e+04 6.3715e+06 ]
971 pecef' = [ -2.5528e+01 1.9842e+04 6.3715e+06 ]
972 [ -4.7367e+01 1.9708e+04 6.3715e+06 ]
973 [ -3.6447e+01 1.9687e+04 6.3715e+06 ]
974 [ 3.4068e+01 1.9726e+04 6.3715e+06 ]
976 Two dimensional polygon area: A = 12600 m^2
977 Two-dimensional polygon centroid: C' = [ 8.8184e+00 1.9775e+04 ]
979 Average of pecef' z coordinates: 6.3715e+06
981 Reverse Transformation Matrix:
982 [ -0.48152 -0.48828 -0.72782 ]
983 t' = [ -0.87643 0.26827 0.39987 ]
984 [ 0.00000 0.83043 -0.55712 ]
986 Polygon centroid (ECEF): C = [ -4.6470e+06 2.5531e+06 -3.5333e+06 ]
987 Polygon centroid (Geo): Cg = [ -33.856926 151.215102 -4.9537e-04 ]
989 Figure 10
991 The point conversion for the polygon uses the final result, "Cg",
992 ignoring the altitude since the original shape did not include
993 altitude.
995 To convert this to a circle, take the maximum distance in ECEF
996 coordinates from the center point to each of the points. This
997 results in a radius of 99.1 meters. Confidence is unchanged.
999 5.2. Increasing and Decreasing Confidence
1001 Assuming that confidence is known to be 19% for Alice's location
1002 information. This is typical value for a three-dimensional ellipsoid
1003 uncertainty of normal distribution where the standard deviation is
1004 supplied in each dimension. The confidence associated with Alice's
1005 location estimate is quite low for many applications. Since the
1006 estimate is known to follow a normal distribution, the method in
1007 Section 4.4.2 can be used. Each axis can be scaled by:
1009 scale = erfinv(0.95^(1/3)) / erfinv(0.19^(1/3)) = 2.9937
1011 Ensuring that rounding always increases uncertainty, the location
1012 estimate at 95% includes a semi-major axis of 23.1, a semi-minor axis
1013 of 10 and a vertical axis of 86.
1015 Bob's location estimate covers an area of approximately 12600 square
1016 meters. If the estimate follows a rectangular distribution, the
1017 region of uncertainty can be reduced in size. To find the confidence
1018 that he is within the smaller area of the concert hall, given by the
1019 polygon [-33.856473, 151.215257; -33.856322, 151.214973;
1020 -33.856424, 151.21471; -33.857248, 151.214753;
1021 -33.857413, 151.214941; -33.857311, 151.215128]. To use this new
1022 region of uncertainty, find its area using the same translation
1023 method described in Section 4.1.1.2, which is 4566.2 square meters.
1024 The confidence associated with the smaller area is therefore 95% *
1025 4566.2 / 12600 = 34%.
1027 5.3. Matching Location Estimates to Regions of Interest
1029 Suppose than a circular area is defined centered at
1030 [-33.872754, 151.20683] with a radius of 1950 meters. To determine
1031 whether Bob is found within this area, we apply the method in
1032 Section 4.5. Using the converted Circle shape for Bob's location,
1033 the distance between these points is found to be 1915.26 meters. The
1034 area of overlap between Bob's location estimate and the region of
1035 interest is therefore 2209 square meters and the area of Bob's
1036 location estimate is 30853 square meters. This gives the probability
1037 that Bob is less than 1950 meters from the selected point as 67.8%.
1039 Note that if 1920 meters were chosen for the distance from the
1040 selected point, the area of overlap is only 16196 square meters and
1041 the confidence is 49.8%. Therefore, it is marginally more likely
1042 that Bob is outside the region of interest, despite the center point
1043 of his location estimate being within the region.
1045 6. Security Considerations
1047 This document describes methods for managing and manipulating
1048 uncertainty in location. No specific security concerns arise from
1049 most of the information provided.
1051 7. Acknowledgements
1053 Peter Rhodes provided assistance with some of the mathematical
1054 groundwork on this document. Dan Cornford provided a detailed review
1055 and many terminology corrections.
1057 8. Informative References
1059 [Convert] Burtch, R., "A Comparison of Methods Used in Rectangular
1060 to Geodetic Coordinate Transformations", April 2006.
1062 [GeoShape]
1063 Thomson, M. and C. Reed, "GML 3.1.1 PIDF-LO Shape
1064 Application Schema for use by the Internet Engineering
1065 Task Force (IETF)", Candidate OpenGIS Implementation
1066 Specification 06-142r1, Version: 1.0, April 2007.
1068 [I-D.ietf-geopriv-arch]
1069 Barnes, R., Lepinski, M., Cooper, A., Morris, J.,
1070 Tschofenig, H., and H. Schulzrinne, "An Architecture for
1071 Location and Location Privacy in Internet Applications",
1072 draft-ietf-geopriv-arch-03 (work in progress),
1073 October 2010.
1075 [I-D.ietf-geopriv-policy]
1076 Schulzrinne, H., Tschofenig, H., Morris, J., Cuellar, J.,
1077 and J. Polk, "Geolocation Policy: A Document Format for
1078 Expressing Privacy Preferences for Location Information",
1079 draft-ietf-geopriv-policy-22 (work in progress),
1080 October 2010.
1082 [I-D.thomson-geopriv-location-obscuring]
1083 Thomson, M., "Obscuring Location",
1084 draft-thomson-geopriv-location-obscuring-02 (work in
1085 progress), January 2011.
1087 [ISO.GUM] ISO/IEC, "Guide to the expression of uncertainty in
1088 measurement (GUM)", Guide 98:1995, 1995.
1090 [NIST.TN1297]
1091 Taylor, B. and C. Kuyatt, "Guidelines for Evaluating and
1092 Expressing the Uncertainty of NIST Measurement Results",
1093 Technical Note 1297, Sep 1994.
1095 [RFC3693] Cuellar, J., Morris, J., Mulligan, D., Peterson, J., and
1096 J. Polk, "Geopriv Requirements", RFC 3693, February 2004.
1098 [RFC3694] Danley, M., Mulligan, D., Morris, J., and J. Peterson,
1099 "Threat Analysis of the Geopriv Protocol", RFC 3694,
1100 February 2004.
1102 [RFC3825] Polk, J., Schnizlein, J., and M. Linsner, "Dynamic Host
1103 Configuration Protocol Option for Coordinate-based
1104 Location Configuration Information", RFC 3825, July 2004.
1106 [RFC4119] Peterson, J., "A Presence-based GEOPRIV Location Object
1107 Format", RFC 4119, December 2005.
1109 [RFC5139] Thomson, M. and J. Winterbottom, "Revised Civic Location
1110 Format for Presence Information Data Format Location
1111 Object (PIDF-LO)", RFC 5139, February 2008.
1113 [RFC5222] Hardie, T., Newton, A., Schulzrinne, H., and H.
1114 Tschofenig, "LoST: A Location-to-Service Translation
1115 Protocol", RFC 5222, August 2008.
1117 [RFC5491] Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV
1118 Presence Information Data Format Location Object (PIDF-LO)
1119 Usage Clarification, Considerations, and Recommendations",
1120 RFC 5491, March 2009.
1122 [Sunday02]
1123 Sunday, D., "Fast polygon area and Newell normal
1124 computation", Journal of Graphics Tools JGT, 7(2):9-
1125 13,2002, 2002, .
1127 [Vatti92] Vatti, B., "A generic solution to polygon clipping",
1128 Communications of the ACM Vol35, Issue7, pp56-63, 1992,
1129 .
1131 [WGS84] US National Imagery and Mapping Agency, "Department of
1132 Defense (DoD) World Geodetic System 1984 (WGS 84), Third
1133 Edition", NIMA TR8350.2, January 2000.
1135 Appendix A. Conversion Between Cartesian and Geodetic Coordinates in
1136 WGS84
1138 The process of conversion from geodetic (latitude, longitude and
1139 altitude) to earth-centered, earth-fixed (ECEF) Cartesian coordinates
1140 is relatively simple.
1142 In this section, the following constants and derived values are used
1143 from the definition of WGS84 [WGS84]:
1145 {radius of ellipsoid} R = 6378137 meters
1147 {inverse flattening} 1/f = 298.257223563
1149 {first eccentricity squared} e^2 = f * (2 - f)
1151 {second eccentricity squared} e'^2 = e^2 * (1 - e^2)
1153 To convert geodetic coordinates (latitude, longitude, altitude) to
1154 ECEF coordinates (X, Y, Z), use the following relationships:
1156 N = R / sqrt(1 - e^2 * sin(latitude)^2)
1158 X = (N + altitude) * cos(latitude) * cos(longitude)
1160 Y = (N + altitude) * cos(latitude) * sin(longitude)
1162 Z = (N*(1 - e^2) + altitude) * sin(latitude)
1164 The reverse conversion requires more complex computation and most
1165 methods introduce some error in latitude and altitude. A range of
1166 techniques are described in [Convert]. A variant on the method
1167 originally proposed by Bowring, which results in an acceptably small
1168 error, is described by the following:
1170 p = sqrt(X^2 + Y^2)
1172 r = sqrt(X^2 + Y^2 + Z^2)
1174 u = atan((1-f) * Z * (1 + e'^2 * (1-f) * R / r) / p)
1176 latitude = atan((Z + e'^2 * (1-f) * R * sin(u)^3)
1177 / (p - e^2 * R * cos(u)^3))
1179 longitude = atan(Y / X)
1181 altitude = sqrt((p - R * cos(u))^2 + (Z - (1-f) * R * sin(u))^2)
1183 If the point is near the poles, that is "p < 1", the value for
1184 altitude that this method produces is unstable. A simpler method for
1185 determining the altitude of a point near the poles is:
1187 altitude = |Z| - R * (1 - f)
1189 Appendix B. Calculating the Upward Normal of a Polygon
1191 For a polygon that is guaranteed to be convex and coplanar, the
1192 upward normal can be found by finding the vector cross product of
1193 adjacent edges.
1195 For more general cases the Newell method of approximation described
1196 in [Sunday02] may be applied. In particular, this method can be used
1197 if the points are only approximately coplanar, and for non-convex
1198 polygons.
1200 This process requires a Cartesian coordinate system. Therefore,
1201 convert the geodetic coordinates of the polygon to Cartesian, ECEF
1202 coordinates (Appendix A). If no altitude is specified, assume an
1203 altitude of zero.
1205 This method can be condensed to the following set of equations:
1207 Nx = sum from i=1..n of (y[i] * (z[i+1] - z[i-1]))
1209 Ny = sum from i=1..n of (z[i] * (x[i+1] - x[i-1]))
1211 Nz = sum from i=1..n of (x[i] * (y[i+1] - y[i-1]))
1213 For these formulae, the polygon is made of points
1214 "(x[1], y[1], z[1])" through "(x[n], y[n], x[n])". Each array is
1215 treated as circular, that is, "x[0] == x[n]" and "x[n+1] == x[1]".
1217 To translate this into a unit-vector; divide each component by the
1218 length of the vector:
1220 Nx' = Nx / sqrt(Nx^2 + Ny^2 + Nz^2)
1222 Ny' = Ny / sqrt(Nx^2 + Ny^2 + Nz^2)
1224 Nz' = Nz / sqrt(Nx^2 + Ny^2 + Nz^2)
1226 B.1. Checking that a Polygon Upward Normal Points Up
1228 RFC 5491 [RFC5491] mandates that polygons be presented in anti-
1229 clockwise direction so that the upward normal is in an upward
1230 direction. Accidental reversal of points can invert this vector.
1231 This error can be hard to detect just by looking at the series of
1232 coordinates that form the polygon.
1234 Calculate the dot product of the upward normal of the polygon
1235 (Appendix B) and any vector that points away from the center of the
1236 Earth from the location of polygon. If this product is positive,
1237 then the polygon upward normal also points away from the center of
1238 the Earth.
1240 The inverse cosine of this value indicates the angle between the
1241 horizontal plane and the approximate plane of the polygon.
1243 A unit vector for the upward direction at any point can be found
1244 based on the latitude (lat) and longitude (lng) of the point, as
1245 follows:
1247 Up = [ cos(lat) * cos(lng) ; cos(lat) * sin(lng) ; sin(lat) ]
1249 For polygons that span less than half the globe, any point in the
1250 polygon - including the centroid - can be selected to generate an
1251 approximate up vector for comparison with the upward normal.
1253 Authors' Addresses
1255 Martin Thomson
1256 Andrew Corporation
1257 Andrew Building (39)
1258 Wollongong University Campus
1259 Northfields Avenue
1260 Wollongong, NSW 2522
1261 AU
1263 Email: martin.thomson@andrew.com
1265 James Winterbottom
1266 Andrew Corporation
1267 Andrew Building (39)
1268 Wollongong University Campus
1269 Northfields Avenue
1270 Wollongong, NSW 2522
1271 AU
1273 Email: james.winterbottom@andrew.com