GEOPRIV M. Thomson Internet-Draft J. Winterbottom Intended status: Informational Andrew Corporation Expires: May 31, 2010 November 27, 2009 Representation of Uncertainty and Confidence in PIDF-LO draft-thomson-geopriv-uncertainty-04 Abstract The key concepts of uncertainty and confidence as they pertain to location information are defined. Methods for the manipulation of location estimates that include uncertainty information are outlined. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on May 31, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Thomson & Winterbottom Expires May 31, 2010 [Page 1] Internet-Draft Uncertainty & Confidence November 2009 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Conventions and Terminology . . . . . . . . . . . . . . . 3 2. A General Definition of Uncertainty and Confidence . . . . . . 4 2.1. Uncertainty as a Probability Distribution . . . . . . . . 4 2.2. Deprecation of the Terms Precision and Resolution . . . . 6 2.3. Accuracy as a Qualitative Concept . . . . . . . . . . . . 7 3. Uncertainty in Location . . . . . . . . . . . . . . . . . . . 8 3.1. Representation of Uncertainty and Confidence in PIDF-LO . 8 3.2. Uncertainty and Confidence for Civic Addresses . . . . . . 9 3.3. DHCP Location Configuration Information and Uncertainty . 9 4. Manipulation of Uncertainty . . . . . . . . . . . . . . . . . 11 4.1. Reduction of a Location Estimate to a Point . . . . . . . 11 4.1.1. Centroid Calculation . . . . . . . . . . . . . . . . . 12 4.2. Conversion to Circle or Sphere . . . . . . . . . . . . . . 15 4.3. Three-Dimensional to Two-Dimensional Conversion . . . . . 16 4.4. Increasing and Decreasing Uncertainty and Confidence . . . 17 4.4.1. Rectangular Distributions . . . . . . . . . . . . . . 17 4.4.2. Normal Distributions . . . . . . . . . . . . . . . . . 18 4.5. Determining Whether a Location is Within a Given Region . 18 4.5.1. Determining the Area of Overlap for Two Circles . . . 20 4.5.2. Determining the Area of Overlap for Two Polygons . . . 20 4.6. Obscuring Location Estimates for Privacy Reasons . . . . . 22 4.6.1. Repeated Requests and Obscured Location Information . 23 5. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.1. Reduction to a Point or Circle . . . . . . . . . . . . . . 25 5.2. Increasing and Decreasing Confidence . . . . . . . . . . . 28 5.3. Matching Location Estimates to Regions of Interest . . . . 28 5.4. Obfuscating Location Estimates . . . . . . . . . . . . . . 29 6. Security Considerations . . . . . . . . . . . . . . . . . . . 30 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31 8. Informative References . . . . . . . . . . . . . . . . . . . . 32 Appendix A. Conversion Between Cartesian and Geodetic Coordinates in WGS84 . . . . . . . . . . . . . . . . 34 Appendix B. Calculating the Upward Normal of a Polygon . . . . . 36 B.1. Checking that a Polygon Upward Normal Points Up . . . . . 36 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 38 Thomson & Winterbottom Expires May 31, 2010 [Page 2] Internet-Draft Uncertainty & Confidence November 2009 1. Introduction Location information represents an estimation of the position of a Target. Under ideal circumstances, a location estimate precisely reflects the actual location of the Target. In reality, there are many factors that introduce errors into the measurements that are used to determine location estimates. The process by which measurements are combined to generate a location estimate is outside of the scope of work within the IETF. However, the results of such a process are carried in IETF data formats and protocols. This document outlines how uncertainty, and its associated datum, confidence, are expressed and interpreted. This document provides a common nomenclature for discussing uncertainty and confidence as they relate to location information. This document also provides guidance on how to manage location information that includes uncertainty. Methods for expanding or reducing uncertainty to obtain a required level of confidence are described. Methods for determining the probability that a Target is within a specified region based on their location estimate are described. These methods are simplified by making certain assumptions about the location estimate and are designed to be applicable to location estimates in a relatively small area. 1.1. Conventions and Terminology This document assumes a basic understanding of the principles of mathematics, particularly statistics and geometry. Some background in geographic information systems is also helpful. Some terminology is borrowed from [RFC3693] and [I-D.ietf-geopriv-arch]. Mathematical formulae are presented using the following notation: add "+", subtract "-", multiply "*", divide "/", power "^" and absolute value "|x|". Precedence is indicated using parentheses. Mathematical functions are represented by common abbreviations: square root "sqrt(x)", sine "sin(x)", cosine "cos(x)", inverse cosine "acos(x)", tangent "tan(x)", inverse tangent "atan(x)", error function "erf(x)", and inverse error function "erfinv(x)". Thomson & Winterbottom Expires May 31, 2010 [Page 3] Internet-Draft Uncertainty & Confidence November 2009 2. A General Definition of Uncertainty and Confidence Uncertainty is a product of the limitations of measurement. In measuring any observable quantity, errors from a range of sources affect the result. Uncertainty is a quantification of that error. When quantifying the impact of measurement errors, two or more values are used. This document limits this to two values: uncertainty and confidence. Uncertainty expresses the magnitude of the possible error. Uncertainty is most often expressed as a range in the same units as the result. Confidence is an estimate of the probability that the "true" value lies within the extents defined by the uncertainty. In the following example, a measurement result is shown as a nominal value plus information on uncertainty (+/- 0.0043 meters) and confidence (95%). e.g. x = 1.00742 +/- 0.0043 meters at 95% confidence This result indicates that the measurement indicates that the value of "x" between 1.00312 and 1.01172 meters with 95% probability. Uncertainty in this context is what is sometimes referred to as a confidence interval. Uncertainty and confidence for location estimates can be derived in a number of ways. This document does not attempt to enumerate the many methods for determining uncertainty. [ISO.GUM] and [NIST.TN1297] provide a set of general guidelines for determining and manipulating measurement uncertainty. This document applies that general guidance for consumers of location information. 2.1. Uncertainty as a Probability Distribution It is helpful to think of the uncertainty and confidence as defining a probability density function (PDF). The probability density indicates the probability that the true value lies at any one point. The shape of the probability distribution depends on the method that is used to determine the result. The two probability density functions most generally applicable most applicable to location information are considered in this document: o The normal PDF (also referred to as a Gaussian PDF) is used where a large number of small random factors contribute to errors. The value used for uncertainty in a normal PDF is related to the standard deviation of the distribution. Thomson & Winterbottom Expires May 31, 2010 [Page 4] Internet-Draft Uncertainty & Confidence November 2009 o A rectangular PDF is used where the errors are known to be consistent across a limited range. A rectangular PDF can occur where a single error source, such as a rounding error, is significantly larger than other errors. The value used for uncertainty where a rectangular PDF is known is the half-width of the distribution; that is, half the width of the distribution. Each of these probability density functions can be characterized by its center point, or mean, and its width. For a normal distribution, uncertainty and confidence together are related to the standard deviation (see Section 4.4). For a rectangular distribution, half of the width of the distribution is used. Figure 1 shows a normal and rectangular probability density function with the mean (m) and standard deviation (s) labelled. The half- width (h) of the rectangular distribution is also indicated. ***** *** Normal PDF ** : ** --- Rectangular PDF ** : ** ** : ** .---------*---------------*---------. | ** : ** | | ** : ** | | * <-- s -->: * | | * : : : * | | ** : ** | | * : : : * | | * : * | |** : : : **| ** : ** *** | : : : | *** ***** | :<------ h ------>| ***** .****-------+.......:.........:.........:.......+-------*****. m Figure 1: Normal and Rectangular Probability Density Functions In relation to a PDF, uncertainty represents a certain range of values and confidence is the probability that the "true" value is found within that range. Confidence is defined as the integral of the PDF over the range represented by the uncertainty. The probability of the "true" value falling between two points is found by finding the area under the curve between the points (that is, the integral of the curve between the points). For any given PDF, the area under the curve for the entire range from negative infinity to positive infinity is 1 or (100%). Therefore, the Thomson & Winterbottom Expires May 31, 2010 [Page 5] Internet-Draft Uncertainty & Confidence November 2009 confidence over any interval of uncertainty is always less than 100%. Figure 2 shows how confidence is determined for a normal distribution. The area of the shaded region gives the confidence (c) for the interval between "m-u" and "m+u". ***** **:::::** **:::::::::** **:::::::::::** *:::::::::::::::* **:::::::::::::::** **:::::::::::::::::** *:::::::::::::::::::::* *:::::::::::::::::::::::* **:::::::::::::::::::::::** *:::::::::::: c ::::::::::::* *:::::::::::::::::::::::::::::* **|:::::::::::::::::::::::::::::|** ** |:::::::::::::::::::::::::::::| ** *** |:::::::::::::::::::::::::::::| *** ***** |:::::::::::::::::::::::::::::| ***** .****..........!:::::::::::::::::::::::::::::!..........*****. | | | (m-u) m (m+u) Figure 2: Confidence as the Integral of a PDF When expressing uncertainty, the value for uncertainty is the range of values and confidence is the probability that the true value is found within that range. In Section 4.4, methods are described for manipulating uncertainty and confidence if the shape of the PDF is known. 2.2. Deprecation of the Terms Precision and Resolution The terms _Precision_ and _Resolution_ are defined in RFC 3693 [RFC3693]. These definitions were intended to provide a common nomenclature for discussing uncertainty; however, these particular terms have many different uses in other fields and their definitions are not sufficient to avoid confusion about their meaning. These terms are unsuitable for use in relation to quantitative concepts when discussing uncertainty and confidence in relation to location information. Thomson & Winterbottom Expires May 31, 2010 [Page 6] Internet-Draft Uncertainty & Confidence November 2009 2.3. Accuracy as a Qualitative Concept Uncertainty and confidence are quantitative concepts. The term _Accuracy_ is useful in describing, qualitatively, the general concepts of location information. Accuracy is generally useful when describing qualitative aspects of location estimates. Accuracy is not a suitable term for use in a quantitative context. For instance, it could be appropriate to say that a location estimate with uncertainty "X" is more accurate than a location estimate with uncertainty "2X" at the same confidence. It is not appropriate to assign a number to "accuracy", nor is it appropriate to refer to any component of uncertainty or confidence as "accuracy". That is, to say that the "accuracy" for the first location estimate is "X" would be an erroneous use of this term. Thomson & Winterbottom Expires May 31, 2010 [Page 7] Internet-Draft Uncertainty & Confidence November 2009 3. Uncertainty in Location A _location estimate_ is the result of location determination. A location estimate is subject to uncertainty like any other observation. However, unlike a simple measure of a one dimensional property like length, a location estimate is specified in two or three dimensions. Uncertainty in a single dimension is expressed as a range; that is, a length of uncertainty in one dimension. Locations in two or three dimensional space are expressed as a subset of that space, either an area or volume of uncertainty. In simple terms, areas or volumes can be formed by the combination of two or three ranges, or more complex shapes could be described. This document uses the term _region of uncertainty_ to refer to the uncertainty of a location estimate expressed either as an area or volume. 3.1. Representation of Uncertainty and Confidence in PIDF-LO A set of shapes suitable for the expression of uncertainty in location estimates in the presence information data format - location object (PIDF-LO) are described in [GeoShape]. These shapes are the recommended form for the representation of uncertainty in PIDF-LO [RFC4119] documents. The PIDF-LO does not include an indication of confidence, but that confidence is 95%, by definition in [RFC5491]. Similarly, the PIDF-LO format does not provide an indication of the shape of the PDF. Absence of uncertainty information in a PIDF-LO document does not indicate that there is no uncertainty in the location estimate. Uncertainty might not have been calculated for the estimate, or it may be withheld for privacy purposes. If the Point shape is used, confidence and uncertainty are unknown; a receiver can either assume a confidence of 0% or infinite uncertainty. The same principle applies on the altitude axis for two-dimension shapes like the Circle. In order to support the functions provided in this document, location information needs to be generated with symmetrical probability distributions in each dimension. See Section 4.4 for more details. Thomson & Winterbottom Expires May 31, 2010 [Page 8] Internet-Draft Uncertainty & Confidence November 2009 3.2. Uncertainty and Confidence for Civic Addresses Civic addresses [RFC5139] inherently include uncertainty, based on the area of the most precise element that is specified. Uncertainty is effectively defined by the presence or absence of elements -- elements that are not present are deemed to be uncertain. To apply the concept of uncertainty to civic addresses, it is helpful to unify the conceptual models of civic address with geodetic location information. Note: This view is one perspective on the process of geo-coding - the translation of a civic address to a geodetic location. In the unified view, a civic address defines a series of (sometimes non-orthogonal) spatial partitions. The first is the implicit partition that identifies the surface of the earth and the space near the surface. The second is the country. Each label that is included in a civic address provides information about a different set of spatial partitions. Some partions require slight adjustments from a standard interpretation: for instance, a road includes all properties that adjoin the street. Each label might need to be interpreted with other values to provide context. As a value at each level is interpreted, one or more spatial partitions at that level are selected, and all other partitions of that type are excluded. For non-orthogonal partitions, only the portion of the partition that fits within the existing space is selected. This is what distinguishes King Street in Sydney from King Street in Melbourne. Each defined element selects a partition of space. The resulting location is the intersection of all selected spaces. The resulting spatial partition can be considered to represent a region of uncertainty. At no stage does this process select a point; although, as spaces get smaller this distinction might have no practical significance and an approximation if a point could be used. Uncertainty in civic addresses can be increased by removing elements. This doesn't necessarily improve confidence in the same way that arbitrarily increasing uncertainty in a geodetic location doesn't increase confidence. 3.3. DHCP Location Configuration Information and Uncertainty Location information is often measured in two or three dimensions; expressions of uncertainty in one dimension only are rare. The "resolution" parameters in [RFC3825] provide an indication of Thomson & Winterbottom Expires May 31, 2010 [Page 9] Internet-Draft Uncertainty & Confidence November 2009 uncertainty in one dimension. [RFC3825] defines a means for representing uncertainty, but a value for confidence is not specified. A default value of 95% confidence can be assumed for the combination of the uncertainty on each axis. That is, the confidence of the resultant rectangular polygon or prism is 95%. Thomson & Winterbottom Expires May 31, 2010 [Page 10] Internet-Draft Uncertainty & Confidence November 2009 4. Manipulation of Uncertainty This section deals with manipulation of location information that contains uncertainty. The following rules generally apply when manipulating location information: o Where calculations are performed on coordinate information, these should be performed in Cartesian space and the results converted back to latitude, longitude and altitude. A method for converting to and from Cartesian coordinates is included in Appendix A. While some approximation methods are useful in simplifying calculations, treating latitude and longitude as Cartesian axes is never advisable. The two axes are not orthogonal. Errors can arise from the curvature of the earth and from the convergence of longitude lines. o Normal rounding rules do not apply when rounding uncertainty. When rounding, uncertainty is always rounded up and confidence is always rounded down (see [NIST.TN1297]). This means that any manipulation of uncertainty is a non-reversible operation; each manipulation can result in the loss of some information. 4.1. Reduction of a Location Estimate to a Point Manipulating location estimates that include uncertainty information requires additional complexity in systems. In some cases, systems only operate on definitive values, that is, a single point. This section describes algorithms for reducing location estimates to a simple form without uncertainty information. Having a consistent means for reducing location estimates allows for interaction between applications that are able to use uncertainty information and those that cannot. Note: Reduction of a location estimate to a point constitutes a reduction in information. Removing uncertainty information can degrade results in some applications. Also, there is a natural tendency to misinterpret a point location as representing a location without uncertainty. This could lead to more serious errors. Therefore, these algorithms should only be applied where necessary. Several different approaches can be taken when reducing a location estimate to a point. Different methods each make a set of assumptions about the properties of the PDF and the selected point; Thomson & Winterbottom Expires May 31, 2010 [Page 11] Internet-Draft Uncertainty & Confidence November 2009 no one method is more "correct" than any other. For any given region of uncertainty, selecting an arbitrary point within the area could be considered valid; however, given the aforementioned problems with point locations, a more rigorous approach is appropriate. Given a result with a known distribution, selecting the point within the area that has the highest probability is a more rigorous method. Alternatively, a point could be selected that minimizes the overall error; that is, it minimises the expected value of the difference between the selected point and the "true" value. If a rectangular distribution is assumed, the centroid of the area or volume minimizes the overall error. Minimizing the error for a normal distribution is mathematically complex. Therefore, this document opts to select the centroid of the region of uncertainty when selecting a point. 4.1.1. Centroid Calculation For regular shapes, such as Circle, Sphere, Ellipse and Ellipsoid, this approach equates to the center point of the region. For regions of uncertainty that are expressed as regular Polygons and Prisms the center point is also the most appropriate selection. For the Arc-Band shape and non-regular Polygons and Prisms, selecting the centroid of the area or volume minimizes the overall error. This assumes that the PDF is rectangular. Note: The centroid of a Polygon or Arc-Band shape is not necessarily within the region of uncertainty. 4.1.1.1. Arc-Band Centroid The centroid of the Arc-Band shape is found along a line that bisects the arc. The centroid can be found at the following distance from the starting point of the arc-band (assuming an arc-band with an inner radius of "r", outer radius "R", start angle "a", and opening angle "o"): d = 4 * sin(o/2) * (R*R + R*r + r*r) / (3*o*(R + r)) This point can be found along the line that bisects the arc; that is, the line at an angle of "a + (o/2)". Negative values are possible if the angle of opening is greater than 180 degrees; negative values indicate that the centroid is found along the angle "a + (o/2) + 180". Thomson & Winterbottom Expires May 31, 2010 [Page 12] Internet-Draft Uncertainty & Confidence November 2009 4.1.1.2. Polygon Centroid Calculating a centroid for the Polygon and Prism shapes is more complex. Polygons that are specified using geodetic coordinates are not necessarily coplanar. For Polygons that are specified without an altitude, choose a value for altitude before attempting this process; an altitude of 0 is acceptable. The method described in this section is simplified by assuming that the surface of the earth is locally flat. This method degrades as polygons become larger; see [GeoShape] for recommendations on polygon size. The polygon is translated to a new coordinate system that has an x-y plane roughly parallel to the polygon. This enables the elimination of z-axis values and calculating a centroid can be done using only x and y coordinates. This requires that the upward normal for the polygon is known. To translate the polygon coordinates, apply the process described in Appendix B to find the normal vector "N = [Nx,Ny,Nz]". This value should be made a unit vector to ensure that the transformation matrix is a special orthogonal matrix. From this vector, select two vectors that are perpendicular to this vector and combine these into a transformation matrix. If "Nx" and "Ny" are non-zero, the matrices in Figure 3 can be used, given "p = sqrt(Nx^2 + Ny^2)". More transformations are provided later in this section for cases where "Nx" or "Ny" are zero. [ -Ny/p Nx/p 0 ] [ -Ny/p -Nx*Nz/p Nx ] T = [ -Nx*Nz/p -Ny*Nz/p p ] T' = [ Nx/p -Ny*Nz/p Ny ] [ Nx Ny Nz ] [ 0 p Nz ] (Transform) (Reverse Transform) Figure 3: Recommended Transformation Matrices To apply a transform to each point in the polygon, form a matrix from the ECEF coordinates and use matrix multiplication to determine the translated coordinates. Thomson & Winterbottom Expires May 31, 2010 [Page 13] Internet-Draft Uncertainty & Confidence November 2009 [ -Ny/p Nx/p 0 ] [ x[1] x[2] x[3] ... x[n] ] [ -Nx*Nz/p -Ny*Nz/p p ] * [ y[1] y[2] y[3] ... y[n] ] [ Nx Ny Nz ] [ z[1] z[2] z[3] ... z[n] ] [ x'[1] x'[2] x'[3] ... x'[n] ] = [ y'[1] y'[2] y'[3] ... y'[n] ] [ z'[1] z'[2] z'[3] ... z'[n] ] Figure 4: Transformation Alternatively, direct multiplication can be used to achieve the same result: x'[i] = -Ny * x[i] / p + Nx * y[i] / p y'[i] = -Nx * Nz * x[i] / p - Ny * Nz * y[i] / p + p * z[i] z'[i] = Nx * x[i] + Ny * y[i] + Nz * z[i] The first and second rows of this matrix ("x'" and "y'") contain the values that are used to calculate the centroid of the polygon. To find the centroid of this polygon, first find the area using: A = sum from i=1..n of (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / 2 For these formulae, treat each set of coordinates as circular, that is "x'[0] == x'[n]" and "x'[n+1] == x'[1]". Based on the area, the centroid along each axis can be determined by: Cx' = sum (x'[i]+x'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A) Cy' = sum (y'[i]+y'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A) Note: The formula for the area of a polygon will return a negative value if the polygon is specified in clockwise direction. This can be used to determine the orientation of the polygon. The third row contains a distance from a plane parallel to the polygon. If the polygon is coplanar, then the values for "z'" are identical; however, the constraints recommended in [RFC5491] mean that this is rarely the case. To determine "Cz'", average these values: Cz' = sum z'[i] / n Once the centroid is known in the transformed coordinates, these can be transformed back to the original coordinate system. The reverse transformation is shown in Figure 5. Thomson & Winterbottom Expires May 31, 2010 [Page 14] Internet-Draft Uncertainty & Confidence November 2009 [ -Ny/p -Nx*Nz/p Nx ] [ Cx' ] [ Cx ] [ Nx/p -Ny*Nz/p Ny ] * [ Cy' ] = [ Cy ] [ 0 p Nz ] [ sum of z'[i] / n ] [ Cz ] Figure 5: Reverse Transformation The reverse transformation can be applied directly as follows: Cx = -Ny * Cx' / p - Nx * Nz * Cy' / p + Nx * Cz' Cy = Nx * Cx' / p - Ny * Nz * Cy' / p + Ny * Cz' Cz = p * Cy' + Nz * Cz' The ECEF value "[Cx,Cy,Cz]" can then be converted back to geodetic coordinates. Given a polygon that is defined with no altitude or equal altitudes for each point, the altitude of the result can either be ignored or reset after converting back to a geodetic value. The centroid of the Prism shape is found by finding the centroid of the base polygon and raising the point by half the height of the prism. This can be added to altitude of the final result; alternatively, this can be added to "Cz'", which ensures that negative height is correctly applied to polygons that are defined in a "clockwise" direction. The recommended transforms only apply if "Nx" and "Ny" are non-zero. If the normal vector is "[0,0,1]" (that is, along the z-axis), then no transform is necessary. Similarly, if the normal vector is "[0,1,0]" or "[1,0,0]", avoid the transformation and use the x and z coordinates or y and z coordinates (respectively) in the centroid calculation phase. If either "Nx" or "Ny" are zero, the alternative transform matrices in Figure 6 can be used. The reverse transform is the transpose of this matrix. if Nx == 0: | if Ny == 0: [ 0 -Nz Ny ] [ 0 1 0 ] | [ -Nz 0 Nx ] T = [ 1 0 0 ] T' = [ -Nz 0 Ny ] | T = [ 0 1 0 ] = T' [ 0 Ny Nz ] [ Ny 0 Nz ] | [ Nx 0 Nz ] Figure 6: Alternative Transformation Matrices 4.2. Conversion to Circle or Sphere The Circle or Sphere are simple shapes that suit a range of applications. A circle or sphere contains fewer units of data to manipulate, which simplifies operations on location estimates. Thomson & Winterbottom Expires May 31, 2010 [Page 15] Internet-Draft Uncertainty & Confidence November 2009 The simplest method for converting a location estimate to a Circle or Sphere shape is to determine the centroid and then find the longest distance to any point in the region of uncertainty to that point. This distance can be determined based on the shape type: Circle/Sphere: No conversion necessary. Ellipse/Ellipsoid: The greater of either semi-major axis or altitude uncertainty. Polygon/Prism: The distance to the furthest vertex of the polygon (for a Prism, it is only necessary to check points on the base). Arc-Band: The furthest length from the centroid to the points where the inner and outer arc end. This distance can be calculated by finding the larger of the two following formulae: X = sqrt( d*d + R*R - 2*d*R*cos(o/2) ) x = sqrt( d*d + r*r - 2*d*r*cos(o/2) ) Once the Circle or Sphere shape is found, the associated confidence can be increased if the result is known to follow a normal distribution. However, this is a complicated process and provides limited benefit. In many cases it also violates the constraint that confidence in each dimension be the same. Confidence should be unchanged when performing this conversion. Two dimensional shapes are converted to a Circle; three dimensional shapes are converted to a Sphere. 4.3. Three-Dimensional to Two-Dimensional Conversion A three-dimensional shape can be easily converted to a two- dimensional shape by removing the altitude component. A sphere becomes a circle; a prism becomes a polygon; an ellipsoid becomes an ellipse. Each conversion is simple, requiring only the removal of those elements relating to altitude. The altitude is unspecified for a two-dimensional shape and therefore has unlimited uncertainty along the vertical axis. The confidence for the two-dimensional shape is thus higher than the three- dimensional shape. Assuming equal confidence on each axis, the confidence of the circle can be increased using the following approximate formula: C[2d] >= C[3d] ^ (2/3) Thomson & Winterbottom Expires May 31, 2010 [Page 16] Internet-Draft Uncertainty & Confidence November 2009 "C[2d]" is the confidence of the two-dimensional shape and "C[3d]" is the confidence of the three-dimensional shape. For example, a Sphere with a confidence of 95% can be simplified to a Circle of equal radius with confidence of 96.6%. 4.4. Increasing and Decreasing Uncertainty and Confidence The combination of uncertainty and confidence provide a great deal of information about the nature of the data that is being measured. If both uncertainty, confidence and PDF are known, certain information can be extrapolated. In particular, the uncertainty can be scaled to meet a certain confidence or the confidence for a particular region of uncertainty can be found. In general, confidence decreases as the region of uncertainty decreases in size and confidence increases as the region of uncertainty increases in size. However, this depends on the PDF. If the region of uncertainty is increased, confidence might increase as result, but only if the PDF is normal. If the region of uncertainty is increased during the process of obfuscation (see Section 4.6), then the confidence cannot be increased. If the region of uncertainty is reduced in size, then the confidence is decreased accordingly. If the PDF is not known, uncertainty and confidence cannot be modified. Uncertainty can be increased, but only if confidence is not increased. 4.4.1. Rectangular Distributions Uncertainty that follows a rectangular distribution can only be decreased in size. Since the PDF is constant over the region of uncertainty, the resulting confidence is determined by the following formula: Cr = Co * Ur / Uo Where "Uo" and "Ur" are the sizes of the original and reduced regions of uncertainty (either the area or the volume of the region); "Co" and "Cb" are the confidence values associated with each region. Information is lost by decreasing the region of uncertainty for a rectangular distribution. Once reduced in size, the uncertainty region cannot subsequently be increased in size. Thomson & Winterbottom Expires May 31, 2010 [Page 17] Internet-Draft Uncertainty & Confidence November 2009 4.4.2. Normal Distributions Uncertainty and confidence can be both increased and decreased for a normal distribution. However, the process is more complicated. For a normal distribution, uncertainty and confidence are related to the standard deviation of the function. The following function defines the relationship between standard deviation, uncertainty and confidence along a single axis: S[x] = U[x] / ( sqrt(2) * erfinv(C[x]) ) Where "S[x]" is the standard deviation, "U[x]" is the uncertainty and "C[x]" is the confidence along a single axis. "erfinv" is the inverse error function. Scaling a normal distribution in two dimensions requires several assumptions. Firstly, it is assumed that the distribution along each axis is independent. Secondly, the confidence for each axis is the same. Therefore, the confidence along each axis can be assumed to be: C[x] = Co ^ (1/n) Where "C[x]" is the confidence along a single axis and "Co" is the overall confidence and "n" is the number of dimensions in the uncertainty. Therefore, to find the uncertainty for each axis at a desired confidence, "Cd", apply the following formula: Ud[x] <= U[x] * (erfinv(Cd ^ (1/n)) / erfinv(Co ^ (1/n))) For regular shapes, this formula can be applied as a scaling factor in each dimension to reach a required confidence. 4.5. Determining Whether a Location is Within a Given Region A number of applications require that a judgement be made about whether a Target is within a given region of interest. Given a location estimate with uncertainty, this judgement can be difficult. A location estimate represents a probability distribution, and the true location of the Target cannot be definitively known. Therefore, the judgement relies on determining the probability that the Target is within the region. The probability that the Target is within a particular region is found by integrating the PDF over the region. For a normal Thomson & Winterbottom Expires May 31, 2010 [Page 18] Internet-Draft Uncertainty & Confidence November 2009 distribution, there are no analytical methods that can be used to determine the integral of the two or three dimensional PDF over an arbitrary region. The complexity of numerical methods is also too great to be useful in many applications; for example, finding the integral of the PDF in two or three dimensions across the overlap between the uncertainty region and the target region. If the PDF is unknown, no determination can be made. When judging whether a location is within a given region, uncertainties using these PDFs can be assumed to be rectangular. If this assumption is made, the confidence should be scaled to 95%, if possible. Note: The selection of confidence has a significant impact on the final result. Only use a different confidence if an uncertainty value for 95% confidence cannot be found. Given the assumption of a rectangular distribution, the probability that a Target is found within a given region is found by first finding the area (or volume) of overlap between the uncertainty region and the region of interest. This is multiplied by the confidence of the location estimate to determine the probability. Figure 7 shows an example of finding the area of overlap between the region of uncertainty and the region of interest. _.-""""-._ .' `. _ Region of / \ / Uncertainty ..+-"""--.. | .-' | :::::: `-. | ,' | :: Ao ::: `. | / \ :::::::::: \ / / `._ :::::: _.X | `-....-' | | | | | \ / `. .' \_ Region of `._ _.' Interest `--..___..--' Figure 7: Area of Overlap Between Two Circular Regions Once the area of overlap, "Ao", is known, the probability that the Target is within the region of interest, "Pi", is: Pi = Co * Ao / Au Given that the area of the region of uncertainty is "Au" and the confidence is "Co". Thomson & Winterbottom Expires May 31, 2010 [Page 19] Internet-Draft Uncertainty & Confidence November 2009 This probability is often input to a decision process that has a limited set of outcomes; therefore, a threshold value needs to be selected. Depending on the application, different threshold probabilities might be selected. In the absence of specific recommendations, this document suggests that the probability be greater than 50% before a decision is made. If the decision process selects between two or more regions, as is required by [RFC5222], then the region with the highest probability can be selected. 4.5.1. Determining the Area of Overlap for Two Circles Determining the area of overlap between two arbitrary shapes is a non-trivial process. Reducing areas to circles (see Section 4.2) enables the application of the following process. Given the radius of the first circle "r", the radius of the second circle "R" and the distance between their center points "d", the following set of formulas provide the area of overlap "Ao". o If the circles don't overlap, that is "d >= r+R", "Ao" is zero. o If one of the two circles is entirely within the other, that is "d <= |r-R|", the area of overlap is the area of the smaller circle. o Otherwise, if the circles partially overlap, that is "d < r+R" and "d > |r-R|", find "Ao" using: a = (r^2 - R^2 + d^2)/(2*d) Ao = r^2*acos(a/r) + R^2*acos((d - a)/R) - d*sqrt(r^2 - a^2) A value for "d" can be determined by converting the center points to Cartesian coordinates and applying the simple formula: d = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2) 4.5.2. Determining the Area of Overlap for Two Polygons A calculation of overlap based on polygons can give better results than the circle-based method. This method is applicable when the region of uncertainty or region of interest are specified as polygons. This calculation needs to be performed in two dimensions. Therefore, translate both polygons onto a plane, using the method described in Section 4.1.1.2. Use the same projection plane for both polygons. Use a transformation based on the normal vector of the region of Thomson & Winterbottom Expires May 31, 2010 [Page 20] Internet-Draft Uncertainty & Confidence November 2009 interest, rather than the region of uncertainty, if this distinction is possible. Points of intersection between each line segment of both polygons need to be found. In the example shown in Figure 8 the polygons A-B- C-D-E-F-G-A and U-V-W-X-Y-Z-U intersect at points 1 through 4. G------------F / | Z------4-----Y | | / | | | A-------1--B | | | / | | |/ E | 2 / | /| / | / X---W / | C |/ | \ 3 | \ /| | \ / | | D | U----------------V Figure 8: Polygon Intersection Example Intersection points are inserted in the node list of each polygon, taking care to maintain the anti-clockwise direction. For the previous example, the node list for the two original polygons become: A-1-B-2-C-D-3-E-F-G-4-A and U-V-3-W-X-2-1-Y-4-Z-U. The set of intersection polygons are found by following a simple algorithm as follows: 1. Start a new intersection polygon. Select any un-visited intersection point and go to that point on either polygon. 2. Mark the current point as having been visited and add the point to the current intersection polygon. 3. Move the the next point on the current polygon, following a counter-clockwise direction. 4. If the new point is already marked, complete the intersection polygon. If there are unmarked points, start this process at Step 1 for a new intersection polygon. Thomson & Winterbottom Expires May 31, 2010 [Page 21] Internet-Draft Uncertainty & Confidence November 2009 5. If the point is an intersection point, change to the other polygon and go to the same point. 6. Continue from step 2. Following this algorithm for the example in Figure 8, two intersections are found. Starting at point 1: 1-Y-4-A-1; starting at point 2: 2-C-D-3-W-X-2. The areas of the resultant set of intersection polygons are added to get the total area of intersection. 4.6. Obscuring Location Estimates for Privacy Reasons [RFC3693] and [RFC3694] describe operations on location information that obscure the real location of a Target to protect privacy. Some obfuscation methods operate on a single point and don't allow for the associated region of uncertainty. This section describes a method that extends single point methods, while the confidence is retained by increasing the size of the region of uncertainty. This method is compatible with the recommendations in [I-D.ietf-geopriv-policy]. To obscure a location estimate that contains uncertainty information the following procedure can be used: 1. The shape is transformed into a Circle or Sphere shape. This simplifies later steps, but by increasing uncertainty could equally be considered additional obfuscation. 2. If the radius of the new region of uncertainty is greater than or equal to the desired uncertainty, no further obscuring is required. 3. Any single point within the region of uncertainty is chosen. For simplicity, this could be the centroid. 4. The selected point is moved randomly. This can be achieved by selecting a random direction and distance. To ensure that the random displacement is distributed evenly in a two-dimensional space, the distance can be selected using (where "rand()" is a function that produces a uniformly distributed random number between 0 and 1): Drandom = Dmax * (1 - | rand() + rand() - 1 |) For this to conform to the method in [I-D.ietf-geopriv-policy], this move can be no more than the desired uncertainty radius, Thomson & Winterbottom Expires May 31, 2010 [Page 22] Internet-Draft Uncertainty & Confidence November 2009 less the radius of the transformed shape. If the existing uncertainty is already greater than the desired uncertainty, no movement is necessary. 5. Based on the movement of the point, the entire region of uncertainty is moved in the same direction and by the same distance. For a circle, this is as simple as moving the center point. 6. The region of uncertainty is expanded by the maximum distance that the point could have moved (not the actual distance moved). The radius of the resulting shape is set to the desired uncertainty. This process ensures that no information about the original region of uncertainty is revealed but the confidence for the final estimate is the same as the original. [I-D.ietf-geopriv-policy] further indicates that any shape that entirely encloses the resulting area can be returned. This method is functionally equivalent to the method described for obscuring civic address by removing the most specific elements. Both increase uncertainty, albeit in different ways. 4.6.1. Repeated Requests and Obscured Location Information The method described in [I-D.ietf-geopriv-policy] suggests that the random numbers be based on a fixed seed. To avoid the need for maintained state, the seed can be reproduced based on a hash of some value specific to a Target, such as a URI or IP address. Using a fixed offset ensures that repeated requests do not reveal any additional information as the intersection of the results could quickly reveal the original region of uncertainty. However, for a mobile device, it is possible that a fixed offset could be learned by a location recipient. For instance, movement along a thoroughfare with a distinctive shape could result in a similar pattern emerging in the obscured location information. To prevent recipients from learning this offset in this manner, the fixed offset cannot be relied upon. The movement pattern needs to be obscured in some manner. The most effective method for masking the details of movement involve removing the effect of movement in the results. Reducing the rate at which location information is provided - or can be requested - ensures that movement is not directly mirrored in the Thomson & Winterbottom Expires May 31, 2010 [Page 23] Internet-Draft Uncertainty & Confidence November 2009 obscured results. New location information can be withheld from a recipient unless the estimated location moves some proportion of the desired minimum uncertainty distance. This could be implemented by checking if the centroid of the new location information fits within the uncertainty region already provided, if it does, the new information is suppressed. A fixed offset, or one that also uses the location information as input, can be used with this approach. Any fixed offset needs to be hard to guess for this to work. For instance, a hash of a value that is not known to recipients might be used (for instance, the unmodified location information). The drawback of this approach is that it requires that the information that was last provided to a recipient is retained; the approach cannot be implemented without some state being maintained. Given that many systems already rely on the existence of this information, this might be a reasonable method. Thomson & Winterbottom Expires May 31, 2010 [Page 24] Internet-Draft Uncertainty & Confidence November 2009 5. Examples This section presents some examples of how to apply the methods described in Section 4. 5.1. Reduction to a Point or Circle Alice receives a location estimate from her LIS that contains a ellipsoidal region of uncertainty. This information is provided at 19% confidence with a normal PDF. A PIDF-LO extract for this information is shown in Figure 9. -34.407242 150.882518 34 7.7156 3.31 28.7 43 Figure 9 This information can be reduced to a point simply by extracting the center point, that is [-34.407242, 150.882518, 34]. If some limited uncertainty were required, the estimate could be converted into a circle or sphere. To convert to a sphere, the radius is the largest of the semi-major, semi-minor and vertical axes; in this case, 28.7 meters. However, if only a circle is required, the altitude can be dropped as can the altitude uncertainty (the vertical axis of the ellipsoid), resulting in a circle at [-34.407242, 150.882518] of radius 7.7156 meters. Thomson & Winterbottom Expires May 31, 2010 [Page 25] Internet-Draft Uncertainty & Confidence November 2009 Bob receives a location estimate with a Polygon shape. This information is shown in Figure 10. -33.856625 151.215906 -33.856299 151.215343 -33.856326 151.214731 -33.857533 151.214495 -33.857720 151.214613 -33.857369 151.215375 -33.856625 151.215906 Figure 10 To convert this to a polygon, each point is firstly assigned an altitude of zero and converted to ECEF coordinates (see Appendix A). Then a normal vector for this polygon is found (see Appendix B). The results of each of these stages is shown in Figure 11. Note that the numbers shown are all rounded; no rounding is possible during this process since rounding would contribute significant errors. Thomson & Winterbottom Expires May 31, 2010 [Page 26] Internet-Draft Uncertainty & Confidence November 2009 Polygon in ECEF coordinate space (repeated point omitted and transposed to fit): [ -4.6470e+06 2.5530e+06 -3.5333e+06 ] [ -4.6470e+06 2.5531e+06 -3.5332e+06 ] pecef = [ -4.6470e+06 2.5531e+06 -3.5332e+06 ] [ -4.6469e+06 2.5531e+06 -3.5333e+06 ] [ -4.6469e+06 2.5531e+06 -3.5334e+06 ] [ -4.6469e+06 2.5531e+06 -3.5333e+06 ] Normal Vector: n = [ -0.72782 0.39987 -0.55712 ] Transformation Matrix: [ -0.48152 -0.87643 0.00000 ] t = [ -0.48828 0.26827 0.83043 ] [ -0.72782 0.39987 -0.55712 ] Transformed Coordinates: [ 8.3206e+01 1.9809e+04 6.3715e+06 ] [ 3.1107e+01 1.9845e+04 6.3715e+06 ] pecef' = [ -2.5528e+01 1.9842e+04 6.3715e+06 ] [ -4.7367e+01 1.9708e+04 6.3715e+06 ] [ -3.6447e+01 1.9687e+04 6.3715e+06 ] [ 3.4068e+01 1.9726e+04 6.3715e+06 ] Two dimensional polygon area: A = 12600 m^2 Two-dimensional polygon centroid: C' = [ 8.8184e+00 1.9775e+04 ] Average of pecef' z coordinates: 6.3715e+06 Reverse Transformation Matrix: [ -0.48152 -0.48828 -0.72782 ] t' = [ -0.87643 0.26827 0.39987 ] [ 0.00000 0.83043 -0.55712 ] Polygon centroid (ECEF): C = [ -4.6470e+06 2.5531e+06 -3.5333e+06 ] Polygon centroid (Geo): Cg = [ -33.856926 151.215102 -4.9537e-04 ] Figure 11 The point conversion for the polygon uses the final result, "Cg", ignoring the altitude since the original shape did not include altitude. To convert this to a circle, take the maximum distance in ECEF coordinates from the center point to each of the points. This results in a radius of 99.1 meters. Confidence is unchanged. Thomson & Winterbottom Expires May 31, 2010 [Page 27] Internet-Draft Uncertainty & Confidence November 2009 5.2. Increasing and Decreasing Confidence Assuming that confidence is known to be 19% for Alice's location information. This is typical value for a three-dimensional ellipsoid uncertainty of normal distribution where the standard deviation is supplied in each dimension. The confidence associated with Alice's location estimate is quite low for many applications. Since the estimate is known to follow a normal distribution, the method in Section 4.4.2 can be used. Each axis can be scaled by: scale = erfinv(0.95^(1/3)) / erfinv(0.19^(1/3)) = 2.9937 Ensuring that rounding always increases uncertainty, the location estimate at 95% includes a semi-major axis of 23.1, a semi-minor axis of 10 and a vertical axis of 86. Bob's location estimate covers an area of approximately 12600 square meters. If the estimate follows a rectangular distribution, the region of uncertainty can be reduced in size. To find the confidence that he is within the smaller area of the concert hall, given by the polygon [-33.856473, 151.215257; -33.856322, 151.214973; -33.856424, 151.21471; -33.857248, 151.214753; -33.857413, 151.214941; -33.857311, 151.215128]. To use this new region of uncertainty, find its area using the same translation method described in Section 4.1.1.2, which is 4566.2 square meters. The confidence associated with the smaller area is therefore 95% * 4566.2 / 12600 = 34%. 5.3. Matching Location Estimates to Regions of Interest Suppose than a circular area is defined centered at [-33.872754, 151.20683] with a radius of 1950 meters. To determine whether Bob is found within this area, we apply the method in Section 4.5. Using the converted Circle shape for Bob's location, the distance between these points is found to be 1915.26 meters. The area of overlap between Bob's location estimate and the region of interest is therefore 2209 square meters and the area of Bob's location estimate is 30853 square meters. This gives the probability that Bob is less than 1950 meters from the selected point as 67.8%. Note that if 1920 meters were chosen for the distance from the selected point, the area of overlap is only 16196 square meters and the confidence is 49.8%. Therefore, it is more likely that Bob is outside the region of interest, despite the center point of his location estimate being within the region. Thomson & Winterbottom Expires May 31, 2010 [Page 28] Internet-Draft Uncertainty & Confidence November 2009 5.4. Obfuscating Location Estimates Alices's Location Server (LS, see [I-D.ietf-geopriv-arch]) provides her location estimate to a Location Recipient (LR), but the ruleset (see [I-D.ietf-geopriv-policy]) that Alice has provided includes an geodetic transformation. The rule states that the location information is obscured by 1500 meters. To apply this rule, a single point is chosen. In this case the centroid, [-34.407242, 150.882518, 34], is used. The result of applying the transformation is the point [-34.41, 150.88, 34]. The maximum distance that this transform could shift a three dimensional point is 1471.3 meters. This is added to the original uncertainty, which becomes 1500 meters: the requested amount of obfuscation. The transformed location estimate is shown in Figure 12. -34.41 150.88 34 1500 Figure 12 Thomson & Winterbottom Expires May 31, 2010 [Page 29] Internet-Draft Uncertainty & Confidence November 2009 6. Security Considerations This document describes methods for managing and manipulating uncertainty in location. No specific security concerns arise from most of the information provided. The algorithm described for obscuring location information is intended as a tool in protecting privacy. Special care should be taken to ensure that repeated requests for obscured location information do not reveal more information than intended. The recommendation that the random component be stored or generated from static information ensures that this cannot occur. Thomson & Winterbottom Expires May 31, 2010 [Page 30] Internet-Draft Uncertainty & Confidence November 2009 7. Acknowledgements Thanks go to Peter Rhodes for his assistance with some of the mathematical groundwork on this document. Thomson & Winterbottom Expires May 31, 2010 [Page 31] Internet-Draft Uncertainty & Confidence November 2009 8. Informative References [I-D.ietf-geopriv-policy] Schulzrinne, H., Tschofenig, H., Morris, J., Cuellar, J., and J. Polk, "Geolocation Policy: A Document Format for Expressing Privacy Preferences for Location Information", draft-ietf-geopriv-policy-21 (work in progress), July 2009. [WGS84] US National Imagery and Mapping Agency, "Department of Defense (DoD) World Geodetic System 1984 (WGS 84), Third Edition", NIMA TR8350.2, January 2000. [GeoShape] Thomson, M. and C. Reed, "GML 3.1.1 PIDF-LO Shape Application Schema for use by the Internet Engineering Task Force (IETF)", Candidate OpenGIS Implementation Specification 06-142r1, Version: 1.0, April 2007. [RFC3693] Cuellar, J., Morris, J., Mulligan, D., Peterson, J., and J. Polk, "Geopriv Requirements", RFC 3693, February 2004. [RFC3694] Danley, M., Mulligan, D., Morris, J., and J. Peterson, "Threat Analysis of the Geopriv Protocol", RFC 3694, February 2004. [RFC4119] Peterson, J., "A Presence-based GEOPRIV Location Object Format", RFC 4119, December 2005. [RFC3825] Polk, J., Schnizlein, J., and M. Linsner, "Dynamic Host Configuration Protocol Option for Coordinate-based Location Configuration Information", RFC 3825, July 2004. [RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, January 2004. [RFC5139] Thomson, M. and J. Winterbottom, "Revised Civic Location Format for Presence Information Data Format Location Object (PIDF-LO)", RFC 5139, February 2008. [RFC5222] Hardie, T., Newton, A., Schulzrinne, H., and H. Tschofenig, "LoST: A Location-to-Service Translation Protocol", RFC 5222, August 2008. [RFC5491] Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV Presence Information Data Format Location Object (PIDF-LO) Usage Clarification, Considerations, and Recommendations", RFC 5491, March 2009. Thomson & Winterbottom Expires May 31, 2010 [Page 32] Internet-Draft Uncertainty & Confidence November 2009 [I-D.ietf-geopriv-arch] Barnes, R., Lepinski, M., Cooper, A., Morris, J., Tschofenig, H., and H. Schulzrinne, "An Architecture for Location and Location Privacy in Internet Applications", draft-ietf-geopriv-arch-01 (work in progress), October 2009. [ISO.GUM] ISO/IEC, "Guide to the expression of uncertainty in measurement (GUM)", Guide 98:1995, 1995. [NIST.TN1297] Taylor, B. and C. Kuyatt, "Guidelines for Evaluating and Expressing the Uncertainty of NIST Measurement Results", Technical Note 1297, Sep 1994. [Convert] Burtch, R., "A Comparison of Methods Used in Rectangular to Geodetic Coordinate Transformations", April 2006. [Sunday02] Sunday, D., "Fast polygon area and Newell normal computation.", Journal of Graphics Tools JGT, 7(2):9- 13,2002, 2002, . Thomson & Winterbottom Expires May 31, 2010 [Page 33] Internet-Draft Uncertainty & Confidence November 2009 Appendix A. Conversion Between Cartesian and Geodetic Coordinates in WGS84 The process of conversion from geodetic (latitude, longitude and altitude) to earth-centered, earth-fixed (ECEF) Cartesian coordinates is relatively simple. In this section, the following constants and derived values are used from the definition of WGS84 [WGS84]: {radius of ellipsoid} R = 6378137 meters {inverse flattening} 1/f = 298.257223563 {first eccentricity squared} e^2 = f * (2 - f) {second eccentricity squared} e'^2 = e^2 * (1 - e^2) To convert geodetic coordinates (latitude, longitude, altitude) to ECEF coordinates (X, Y, Z), use the following relationships: N = R / sqrt(1 - e^2 * sin(latitude)^2) X = (N + altitude) * cos(latitude) * cos(longitude) Y = (N + altitude) * cos(latitude) * sin(longitude) Z = (N*(1 - e^2) + altitude) * sin(latitude) The reverse conversion requires more complex computation and most methods introduce some error in latitude and altitude. A range of techniques are described in [Convert]. A variant on the method originally proposed by Bowring, which results in an acceptably small error, is described by the following: p = sqrt(X^2 + Y^2) r = sqrt(X^2 + Y^2 + Z^2) u = atan((1-f) * Z * (1 + e'^2 * (1-f) * R / r) / p) latitude = atan((Z + e'^2 * (1-f) * R * sin(u)^3) / (p - e^2 * R * cos(u)^3)) longitude = atan(Y / X) altitude = sqrt((p - R * cos(u))^2 + (Z - (1-f) * R * sin(u))^2) Thomson & Winterbottom Expires May 31, 2010 [Page 34] Internet-Draft Uncertainty & Confidence November 2009 If the point is near the poles, that is "p < 1", the value for altitude that this method produces is unstable. A simpler method for determining the altitude of a point near the poles is: altitude = |Z| - R * (1 - f) Thomson & Winterbottom Expires May 31, 2010 [Page 35] Internet-Draft Uncertainty & Confidence November 2009 Appendix B. Calculating the Upward Normal of a Polygon For a polygon that is guaranteed to be convex and coplanar, the upward normal can be found by finding the vector cross product of adjacent edges. For more general cases the Newell method of approximation described in [Sunday02] may be applied. In particular, this method can be used if the points are only approximately coplanar, and for non-convex polygons. This process requires a Cartesian coordinate system. Therefore, convert the geodetic coordinates of the polygon to Cartesian, ECEF coordinates (Appendix A). If no altitude is specified, assume an altitude of zero. This method can be condensed to the following set of equations: Nx = sum from i=1..n of (y[i] * (z[i+1] - z[i-1])) Ny = sum from i=1..n of (z[i] * (x[i+1] - x[i-1])) Nz = sum from i=1..n of (x[i] * (y[i+1] - y[i-1])) For these formulae, the polygon is made of points "(x[1], y[1], z[1])" through "(x[n], y[n], x[n])". Each array is treated as circular, that is, "x[0] == x[n]" and "x[n+1] == x[1]". To translate this into a unit-vector; divide each component by the length of the vector: Nx' = Nx / sqrt(Nx^2 + Ny^2 + Nz^2) Ny' = Ny / sqrt(Nx^2 + Ny^2 + Nz^2) Nz' = Nz / sqrt(Nx^2 + Ny^2 + Nz^2) B.1. Checking that a Polygon Upward Normal Points Up RFC 5491 [RFC5491] mandates that polygons be presented in anti- clockwise direction so that the upward normal is in an upward direction. Accidental reversal of points can invert this vector. This error can be hard to detect just by looking at the series of coordinates that form the polygon. Calculate the dot product of the upward normal of the polygon (Appendix B) and any vector that points away from the center of the Earth from the location of polygon. If this product is positive, Thomson & Winterbottom Expires May 31, 2010 [Page 36] Internet-Draft Uncertainty & Confidence November 2009 then the polygon upward normal also points away from the center of the Earth. The inverse cosine of this value indicates the angle between the horizontal plane and the approximate plane of the polygon. A unit vector for the upward direction at any point can be found based on the latitude (lat) and longitude (lng) of the point, as follows: Up = [ cos(lat) * cos(lng) ; cos(lat) * sin(lng) ; sin(lat) ] For polygons that span less than half the globe, any point in the polygon - including the centroid - can be selected to generate the up vector. Thomson & Winterbottom Expires May 31, 2010 [Page 37] Internet-Draft Uncertainty & Confidence November 2009 Authors' Addresses Martin Thomson Andrew Corporation Andrew Building (39) Wollongong University Campus Northfields Avenue Wollongong, NSW 2522 AU Email: martin.thomson@andrew.com James Winterbottom Andrew Corporation Andrew Building (39) Wollongong University Campus Northfields Avenue Wollongong, NSW 2522 AU Email: james.winterbottom@andrew.com Thomson & Winterbottom Expires May 31, 2010 [Page 38]