Considerations about Interpolations

Role of interpolation

GML (in conformity with ISO:19107) establishes standards to specify the CRS of geographic points, in order to unambiguously identify their position on the Earth surface. Particular attention has to be paid to the definition and Earth location of extended geometric entities (curves and surfaces).

In GML, curve segments are defined by means of a set of control points and control parameters. They also have an enumerator attribute called "interpolation", specifying the mechanism used to determine the exact geographic extent of the curve, out of the control points and parameters. Its possible values include "linear" and "geodesic".

The notion of "linear" interpolation relies on the existence of a "vector" (or "linear") structure on the surface. We are used to take for granted that such a kind of structure exists. This is the case for a "flat" surface, isomorphic to , because is endowed with a natural linear structure. But this is not true in general, and in particular, it is not true for a curved surface, such as the Earth. So, in principle, it doesn't make sense to talk about linear segments on the Earth! Actually we can bypass this conceptual problem by slightly changing the definition of linear interpolation. This can be done by relying on the choice of a local CRS (a linear structure is locally implicitly defined by the coordinate system itself, namely by the local mapping of the surface on): a linear segment joining two given points, A and B, will be the locus of points whose coordinates belong to the convex linear combination the endpoint coordinates:

The drawback of this definition is that two different CRS on the same surface will give rise to two different "linear segments" (two different sets of points) joining the same couple of points.

Why geodesic is better

Things are a little bit different with the notion of "geodesic" interpolation. This is independent from the chosen CRS and just relies on the existence of a specific metric structure on the surface. So, contrary to linear ones, geodesic segments joining two given points on the Earth are well defined and independent from the choice of a projection (CRS). The same is true for any other kind of curve. For instance, a circumference (circular arc) of given center and radius, will have a fixed shape on any (projected) chart but will correspond to different curves on the Earth. On the contrary, a "geodesic arc" (the locus of points equidistant, with respect to the ellipsoidal metric, from a given center) will have a different shapes in different charts, corresponding to the same set of points on the Earth.

The geodesic interpolation is a better choice than the linear one, for at least two further reasons:

1. many curves in aeronautical applications (e.g. the footprint of a GPS driven aircraft) are actually geodesic in nature rather than linear
2. worldwide aeronautical data originators adopt many different CRSs (the most convenient one for their own location). When putting together data coming from different originators (hence different CRSs), it is by far computationally easier, for a GIS system, to deal with geodesic entities on a given ellipsoid (such as WGS 84) rather than dealing with linear objects coming from different CRSs

Practical considerations

The purpose of the GML aeronautical profile should be ensuring that the geometric content of AIXM messages is unambiguously interpreted by any aeronautical application. A good mathematical definition is necessary but it is by no means sufficient in order to unambiguously exchange geographic information. If the applications exchanging data are not able to correctly deal with its geometric content, the effort of defining a rigorous language is almost in vain.

One of the most critical issues is the accuracy with which geometric entities have to be stored and exchanged. The magnitude of the errors implicitly committed by erroneously interpreting the interpolation of an extended object may vary broadly, depending on many factors, such as the choice of CRS, the location of the object with respect to the CRS natural domain, the extension of the object itself, etc. In many cases they are (almost) negligible for aeronautical purposes. But it is not rare to run into big trouble which can be brought back to the inaccuracy of the underlying computation engines of the applications dealing with geographic data.

Hardly any GIS application, nowadays, is actually able to correctly deal with geodesic entities. Apart for a few specific tools, GIS usually treats geodesic objects as linear in many respects (for computation and visualization purposes). One of the most commonly used tricks to reduce approximation errors of extended objects is their "densification". Densification has its drawbacks, anyways:

• the original geometric data (the extended curve) is altered, with integrity loss;
• the subsampling introduces a given amount of arbitrariness and irreversibility (from the subsampled geometry it is not possible to recover the original data);
• the approximated representation implies some computational errors (consider, for instance the difference between a circular arc and a chord approximating the arc);
• different applications may require different accuracy levels and hence a different amount of "densification".

For all of these reasons, the GML aeronautical profile should look forward to the future and set down the foundations for a rigorous geographic information exchange among the next generation of aeronautical applications, leaving to each application the responsibility to manage the geometric content in the most proper way for its purposes.

Interpolation and Densification Considerations

Background

Within geospatial standards and technologies there are two classes of geometry models in common use:

1. Comprehensive models based on ISO 19107;
2. Simple models based on a subset of ISO 19107;

To date, there are numerous implementations of simple geometry models, namely:

• OGC Simple Feature Access: OGC's abstract model for simple geometry.
  • OGC Well Known Text (WKT)
  • OGC Simple Features SQL – Binary Geometry
  • OGC Simple Features - CORBA
• SQL MM (Multi-Media) : This provides an ISO model for database access to geometries which is similar to the OGC Simple Features for SQL.

The majority of mainstream 'off the shelf' database technologies which handle geographical data for storage and query are based on the simple feature model. For example:

In addition, most popular desktop GIS applications also implement a simple geometry model and are interoperable with these databases.

Comparison of models

The ISO19107/GML model contains a number of structures which do not occur in the simple models:

• Composite geometries
• Curve interpolations other than line and 3 point circular arc e.g. arc by centre point, geodesic, offset curve.
• Surface patches other than polygon.
• Composition of geometries by reference (GML allows xpointer references to member geometries within a composite or aggregate geometry).
• Simple geometry only allows circles as polygon boundaries, not as a curve type in their own right.

ISO/GML allows an unlimited level of nesting of geometry structure. For example a composite curve may have members which are composite curves. These curves may in turn contain multiple segments. The simple model only allows a maximum of 3 levels of nested structure e.g. a multicurve may contain compound curves; compound curves may contain primitive curves; compound curves may not contain other compound curves.

For practical management of spatial data it is therefore often necessary to convert geometry types only available within ISO19107/GML 3.2 geometries to 'simple' geometries in order to make use of the spatial storage, index and query functionality of mainstream technologies.

Mapping of GML to Simple Geometry

Flattening of geometry structure

Because of the limited amount of nesting allowed in simple geometry deeply nested structures in GML must be "flattened" to fit the simple model. This can be done by removing intermediate layers of structure. For example, a composite curve can be mapped to a compound curve containing primitive elements corresponding to each segment in each curve within the composite.

Densification of curves

The biggest obstacle to converting ISO/GML geometries to simple geometries is the limited number of curve interpolations in simple geometry models. Simple geometry allows for

• Straight lines interpolation between a series of control points.
• Arcs and circles defined by three control points on the edge of the curve.

ISO/GML allows for several additional interpolations. Since these have no direct equivalent in the simple geometry the ISO/GML geometries must be converted to an approximation of the original geometry which is made up of only the interpolation types in the simple model. All curve segment types which cannot be mapped directly to a simple curve should be converted to LineStrings since this is the most interoperable interpolation type.

The process of converting to LineString is one of "densification". In densification a set of control points are generated along the path of the curve. A LineString is created from the set of control points generated. The linestring is therefore an approximation of the shape of the original curve.

The accuracy of the approximation depends on how many additional control points are generated and their spacing. This can be controlled by parameters. ISO 19107 specified two parameters, either or both of which can be used to control densification. These are:

• Maximum distance between control points.
• Maximum offset i.e. the maximum distance between the densified curve and the original.

The maximum distance between control points allows for more efficient processing, so only this parameter should be used.

The size of the maximum distance between control points required will depend on circumstances. Clearly the level of accuracy required is the principle factor in selecting the parameter, but for practical purposes this must be balanced with the number of control points generated. For example, a trans-Atlantic flight path probably needs less precision than a runway boundary. Equally, setting a maximum control point distance of 10 meters would create an unmanageable number of points in the flight path, but not in the runway boundary.

* Arcs and circles are interpreted as being the set of points at an equal geodesic distance from the centre point on the ellipsoid. In non-geodetic coordinate systems this can result in shapes which are not circular in the projected coordinate system. More information on arc interpretation is provided in Annex A

** Some implementations of simple geometry are strict about arc interpolation and only allow circular arcs in projected planar coordinate systems. This is because, on an ellipsoid, points at an equal distance from a centre point do not form a circular arc.

Since both geometry models use a boundary value representation, the densification of curves can be applied to surface boundaries. No additional transformations are required for surface geometries.

Loss of data structure

The simple model contains less information than the ISO/GML model. ISO/GML geometries which have been mapped to simple geometry therefore cannot be reconstructed from their simple representation.

Where curves have been densified the original (and potentially more precise) representation is not preserved. The simplified geometry is therefore very useful for most practical purposes, but may not be sufficient close to the original for audit and accountability purposes, i.e. it is not exactly the same geometry which was supplied in the GML.