Triangulated Irregular Network based transformation

Added in version 7.2.0.

Alias

tinshift

Input type

Projected or geographic coordinates (horizontal), meters (vertical)

Output type

Projected or geographic coordinates (horizontal), meters (vertical)

Domain

2D or 3D

Available forms

Forward and inverse

The tinshift transformation takes one mandatory argument, file, that points to a JSON file, which contains the triangulation and associated metadata. Input and output coordinates must be geographic or projected coordinates. Depending on the content of the JSON file, horizontal, vertical or both components of the coordinates may be transformed.

The transformation is invertible, with the same computational complexity than the forward transformation.

Parameters

Required

+file=<filename>

Filename to the JSON file for the TIN.

Example

Transforming a point with the Finland EPSG:2393 ("KKJ / Finland Uniform Coordinate System") projected CRS to EPSG:3067 ("ETRS89 / TM35FIN(E,N)")

$ echo 3210000.0000 6700000.0000 0 2020 | cct +proj=tinshift +file=./triangulation_kkj.json

209948.3217     6697187.0009    0.0000     2020

Algorithm

Internally, tinshift ingest the whole file into memory. It is considered that triangulation should be small enough for that.

When a point is transformed, one must find the triangle into which it falls into. Instead of iterating over all triangles, we build a in-memory quadtree to speed-up the identification of candidates triangles.

To determine if a point falls into a triangle, one computes its 3 barycentric coordinates from its projected coordinates, \(\lambda_i\) for \(i=1,2,3\). They are real values (in the [0,1] range for a point inside the triangle), giving the weight of each of the 3 vertices of the triangles.

Once those weights are known, interpolating the target horizontal coordinate is a matter of doing the linear combination of those weights with the target horizontal coordinates at the 3 vertices of the triangle (\(Xt_i\) and \(Yt_i\)):

\[ \begin{align}\begin{aligned}X_{target} = Xt_1 * \lambda_1 + Xt_2 * \lambda_2 + Xt_3 * \lambda_3\\Y_{target} = Yt_1 * \lambda_1 + Yt_2 * \lambda_2 + Yt_3 * \lambda_3\end{aligned}\end{align} \]

This interpolation is exact at the vertices of the triangulation, and has linear properties inside each triangle. It is completely equivalent to other formulations of triangular interpolation, such as

\[ \begin{align}\begin{aligned}X_{target} = A + X_{source} * B + Y_{source} * C\\Y_{target} = D + X_{source} * E + Y_{source} * F\end{aligned}\end{align} \]

where the A, B, C, D, E, F constants (for a given triangle) are found by solving the 2 systems of 3 linear equations, constraint by the source and target coordinate pairs of the 3 vertices of the triangle:

\[ \begin{align}\begin{aligned}Xt_i = A + Xs_i * B + Ys_i * C\\Yt_i = D + Xs_i * E + Ys_i * F\end{aligned}\end{align} \]

Similarly for a vertical coordinate transformation, where \(Zoff_i\) is the vertical offset at each vertex of the triangle:

\[Z_{target} = Z_{source} + Zoff_1 * \lambda_1 + Zoff_2 * \lambda_2 + Zoff_3 * \lambda_3\]

Constraints on the triangulation

No check is done on the consistence of the triangulation. It is highly recommended that triangles do not overlap each other (when considering the source coordinates or the forward transformation, or the target coordinates for the inverse transformation), otherwise which triangle will be selected is unspecified. Besides that, the triangulation does not need to have particular properties (like being a Delaunay triangulation)

File format

The triangulation is stored in a text-based format, using JSON as a serialization.

Below a minimal example, from the KKJ to ETRS89 transformation, with just a single triangle:

{
  "file_type": "triangulation_file",
  "format_version": "1.0",
  "name": "Name",
  "version": "Version",
  "publication_date": "2018-07-01T00:00:00Z",
  "license": "Creative Commons Attribution 4.0 International",
  "description": "Test triangulation",
  "authority": {
    "name": "Authority name",
    "url": "http://example.com",
    "address": "Adress",
    "email": "test@example.com"
  },
  "links": [
    {
      "href": "https://example.com/about.html",
      "rel": "about",
      "type": "text/html",
      "title": "About"
    },
    {
      "href": "https://example.com/download",
      "rel": "source",
      "type": "application/zip",
      "title": "Authoritative source"
    },
    {
      "href": "https://creativecommons.org/licenses/by/4.0/",
      "rel": "license",
      "type": "text/html",
      "title": "Creative Commons Attribution 4.0 International license"
    },
    {
      "href": "https://example.com/metadata.xml",
      "rel": "metadata",
      "type": "application/xml",
      "title": " ISO 19115 XML encoded metadata regarding the deformation model"
    }
  ],
  "transformed_components": [ "horizontal" ],
  "vertices_columns": [ "source_x", "source_y", "target_x", "target_y" ],
  "triangles_columns": [ "idx_vertex1", "idx_vertex2", "idx_vertex3" ],
  "vertices": [ [2,49,2.1,49.1], [3,50,3.1,50.1], [2, 50, 2.1,50.1] ],
  "triangles": [ [0, 1, 2] ]
}

So after the generic metadata, we define the input and output CRS (informative only), and that the transformation affects horizontal components of coordinates. We name the columns of the vertices and triangles arrays. We defined the source and target coordinates of each vertex, and define a triangle by referring to the index of its vertices in the vertices array.

More formally, the specific items for the triangulation file are:

input_crs

String identifying the CRS of source coordinates in the vertices. Typically EPSG:XXXX. If the transformation is for vertical component, this should be the code for a compound CRS (can be EPSG:XXXX+YYYY where XXXX is the code of the horizontal CRS and YYYY the code of the vertical CRS). For example, for the KKJ->ETRS89 transformation, this is EPSG:2393 (KKJ / Finland Uniform Coordinate System). The input coordinates are assumed to be passed in the "normalized for visualisation" / "GIS friendly" order, that is longitude, latitude for geographic coordinates and easting, northing for projected coordinates.

output_crs

String identifying the CRS of target coordinates in the vertices. Typically EPSG:XXXX. If the transformation is for vertical component, this should be the code for a compound CRS (can be EPSG:XXXX+YYYY where XXXX is the code of the horizontal CRS and YYYY the code of the vertical CRS). For example, for the KKJ->ETRS89 transformation, this is EPSG:3067 ("ETRS89 / TM35FIN(E,N)"). The output coordinates will be returned in the "normalized for visualisation" / "GIS friendly" order, that is longitude, latitude for geographic coordinates and easting, northing for projected coordinates.

transformed_components

Array which may contain one or two strings: "horizontal" when horizontal components of the coordinates are transformed and/or "vertical" when the vertical component is transformed.

fallback_strategy

String identifying how to treat points that do not fall into any of the specified triangles. This item is available for format_version >= 1.1. Possible values are none, nearest_side and nearest_centroid. The default is none and signifies, that points that fall outside the specified triangles are not transformed. This is also the behavior for format_version before 1.1. If fallback_strategy is set to nearest_side, then points that do not fall into any triangle are transformed according to the triangle closest to them by euclidean distance. If fallback_strategy is set to nearest_centroid, then points that do not fall into any triangle are transformed according to the triangle with the closest centroid (intersection of its medians).

vertices_columns

Specify the name of the columns of the rows in the vertices array. There must be exactly as many elements in vertices_columns as in a row of vertices. The following names have a special meaning: source_x, source_y, target_x, target_y, source_z, target_z and offset_z. source_x and source_y are compulsory. source_x is for the source longitude (in degree) or easting. source_y is for the source latitude (in degree) or northing. target_x and target_y are compulsory when horizontal is specified in transformed_components. (source_z and target_z) or offset_z are compulsory when vertical is specified in transformed_components

triangles_columns

Specify the name of the columns of the rows in the triangles array. There must be exactly as many elements in triangles_columns as in a row of triangles. The following names have a special meaning: idx_vertex1, idx_vertex2, idx_vertex3. They are compulsory.

vertices

An array whose items are themselves arrays with as many columns as described in vertices_columns.

triangles

An array whose items are themselves arrays with as many columns as described in triangles_columns. The value of the idx_vertexN columns must be indices (between 0 and len(vertices-1) of items of the vertices array.

A JSON schema is available for this file format.