town envs brainshit

lucidiot's cybrecluster

Well-Known Binary ISO avec Kaitai Struct, partie 1

Lucidiot — Informatique — 2022-02-06
L'écart entre les organismes de standardisation et la réalité va devenir flagrant.

On attaque aujourd'hui la deuxième des trois variantes du Well-Known Binary : la variante ISO. C'est probablement la plus complexe des trois ! Je vais probablement passer autant de temps à expliquer chacun des concepts qu'à les définir en YAML.

J'ai pu mettre la main grâce à la Wayback Machine sur un brouillon de la spécification ISO 13249-3:2016 édité en 2015, vu que je ne vais certainement pas payer des centaines d'euros pour plus d'un millier de pages de charabia incompréhensible et inutile, et vu que le site de l'ISO était en panne au moment où les recherches sur cet article ont été effectuées.

J'avais auparavant accédé à une version datant de 2002, et en un peu plus de dix ans la spécification a donc évolué de 500 à 1500 pages, et elle n'a plus grand chose à avoir avec les implémentations actuelles dans les divers systèmes d'information géographiques. Il y a un très grand nombre de notions qui ont été ajoutées au fil du temps et qui n'ont pourtant jamais été implémentées nulle part, et dont l'utilité concrète semble de moins en moins évidente. Certaines des notions sont si rarement utilisées qu'elles ne peuvent pas être sérialisées en WKB ou WKT du tout, donc on ne les verra pas ici. Il est assez clair que tout le monde préfère largement suivre les standards de l'Open Geospatial Consortium, qui sont plus lisibles et plus sains d'esprit. Ça ne fera qu'une critique de plus parmi les nombreuses qu'on peut faire de l'ISO…

Entre le WKB standard et le WKB ISO, les deux changements principaux sont de nouveaux types de géométries, notamment des courbes, et le support de deux nouvelles dimensions. Nous allons commencer par traiter séparément tous ces types de géométries, et nous essaierons plus tard de gérer les dimensions multiples, ce qui ne sera pas une mince à faire.

Cette spécification définit le WKB à l'aide d'une grammaire ABNF similaire à celle du WKT standard. Cette grammaire est parfois utile puisqu'elle va définir les choses de façon plus formelle, mais pour des données binaires, cela peut rapidement rendre la lecture très difficile, notamment parce qu'il faut faire énormément d'allers et retours entre des pages pour comprendre le type de chaque attribut, distinguer certains attributs très proches mais nommés différemments, ou juste comprendre ce que chaque attribut est censé faire. Par conséquent, j'ai dû faire pas mal de recherches sur chaque géométrie pour comprendre ce que c'est avant d'essayer de l'implémenter, et je vais en parler assez longuement, plus que dans mes articles sur le WKT. Cela a fortement rallongé les articles, donc aujourd'hui, on ne va voir que tout ce qui se rapproche des triangles.

Triangle

On a déjà pu frôler le triangle quand on a essayé d'atteindre le support complet du Well-Known Text, puisqu'il est aussi défini par l'Open Geospatial Consortium. Le triangle est un sous-type de polygone qui ne dispose que d'un seul anneau linéaire, et cet anneau linéaire est composé de quatre points — le dernier point est égal au premier pour fermer l'anneau.

Dans Kaitai Struct, il est possible de définir des constantes à l'aide de contents, ce qui peut être utile pour gérer un nombre magique. On pourrait donc rendre constant le nombre d'anneaux linéaires et de points du triangle :

- id: count
  # Un seul anneau linéaire
  contents: [0x00, 0x00, 0x00, 0x01]

Le fonctionnement de Kaitai fait cependant que ces constantes ne sont pas influencées par le boutisme qu'on a défini précédemment avec endianness. On ne peut par conséquent pas avoir recours à ce système ! On pourrait peut-être utiliser à la place un système d'assertions, qui vérifie que le nombre qu'on a compris est bien égal à 1 :

- id: count
  type: u4
  valid: 1

Cette syntaxe a été proposée pour la version 0.10 de Kaitai Struct, et vous pouvez en lire la discussion dans une issue GitHub, mais elle n'est pas encore disponible. Par conséquent, on n'y aura pas droit non plus.

On va donc se contenter de traiter le triangle exactement comme si c'était un polygone. On ajoute d'abord son identifiant de type à l'énumération des types de géométrie :

enums: {
  geometry_type: {
    # ...
    "17": "triangle"
  }
}

On peut ensuite l'associer à notre type polygon existant dans le switch-on qui détermine le corps de la géométrie.

{
  switch-on: "type",
  cases: {
    # ...
    "geometry_type::triangle": "polygon"
  }
}

Surface polyédrale

Il y a moult types que je ne mentionne pas directement tout en les définissant dans le fichier YAML, notamment parce qu'ils n'ont pas de représentation en WKB. Un de ces types est ST_Surface, un type « non-instanciable », c'est-à-dire un type qui est défini mais qui ne sert à rien tout seul puisqu'il ne peut pas être utilisé. Le polygone et le triangle sont des exemples de surfaces, et une surface de façon générale est une collection d'anneaux de points.

La surface polyédrale est déclarée comme étant une surface, mais au lieu d'être une collection d'anneaux, c'est une collection de polygones, autrement dit, une collection de collections d'anneaux. Elle est donc techniquement à la dimension 3 en étant définie à la dimension 2. La dimension 0 est le point, la dimension 1 est la courbe (une ligne brisée est un sous-type de courbe), la dimension 2 est la surface, et le concept de dimension 3 n'est utilisé que pour le solide, qu'on verra plus tard. La consistance est clairement le maître mot dans ce standard…

On avait déjà vu la surface polyédrale dans le contexte du WKT. On avait suivi le standard OGC à ce moment-là, mais la définition de la surface polyédrale est différente entre les deux standards, donc il me faudra probablement repasser sur le WKT pour le complexifier un peu plus. Dans son principe, elle reste une collection de polygones dont les bords se touchent, et c'est ce qui fait qu'elle peut se comporter comme une seule et une unique surface ; si on ne considère que le bord extérieur de tous les polygones ensemble, avec tous les anneaux intérieurs, la surface polyédrale forme un grand polygone seul.

C'est reparti pour un tour ; on peut réutiliser notre type multi_polygon, qui contient déjà une collection de polygones définie exactement comme celle de la surface polyédrale.

enums: {
  geometry_type: {
    # ...
    "15": "polyhedral_surface"
  }
}
# ...
types: {
  geometry: {
    seq: ({
      switch-on: "type",
      cases: {
        # ...
        "geometry_type::polyhedral_surface": "multi_polygon"
      }
    } | endianize)
  }
}

Réseau triangulaire irrégulier

Le réseau triangulaire irrégulier, en anglais TIN, est l'équivalent de la surface polyédrale mais restreint à des triangles : une collection de triangles donc. On l'utilise généralement pour former une représentation de l'élévation du terrain, donc il est le plus souvent utilisé avec trois ou quatre dimensions. On pourrait donc se dire qu'ici on peut utiliser encore une fois multi_polygon, puisqu'on ne peut pas avoir de vérifications systématiques dans Kaitai Struct pour limiter à 4 points, mais il y a des données supplémentaires. On l'avait là aussi déjà vu dans le traitement du WKT, mais il prend cette fois une toute autre envergure. Voici la structure complète d'un TIN :

Un TIN commence par une liste de triangles WKB assez classique. Mais il continue ensuite avec une liste d'éléments TIN ou ST_TINElement, et se termine par une longueur maximale du côté de chaque triangle.

Les éléments TIN

Les éléments TIN sont assez étranges ; c'est comme si on associait des géométries au TIN en tant que métadonnées arbitraires. Les éléments TIN ont un type, qui est une chaîne de caractères allant jusqu'à 30 caractères. Ils ont ensuite un identifiant optionnel, sous forme de nombre entier signé, contrairement à tous les autres nombres non signés auxquels nous étions habitués depuis le début. L'identifiant est tout simplement à zéro s'il n'est pas défini ; en WKT, on l'omettrait complètement. Il y a également une étiquette optionelle, appellée tag, qui permet de stocker une information supplémentaire arbitraire sous forme de texte dont l'utilisation n'est pas standardisée du tout. Cette chaîne de caractères peut atteindre 64 caractères. Enfin, on a une géométrie quelconque, obligatoire, décrite comme un autre WKB ; de la récursion encore une fois !

Les chaînes de caractères se composent d'un octet tout simple qui donne leur longueur, suivi par leur texte. Chaque chaîne de caractères n'est pas spécifiée de façon très explicite par le standard ; l'encodage des caractères n'est notamment pas spécifié. Je vais assumer que nous travaillons en UTF-8, parce que c'est l'encodage le plus banal de nos jours, et celui souvent par défaut dans les bases de données.

Il existe quelques types prédéfinis d'éléments TIN, et ces types ont des types particuliers de géométries spécifiés. Cependant, les implémentations sont libres de choisir quels types prédéfinis elles prennent en charge, donc en fait, il n'y a pas vraiment de restrictions particulières. Ces types prédéfinis aident cependant à comprendre un peu l'intérêt de ce système de métadonnées assez étrange :

random points

Ensemble de points 3D à partir desquels on peut générer une surface faisant partie du TIN.

group spot

La même chose que random points, avec la différence que les points de l'ensemble ont quelque chose à voir les uns avec les autres, et ne sont pas juste complètement arbitraires ou aléatoires.

boundary

Un polygone 3D qui restreint le TIN à une zone donnée. Il ne peut y en avoir qu'un par TIN, et le support des anneaux linéaires intérieurs du polygone est optionnel.

breakline

Une ligne brisée 3D que les triangles du TIN ne sont pas autorisés à dépasser. Les triangles doivent être réajustés (on appelle ça la retriangulation) pour suivre exactement cette ligne ; cela permet de déformer le TIN pour suivre une ligne d'élévation connue.

soft break

La même chose qu'une breakline, sauf que la déformation potentiellement engendrée n'est plus aussi abrupte ; la retriangulation peut se permettre d'adoucir les contours pour suivre la contrainte.

control contour

La même chose qu'une breakline, sauf que tous les points de la ligne brisée 3D doivent avoir exactement la même élévation.

void

Polygone 3D définissant une zone dans laquelle les triangles du TIN doivent être ignorés, pour indiquer par exemple une zone dans lesquelles on n'a pas de données d'élévation valides. Les triangles doivent être ajustés si nécessaires pour suivre les bords du void comme si c'étaient des breakline.

break void

Polygone 3D dont les données d'élévations écrasent les données d'élévation indiquées par les triangles du TIN ; cela peut être utile pour des données d'élévation complexes où il faudrait un très grand nombre de triangles pour les représenter alors qu'un polygone ferait très bien l'affaire par exemple.

drape void

L'inverse du break void : l'élévation des triangles originaux écrase celle du drape void.

hole

La même chose qu'un drape void, mais il peut être en 2 dimensions.

stop line

Représente une zone où la continuité ou régularité qu'indique le TIN n'est pas garantie. On a l'impression que c'est adouci, mais c'est probablement bien plus le bazar.

Toutes ces métadonnées prédéfinies font beaucoup référence au principe de (re)triangulation, le recalcul automatique de tous les triangles du TIN en fonction de tous ces paramètres. C'est là tout le principe de ce système : on doit pouvoir créer un TIN avec zéro triangles, définir des limites extérieures, ajouter des courbes de niveau connues, des points d'élévation connues, etc., et mélanger tout ça bien fort pour obtenir une modélisation numérique de l'élévation du terrain, en anglais un DEM. Quand on commence à atteindre la troisième dimension spatiale, tout se complexifie !

On va donc définir la chaîne de caractères, et l'élément TIN seul, séparément des géométries. Nous sommes aidés par notre fonction existante endianize pour la gestion du boutisme qu'il réintroduit, donc tout ce qu'on a à faire, c'est définir les quelques attributs qu'on a vu ci-dessus. J'ai mentionné aussi qu'il n'y a aucune réelle restriction particulière sur le contenu des éléments, donc on n'a pas non plus à se soucier des types prédéfinis et de leurs contraintes.

types: {
  wkb_string: {
    seq: [
      {
        id: "length",
        type: "u1"
      },
      {
        id: "value",
        type: "str",
        size: "length",
        encoding: "UTF-8"
      }
    ]
  },
  tin_element: ({
    seq: [
      {
        id: "type",
        type: "wkb_string"
      },
      {
        id: "id",
        type: "s4"
      },
      {
        id: "tag",
        type: "wkb_string"
      },
      {
        id: "geometry",
        type: "geometry"
      }
    ]
  } | endianize)
}

Je définis le type wkb_string pour pouvoir réutiliser la construction de chaîne de caractères deux fois de suite dans notre élément TIN, et j'utilise l'attribut length pour faire varier la longueur de la chaîne de caractères en fonction du nombre entier qui la précède. On découvre s4 au lieu de u4 pour l'identifiant optionnel d'un élément TIN puisque i prend en compte un bit de signe, contrairement à u qui est non-signé.

Définition du TIN

Maintenant que les éléments d'un TIN sont définis, on peut revenir à la définition du TIN lui-même. Elle est un peu plus simple ; une liste de polygones, puis une liste d'éléments TIN, puis un double pour la taille maximale des triangles.

Je pourrais utiliser la fonction counted que nous avions défini précédemment, mais elle renvoie directement un type, et pas seulement la partie d'une séquence d'attributs d'un type. En clair, je ne vais pas pouvoir proprement enchaîner deux listes puis un nombre. On va donc devoir redéfinir notre fonction :

def counted: [
  {
    id: "count",
    type: "u4"
  },
  . + {
    repeat: "expr",
    "repeat-expr": "count"
  }
];

La différence par rapport à la version précédente est seulement que counted renvoie un tableau. On avait autrefois ce tableau entouré de { seq: [...] }. On va donc devoir répercuter ce petit sacrifice sur les autres types existants qui faisaient usage de counted :

types: {
  line_string: {
    seq: ({ id: "points", type: "point" } | counted)
  },
  polygon: {
    seq: ({ id: "rings", type: "line_string" } | counted)
  },
  multi_point: {
    seq: ({ id: "points", type: "wkb_point" } | counted)
  },
  multi_line_string: {
    seq: ({ id: "line_strings", type: "wkb_line_string" } | counted)
  },
  multi_polygon: {
    seq: ({ id: "polygons", type: "wkb_polygon" } | counted)
  },
  geometry_collection: {
    seq: ({ id: "geometries", type: "geometry" } | counted)
  },
}

On va dire qu'au moins, il y a un peu plus d'aération entre chaque type.

La définition du TIN se résume donc maintenant à assembler deux appels à counted pour les deux listes avec un dernier attribut de type f8. jq nous permet d'additionner des tableaux pour les concaténer, donc ce n'est pas très compliqué :

enums: {
  geometry_type: {
    # ...
    "16": "tin"
  }
}
types: {
  geometry: {
    seq: ({
      switch-on: "type",
      cases: {
        # ...
        "geometry_type::tin": "tin"
      }
    } | endianize),
    types: {
      tin: {
        seq: (
          ({ id: "triangles", type: "wkb_polygon" } | counted)
          + ({ id: "elements", type: "tin_element" } | counted)
          + [
            {
              id: "max_side_length",
              type: "f8"
            }
          ]
        )
      }
    }
  }
}

Il y a encore un autre problème ! Avec ce système, la génération de code du type tin donnera quelque chose comme ceci :

tin:
  seq:
  - id: count
    type: u4
  - id: triangles
    type: wkb_polygon
    repeat: expr
    repeat-expr: count
  - id: count
    type: u4
  - id: elements
    type: tin_element
    repeat: expr
    repeat-expr: count
  - id: max_side_length
    type: f8

Avec cette définition, on aura une erreur de Kaitai Struct :

Call stack: undefined io.kaitai.struct.format.YAMLParseException: /types/geometry/types/body/types/tin/seq/2: duplicate attribute ID 'count', previously defined at /types/geometry/types/body/types/tin/seq/0

L'attribut count est en double, parce que la fonction counted définit à chaque fois un attribut count. On peut corriger ça en ajoutant la capacité à la fonction d'utiliser un paramètre optionnel de préfixe d'attribut :

def counted(prefix): [
  {
    id: "\(prefix)count",
    type: "u4"
  },
  . + {
    repeat: "expr",
    "repeat-expr": "\(prefix)count"
  }
];

def counted: counted("");

On utilise l'interpolation de chaîne de caractères disponible dans jq pour ajouter prefix à notre attribut count. La fonction counted nécessite cependant maintenant un argument, et la notion d'arguments par défaut, typés, ou optionnels n'existe pas dans jq. On définit donc une autre fonction counted sans arguments, qui appelle counted sans préfixe, pour maintenir une compatibilité pour tous les autres types.

On peut maintenant utiliser notre nouvelle définition dans tin :

seq: (
  ({ id: "triangles", type: "wkb_polygon" } | counted("triangle_"))
  + ({ id: "elements", type: "tin_element" } | counted("element_"))
  + [
    {
      id: "max_side_length",
      type: "f8"
    }
  ]
)

On obtiendra alors triangle_count et element_count, et Kaitai Struct sera très content.

Script actuel

#!/usr/bin/jq
# Generates a Kaitai Struct-compatible JSON structure to parse
# the ISO Well-Known Binary.
# Usage: oq -n -o simpleyaml -f wkb_iso.jq  wkb_iso.ksy

def endianize: {
  seq: [
    {
      id: "endianness",
      type: "u1"
    },
    {
      id: "body",
      type: "body"
    }
  ],
  types: {
    "body": (. + {
      meta: {
        endian: {
          "switch-on": "_parent.endianness",
          cases: {
            "0": "be",
            "1": "le"
          }
        }
      }
    })
  }
};

def counted(prefix): [
  {
    id: "\(prefix)count",
    type: "u4"
  },
  . + {
    repeat: "expr",
    "repeat-expr": "\(prefix)count"
  }
];

def counted: counted("");

def wkb_seq: [
  {
    id: "type",
    type: "u4",
    enum: "geometry_type"
  },
  {
    id: "data",
    type: .
  }
];

{
  meta: {
    id: "wkb_iso",
    title: "ISO Well-Known Binary",
    license: "AGPL-3.0-or-later",
    xref: {
      iso: "19125-3:2015"
    }
  },
  "doc-ref": [
    "https://www.ogc.org/standards/sfa",
    "http://libgeos.org/specifications/wkb/"
  ],
  seq: [
    {
      id: "geometry",
      type: "geometry"
    }
  ],
  enums: {
    geometry_type: {
      "0": "geometry",
      "1": "point",
      "2": "line_string",
      "3": "polygon",
      "4": "multi_point",
      "5": "multi_line_string",
      "6": "multi_polygon",
      "7": "geometry_collection",
      "15": "polyhedral_surface",
      "16": "tin",
      "17": "triangle"
    }
  },
  types: {
    geometry: ({
      seq: ({
        "switch-on": "type",
        cases: {
          "geometry_type::point": "point",
          "geometry_type::line_string": "line_string",
          "geometry_type::polygon": "polygon",
          "geometry_type::multi_point": "multi_point",
          "geometry_type::multi_line_string": "multi_line_string",
          "geometry_type::multi_polygon": "multi_polygon",
          "geometry_type::geometry_collection": "geometry_collection",
          "geometry_type::polyhedral_surface": "multi_polygon",
          "geometry_type::tin": "tin",
          "geometry_type::triangle": "polygon"
        }
      } | wkb_seq),
      types: {
        point: {
          seq: [
            {
              id: "x",
              type: "f8"
            },
            {
              id: "y",
              type: "f8"
            }
          ]
        },
        line_string: {
          seq: ({ id: "points", type: "point" } | counted)
        },
        polygon: {
          seq: ({ id: "rings", type: "line_string" } | counted)
        },
        wkb_point: ({ seq: ("point" | wkb_seq) } | endianize),
        wkb_line_string: ({ seq: ("line_string" | wkb_seq) } | endianize),
        wkb_polygon: ({ seq: ("polygon" | wkb_seq) } | endianize),
        multi_point: {
          seq: ({ id: "points", type: "wkb_point" } | counted)
        },
        multi_line_string: {
          seq: ({ id: "line_strings", type: "wkb_line_string" } | counted)
        },
        multi_polygon: {
          seq: ({ id: "polygons", type: "wkb_polygon" } | counted)
        },
        geometry_collection: {
          seq: ({ id: "geometries", type: "geometry" } | counted)
        },
        wkb_string: {
          seq: [
            {
              id: "length",
              type: "u1"
            },
            {
              id: "value",
              type: "str",
              size: "length",
              encoding: "UTF-8"
            }
          ]
        },
        tin_element: ({
          seq: [
            {
              id: "type",
              type: "wkb_string"
            },
            {
              id: "id",
              type: "s4"
            },
            {
              id: "tag",
              type: "wkb_string"
            },
            {
              id: "geometry",
              type: "geometry"
            }
          ]
        } | endianize),
        tin: {
          seq: (
            ({ id: "triangles", type: "wkb_polygon" } | counted("triangle_"))
            + ({ id: "elements", type: "tin_element" } | counted("element_"))
            + [
              {
                id: "max_side_length",
                type: "f8"
              }
            ]
          )
        }
      }
    } | endianize)
  }
}

Conclusion

Si vous avez réussi à suivre les précédents articles et que vous pensiez que le traitement de la variante standard du WKB était déjà bien trop compliqué, vous êtes servis. On va aller encore plus loin la prochaine fois en rentrant dans le domaine des courbes, et en tordant encore plus les notions de mathématiques pour suivre les désirs des technocrates géospatiaux.

Vous vous demandez peut-être à nouveau pourquoi je vais aussi loin sur ce format ; je n'ai pas tellement besoin de traiter la variante ISO en soit, puisque l'absence totale d'implémentations signifie qu'on ne la rencontrera jamais. Cela dit, j'ai en tête des projets qui pourraient faire usage du WKB et pourraient même plus tard refaire le lien avec les explorations de réseaux Wi-Fi. C'est encore très loin cela dit, et vous n'en entendrez pas parler pendant au moins plusieurs mois. En attendant, vous pourrez je suppose admirer mon courage…

Commentaires

Il n'y a pour l'instant aucun commentaire. Soyez le premier !