town envs brainshit

lucidiot's cybrecluster

Well-Known Binary ISO avec Kaitai Struct, partie 4

Lucidiot — Informatique — 2022-02-27
Sans doute l'article le plus long et le plus complexe de toute l'histoire de ce blog… pour l'instant en tous cas.

Dans ce nouvel opus d'une série sur du traitement de fichiers binaires qui s'éternise et commence à m'épuiser autant que mes lecteurs, nous allons enfin venir à bout de la variante ISO du Well-Known Binary en prenant en charge une dernière fonctionnalité importante : la gestion de trois et de quatre dimensions. Autant vous avertir : cet article a été suffisamment long pour nécessiter que j'apporte des modifications à la base de données de Brainshit pour qu'elle soit capable de le stocker !

Introduction aux dimensions

Dans le WKB standard, ainsi que jusqu'à présent, nous n'avons travaillé qu'avec deux dimensions X et Y. J'ai cependant plusieurs fois mentionné les dimensions Z (élévation) et M (mesure). La dimension Z est une dimension spatiale supplémentaire pour représenter l'altitude, et elle est notamment utile pour le réseau triangulaire irrégulier (TIN) puisque son utilisation concrète se résume à la topologie. La dimension M est une dimension non-spatiale qui permet d'associer à des entités géospatiales des données numériques quelconques, et surtout de faire des opérations mathématiques dessus en utilisant les fonctions disponibles pour les données spatiales. Par exemple, si vous souhaitiez filtrer pour n'avoir que les dimensions X, Y, Z et M entre 10 et 20, vous pourriez utiliser WHERE ST_Intersects(feature, ST_GeomFromText('LINESTRING ZM ((10 10 10 10, 20 20 20 20))')) directement. D'autres fonctions peuvent être encore plus intéressantes, telles que celles de clustering pour regrouper les entités entre elles et observer des tendances.

Ces deux dimensions supplémentaires et optionnelles existent depuis longtemps dans les systèmes d'information géographiques mais sont arrivées assez tardivement dans le standard ISO, causant l'appartion du WKB étendu que nous verrons après ce WKB ISO. Ces deux dimensions existant désormais dans le standard ISO, on va pouvoir essayer de les implémenter dans notre schéma. Voici l'état de leur prise en charge :

À première vue, on peut se dire qu'on peut construire toutes les géométries avec et sans Z, et juste ignorer le vecteur et le placement affine quand on ajoute M. Mais c'est sans compter un petit nouveau dont nous n'avons pas encore parlé !

Solide à représentation surfacique

La représentation surfacique, abrégée en anglais B-Rep, est une technique consistant à modéliser des solides par un ensemble de surfaces contigues. Prenons par exemple un cube : il y a 6 faces, donc on va décrire ces 6 faces séparément, avec des bords qui se touchent, et les regrouper ensemble et dire qu'elles forment un seul et unique solide.

Il existe d'autres façons de représenter des solides, mais ISO ne semble vraiment ne s'intéresser qu'à la représentation surfacique. Le BRepSolid de la norme ISO se compose d'une ou plusieurs surfaces polyédrales ou surfaces composées, et ne peut être représenté qu'avec les dimensions X, Y et Z, sans M. Il est vrai qu'avec seulement deux dimensions, il est assez difficile de représenter un solide, mais je ne comprends pas vraiment l'absence de la dimension M, qui peut très bien être représentée par les surfaces qui composent ce solide. Peut-être est-ce ma version du standard qui n'est pas assez à jour ? Je ne le saurai pas vraiment. Le BRepSolid est plutôt mal documenté dans le standard par rapport aux autres, probablement parce qu'il n'est pas très utile de toute façon.

On va quand même pouvoir essayer de le représenter dans notre parseur en utilisant les quelques bribes d'informations dont on dispose. Voilà la grammaire ABNF de ce solide :

<brepsolidz binary representation> ::= <byte order> <wkbbrepsolidz> [ <num> <wkbshellz binary>... ]
<wkbbrepsolidz> ::= <uint32>
<wkbshellz binary> ::=
  <polyhedralsurfacez binary representation>
  | <polyhedralsurfacezm binary representation>
  | <compoundsurfacez binary representation>
  | <compoundsurfacezm binary representation>

Ce solide est en fait un ensemble de surfaces polyhédrales ou de surfaces composées. La surface composée peut contenir des surfaces polyhédrales, donc avoir une surface polyhédrale ici est assez redondant. Mais ce qui est encore plus étrange, c'est le fait que la dimension M est ici autorisée pour le contenu du solide ! En lisant très attentivement le standard, on remarque un passage qui explique en fait que la dimension M de ces surfaces est totalement ignorée, donc que leur stockage ici est complètement inutile.

Quoi qu'il en soit, la représentation de ce solide n'est pas très difficile avec les fonctions qu'on a déjà construit ; c'est comme si on construisait une version plus spécifique du multi_surface.

wkb_shell_xyz: ({
  seq: (
    {
      "switch-on": "type",
      cases: {
        "geometry_type::polyhedral_surface": "multi_polygon",
        "geometry_type::compound_surface": "compound_surface"
      }
    } | wkb_seq
  )
}),
brep_solid_xyz: {
  seq: ({ id: "shells", type: "wkb_shell_xyz" } | counted)
}

Notez que j'utilise déjà une notation inhabituelle, où chaque types est suivi du suffixe de ses dimensions, et que pour l'instant je n'ai recours que aux surfaces à deux dimensions, ce qui n'est pas ce qu'on a véritablement ici. On verra tout à l'heure comment on peut mieux gérer tout ça, quand on aura implémenté correctement la gestion des dimensions.

Différences selon les dimensions

Pour avoir une meilleure idée de ce qui nous attend avec la gestion de différentes dimensions, observons les valeurs supplémentaires qui seront ajoutées à nos types existants en fonction des dimensions appliquées.

Identifiants

L'identifiant du type de géométrie est aussi utilisé pour indiquer le nombre de dimensions dans celle-ci. Dans le WKB ISO, on ajoute 1000 pour indiquer la dimension Z, 2000 pour M, et 3000 pour Z et M simultanément. Voilà donc un tableau un résume tous les identifiants possibles, à l'exception des identifiants 100000x qui étaient là pour des raisons de rétrocompatibilité :

Points et vecteurs

Pour les points et les vecteurs, ce n'est pas très compliqué. S'il y a la dimension Z, on rajoute un troisième nombre à virgule flottante. S'il y a une dimension M, seulement dans le cas du point, on ajoute encore un nombre à virgule flottante.

Placement affine

Dans le cas du placement affine, la dimension M n'est pas permise. La seule modification qu'on aura donc, avec la dimension Z, est que l'emplacement de référence sera un point en XYZ, et les vecteurs seront toujours au nombre de trois et auront eux aussi une dimension Z.

Notons que, comme pour le triangle ou d'autres types que nous avons vu précédemment, il ne sera pas possible de valider la contrainte spécifiant qu'il n'y a forcément que trois vecteurs, donc on n'en tiendra pas compte.

Surfaces, collections, courbes simples ou composées

Je définis ici les courbes simples comme des courbes définies seulement par une série de points : la ligne brisée, la chaîne d'arcs de cercles, le cercle et la chaîne de géodésiques. Pour ces courbes, la même chose s'appliquera que pour tous les autres types qui ne font que contenir une liste d'autres éléments : les polygones, polygones courbes, triangles, ensembles de points, ensembles de lignes brisées, ensembles de polygones, ensembles de courbes, ensembles de surfaces, courbes composées ou surfaces composées.

Ce n'est pas très compliqué : la dimension de tous les éléments qui s'y trouvent est modifiée. Il n'est pas possible d'avoir des géométries de dimensions différentes, même dans une collection de géométries, et c'est tant mieux.

Courbe NURBS

Les points de contrôle de la courbe NURBS peuvent avoir la dimension Z mais pas M, tout comme le placement affine dans les trois autres courbes. Pour la dimension M, deux nombres à virgule flottante viennent s'ajouter à la fin de la définition de chaque courbe pour indiquer la valeur de M au début et à la fin de la courbe.

Les points des courbes NURBS sont donc redéfinis pour juste inclure le Z dans le point WKB qu'ils contiennent, et leurs autres attributs ne sont pas modifiés.

Autres courbes

Pour les trois derniers types, qui sont la courbe elliptique, la clothoïde et la courbe en spirale, la gestion des dimensions supplémentaires est là aussi assez particulière.

Voilà à quoi ressemble la clothoïde avec les quatre dimensions :

Le placement affine, comme les points de la courbe NURBS, est complété par la dimension Z, et pour la dimension M, on rajoute là aussi deux nombres à virgule pour la mesure en début et en fin de courbe.

Gestion des identifiants

Pour commencer en douceur, on va essayer de seulement générer les valeurs de l'énumération geometry_type, c'est-à-dire l'association aux nombres entiers du type de géométrie à des noms plus compréhensibles. Le tableau présenté précédemment qui résume tous les identifiants nous montre que nous pouvons générer la quasi-totalité des identifiants en faisant quelques additions, et il y a seulement 5 cas particuliers. On va définir une seule fois les identifiants 0 à 24, ajouter 1000, 2000 et 3000 pour obtenir les autres dimensions, et enfin ajouter manuellement les 5 identifiants du solide à représentation surfacique, du vecteur et du placement affine, et les identifiants supplémentaires de rétrocompatibilité.

geometry_type: (
  {
    "0": "geometry",
    "1": "point",
    "2": "line_string",
    "3": "polygon",
    "4": "multi_point",
    "5": "multi_line_string",
    "6": "multi_polygon",
    "7": "geometry_collection",
    "8": "circular_string",
    "9": "compound_curve",
    "10": "curve_polygon",
    "11": "multi_curve",
    "12": "multi_surface",
    "15": "polyhedral_surface",
    "16": "tin",
    "17": "triangle",
    "18": "circle",
    "19": "geodesic_string",
    "20": "elliptical_curve",
    "21": "nurbs_curve",
    "22": "clothoid",
    "23": "spiral_curve",
    "24": "compound_surface"
  }
  | to_entries
  | [
    . as $entries
    | [
      [0, ""],
      [1, "z"],
      [2, "m"],
      [3, "zm"]
    ][]
    | . as $dimension
    | $entries[]
    | {
      key: (.key | tonumber + $dimension[0] * 1000 | tostring),
      value: "\(.value)_xy\($dimension[1])"
    }
  ] | from_entries
  | . + {
    "101": "vector_xy",
    "102": "affine_placement_xy",
    "1101": "vector_xyz",
    "1102": "affine_placement_xyz",
    "1025": "brep_solid_xyz",
    "1000001": "circular_string_xy",
    "1000002": "compound_curve_xy",
    "1000003": "curve_polygon_xy",
    "1000004": "multi_curve_xy",
    "1000005": "multi_surface_xy"
  }
)

J'ai dit en douceur ? Toutes mes excuses.

Le principe de ce script est d'itérer sur un tableau de deux paramètres, l'un donnant le multiplicateur (0 pour 0, 1 pour 1000, etc.) et l'autre le suffixe de dimension qu'on veut. On a toujours _xy, donc je n'ai indiqué que z et m. On prend un objet qui contient les 25 types de géométries qui peuvent être répétés pour toutes les dimensions, et on utilise ce tableau de paramètres pour répéter ces identifiants avec le bon nombre de milliers et le bon suffixe. On ajoute enfin les cas particuliers, qui ne méritent pas d'être factorisés.

Le plus compliqué dans ce script vient du fonctionnement même de jq pour la manipulation des objets ; on se retrouve à utiliser des conversions en tableaux avec to_entries et from_entries ainsi que des variables pour pouvoir accéder en même temps aux identifiants originaux et aux dimensions.

On doit maintenant mettre à jour le grand switch-on sur le type geometry, qui détermine quel type Kaitai Struct utiliser dès qu'on a fini de lire le boutisme et le type, et donc qui doit avoir toutes les associations pour toutes ces nouvelles dimensions. On avait déjà fait un peu de factorisation dans l'article précédent pour avoir $curves et $surfaces, réutilisables dans le cas particulier de l'ensemble de courbes et de l'ensemble de surfaces. On va les conserver, car on en aura besoin dans leur état actuel plus tard, et on va utiliser une approche similaire à celle qu'on vient de faire pour transformer "geometry_type::something": "something" en "geometry_type::something_xyzm": "something_xyzm" :

def dimension_suffix(suffix): with_entries({
  key: "\(.key)_xy\(suffix)",
  value: "\(.value)_xy\(suffix)"
});

types: {
  geometry: {
    seq: ({
      "switch-on": "type",
      cases: (
        ($curves + $surfaces + {
          "geometry_type::point": "point",
          "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::multi_curve": "multi_curve",
          "geometry_type::multi_surface": "compound_surface"
        }) as $types
        | ["", "z", "m", "zm"]
        | map(. as $dimension | $types | dimension_suffix($dimension))
        | add + {
        "geometry_type::vector_xy": "point_xy",
        "geometry_type::vector_xyz": "point_xyz",
        "geometry_type::affine_placement_xy": "affine_placement_xy",
        "geometry_type::affine_placement_xyz": "affine_placement_xyz",
        "geometry_type::brep_solid_xyz": "brep_solid_xyz"
      })
    } | wkb_seq),
    # ...
  },
  # ...
}

On commence par stocker dans $types l'objet qui contient les 24 types de géométries qu'on acceptera dans toutes les dimensions. On retrouve ensuite un tableau qui définit les 4 combinaisons de dimensions disponibles, puis on les utilise avec une nouvelle fonction dimension_suffix qui ajoute le suffixe qu'on veut à tous ces types. On se retrouve alors avec un tableau d'objets, chaque objet ayant toutes ses clés et valeurs avec le suffixe d'une des combinaisons de dimensions. On peut utiliser add pour les additionner ensemble et construire un unique objet, auquel on peut ajouter les quelques cas particuliers.

J'aurais pu utiliser une fonction aussi pour la gestion des identifiants numériques, mais je n'avais pas trop envie de définir une fonction pour qu'elle ne soit utilisée qu'une seule fois et qu'elle aie une description assez étrange. On utilisera par contre dimension_suffix un peu plus tard.

Gestion des types

Pour la gestion des attributs spécifiques à chaque type de géométrie, je vais utiliser un système plus simple, pour de vrai cette fois. Le principe va être d'avoir une fonction qui acceptera comme paramètre le suffixe de dimension, comme tout à l'heure ; "", "z", "m" ou "zm". On utilisera ensuite ce suffixe avec des conditions pour pouvoir ajouter ou modifier des attributs en fonction des dimensions supplémentaires. Voilà à quoi ressemble l'appel à cette fonction, depuis la racine du script :

def dimension_types: {
  point: { 
    # ...
  },
  line_string: {
    # ...
  }
  # ...
};

{
  # ...
  types: {
    geometry: ({
      seq: ...,
      types: (
        ["", "z", "m", "zm"]
        | map(dimension_types)
        | add
      )
    } | endianize)
  }
}

Réorganisation du script

Si déjà on fait le déplacement du contenu actuel de types vers la fonction, on va se heurter à des erreurs :

jq: error: $curves is not defined at <top-level>, line 283:
        cases: $curves               
jq: error: $surfaces is not defined at <top-level>, line 291:
        cases: $surfaces               
jq: 2 compile errors

Les variables $curves et $surfaces sont définies juste avant le début de l'objet principal qui décrit l'intégralité de notre schéma. La structure d'un script jq est ainsi faite que les fonctions ne peuvent être définies qu'avant un script principal, et que les variables ne peuvent être définies que dans le script principal. Puisqu'on ne peut pas utiliser de variables avant qu'elles ne soient définies et qu'on ne peut pas définir des variables avant des fonctions, on va redéfinir nos deux variables en tant que fonctions :

def curves: {
  "geometry_type::line_string": "line_string",
  "geometry_type::circular_string": "line_string",
  "geometry_type::compound_curve": "multi_curve",
  "geometry_type::circle": "line_string",
  "geometry_type::geodesic_string": "line_string",
  "geometry_type::elliptical_curve": "elliptical_curve",
  "geometry_type::nurbs_curve": "nurbs_curve",
  "geometry_type::clothoid": "clothoid",
  "geometry_type::spiral_curve": "spiral_curve"
};

def surfaces: {
  "geometry_type::polygon": "polygon",
  "geometry_type::curve_polygon": "multi_curve",
  "geometry_type::polyhedral_surface": "multi_polygon",
  "geometry_type::tin": "tin",
  "geometry_type::triangle": "polygon",
  "geometry_type::compound_surface": "compound_surface"
};

def dimension_types: {
  # ...
};

On renommera du coup $curves en curves et $surfaces en surfaces. Leur comportement sera exactement le même qu'avant puisqu'on récupérera de toute façon un objet qui n'est pas influencé par son contexte (.).

On peut maintenant enfin rentrer dans le vif du sujet et traiter l'ajout des dimensions à tous les types de géométries.

Types invariables

On a déplacé l'intégralité de types vers notre fonction, mais il y a quelques types qui ne sont pas concernés du tout par les dimensions : les chaînes de caractères (wkb_string), les éléments TIN, et les nœuds dans les courbes NURBS. On va donc d'abord les redéplacer au bon endroit, en les ajoutant tout simplement après les types qu'on aura généré avec notre fonction. Cette fois, pas de problème de placement comme on a eu avec nos variables ; ces types sont des types de Kaitai Struct, donc ils ne seront vraiment interprétés comme tels que par Kaitai Struct depuis un schéma déjà complètement construit.

types: (
  ["", "z", "m", "zm"]
  | map(dimension_types)
  | add + {
    wkb_string: {
      # ...
    },
    tin_element: {
      # ...
    },
    knot: {
      # ...
    }
  }
)

Point

Nous pouvons commencer par considérer le type le plus simple, le point. Il va introduire la façon que nous allons utiliser pour rendre certains attributs optionnels en fonction des dimensions à ajouter. Commençons par définir un point avec toutes les dimensions possibles en même temps :

point_xyzm: {
  seq: [
    {
      id: "x",
      type: "f8"
    },
    {
      id: "y",
      type: "f8"
    },
    {
      id: "z",
      type: "f8"
    },
    {
      id: "m",
      type: "f8"
    }
  ]
}

Pour rendre un attribut optionnel ici, le plus simple est d'utiliser un nouveau type de valeur de jq, plutôt comparable à l'undefined de JavaScript : empty. Ce mot-clé a des comportements assez particuliers en fonction de là où on l'utilise, et il est conçu pour retourner absolument rien ; pas null, pas une chaîne vide, pas un zéro, mais vraiment rien du tout. Voici un exemple assez parlant :

$ jq --null-input '[empty, true, false, empty]'
[true, false]

Les valeurs empty sont complètement ignorées dans le tableau sortant de ce script. On peut utiliser ça avec des structures conditionnelles : if … then … else empty end va nous permettre de rendre une case d'un tableau optionnelle selon une condition qui nous intéresse. On reçoit en paramètre "", "z", "m" ou "zm", on peut donc utiliser l'opérateur contains pour voir si la chaîne contient une dimension particulière :

"point_xy\(.)": {
  seq: [
    {
      id: "x",
      type: "f8"
    },
    {
      id: "y",
      type: "f8"
    },
    if contains("z") then {
      id: "z",
      type: "f8"
    } else empty end,
    if contains("m") then {
      id: "m",
      type: "f8"
    } else empty end
  ]
}

On peut maintenant générer point_xy, qui ne contiendrait alors que x et y, ou point_xym, qui ne contiendrait pas z.

Cas simples

Notez qu'on a également ajouté _xy\(.) dans la clé du point pour pouvoir prendre en charge l'ajout automatique du suffixe au nom de type. Ce simple ajout de suffixe suffit à résoudre la gestion des dimensions pour un assez grand nombre de types :

{
  "line_string_xy\(.)": {
    seq: ({ id: "points", type: "point_xy\(.)" } | counted)
  },
  "polygon_xy\(.)": {
    seq: ({ id: "rings", type: "line_string_xy\(.)" } | counted)
  },
  "wkb_point_xy\(.)": ({ seq: ("point_xy\(.)" | wkb_seq) } | endianize),
  "wkb_line_string_xy\(.)": ({ seq: ("line_string_xy\(.)" | wkb_seq) } | endianize),
  "wkb_polygon_xy\(.)": ({ seq: ("polygon_xy\(.)" | wkb_seq) } | endianize),
  "multi_point_xy\(.)": {
    seq: ({ id: "points", type: "wkb_point_xy\(.)" } | counted)
  },
  "multi_line_string_xy\(.)": {
    seq: ({ id: "line_strings", type: "wkb_line_string_xy\(.)" } | counted)
  },
  "multi_polygon_xy\(.)": {
    seq: ({ id: "polygons", type: "wkb_polygon_xy\(.)" } | counted)
  },
  "tin_xy\(.)": {
    seq: (
      ({ id: "triangles", type: "wkb_polygon_xy\(.)" } | counted("triangle_"))
      + ({ id: "elements", type: "tin_element" } | counted("element_"))
      + [
        {
          id: "max_side_length",
          type: "f8"
        }
      ]
    )
  },
  "nurbs_point_xy\(.)": ({
    seq: [
      {
        id: "point",
        type: "wkb_point_xy\(.)"
      },
      # One bit is ignored here due to unclear specification
      {
        id: "weight",
        type: "f8"
      }
    ]
  } | endianize),
  "multi_curve_xy\(.)": {
    seq: ({ id: "curves", type: "wkb_curve_xy\(.)" } | counted)
  },
  "compound_surface_xy\(.)": {
    seq: ({ id: "surfaces", type: "wkb_surface_xy\(.)" } | counted)
  }
}

Les types pour lesquels il nous reste du traitement particulier à faire sont les courbes et les surfaces contenues dans les ensembles, les placements affine, les courbes, la collection de géométries et le solide à représentation surfacique.

Ensembles de courbes et surfaces

On a déjà pu convertir multi_curve et compound_surface pour qu'ils utilisent les dimensions, mais ils nécessitent la redéfinition de wkb_curve et wkb_surface pour lesquels un traitement légèrement différent va être nécessaire :

def dimension_types: . as $dimension | {
  "wkb_curve_xy\(.)": ({
    seq: (
      {
        "switch-on": "type",
        cases: (curves | dimension_suffix($dimension))
      } | wkb_seq
    )
  } | endianize),
  "wkb_surface_xy\(.)": ({
    seq: (
      {
        "switch-on": "type",
        cases: (surfaces | dimension_suffix($dimension))
      } | wkb_seq
    )
  } | endianize)
}

On retrouve ici notre fonction dimension_suffix, qui peut donner rapidement à un ensemble de cases un suffixe de dimensions.

Solide à représentation surfacique

Le solide à représentation surfacique est un cas à part puisqu'il n'existe que dans la dimension XYZ. On va donc le définir en bas du script, à côté des types invariables qu'on a vu précédemment. Mais il accepte à la fois des surfaces polyhédrales et composées avec les dimensions XYZ et XYZM, en ignorant en fait complètement la dimension M une fois que le format binaire est interprété. Je n'en comprends pas l'intérêt, mais c'est ce que dit le standard, alors on va le suivre. On va tout simplement utiliser deux fois notre dimension_suffix pour doubler nos deux cas, et tout ajouter, pour former un petit ensemble de types :

wkb_shell_xyz: ({
  seq: (
    {
      "switch-on": "type",
      cases: ({
        "geometry_type::polyhedral_surface": "multi_polygon",
        "geometry_type::compound_surface": "compound_surface"
      } | [dimension_suffix("z"), dimension_suffix("zm")] | add)
    } | wkb_seq
  )
})

Placement affine

Le placement affine a la particularité de n'avoir aucune variante pour la dimension M ; les types _xym et _xyzm ne doivent donc pas du tout apparaître pour lui. Pour ça, on va rajouter une condition à la fin de la fonction dimension_types pour ne les inclure que si la fonction n'a pas été appelée avec la dimension M :

def dimension_types: . as $dimension | {
  # ...
} + if contains("m") then {} else {
  "affine_placement_xy\(.)": {
    seq: (
      [
        {
          id: "location",
          type: "point_xy\(.)"
        }
      ] + ({ id: "reference_directions", type: "point_xy\(.)" } | counted)
    )
  },
  "wkb_affine_placement_xy\(.)": ({ seq: ("affine_placement_xy\(.)" | wkb_seq) } | endianize)
} end;

Lorsque les dimensions souhaitées contiennent M, on ajoute un objet vide à l'objet existant, ce qui résulte en aucun changement. S'il n'y a pas M, alors on ajoute le placement affine. Notez qu'on utilise un objet vide et pas empty ; l'addition de n'importe quoi avec empty renverra empty, donc toute la fonction renverrait empty et on se retrouverait avec plus aucun type généré pour la dimension M. C'est un des nombreux cas particuliers avec l'utilisation de empty, qui doit donc être bien maîtrisée.

Courbe NURBS

Maintenant que le placement affine est redéfini, on peut s'attaquer aux courbes. Le cas de la courbe NURBS est le plus complexe. D'abord, les points de contrôle de la courbe NURBS n'ont pas non plus de dimension M, donc on va les ajouter au même endroit que le placement affine :

"wkb_affine_placement_xy\(.)": {
  # ...
},
"nurbs_point_xy\(.)": ({
  seq: [
    {
      id: "point",
      type: "wkb_point_xy\(.)"
    },
    # One bit is ignored here due to unclear specification
    {
      id: "weight",
      type: "f8"
    }
  ]
} | endianize)

Ensuite, on peut utiliser ces points NURBS dans la définition de la courbe. Cependant, puisqu'il n'existe pas de points avec la dimension M alors qu'une courbe NURBS peut avoir une dimension M, on va devoir soustraire cette dimension dans le nom du type utilisé pour le point :

"nurbs_curve_xy\(.)": {
  seq: (
    [
      {
        id: "degree",
        type: "u1"
      }
    ]
    + ({ id: "control_points", type: "nurbs_point_xy\(rtrimstr("m")" } | counted("control_point_"))
    + ({ id: "knots", type: "knot" } | counted("knot_"))
  )
},

On utilise rtrimstr("m"), une fonction qui va retirer toutes les lettres m qui arrivent à la fin de la chaîne de caractères. On n'a rien spécifié en entrée de la fonction, donc c'est ., notre dimension, qui est utilisée. Si on essaie donc de construire la courbe NURBS pour xym ou xyzm, c'est xy et xyz qui seront utilisés pour le point NURBS.

Il ne reste maintenant plus qu'à ajouter les deux nombres à virgule flottante lorsque la courbe utilise la dimension M :

  seq: (
    # ... +
    ({ id: "knots", type: "knot" } | counted("knot_"))
    + if contains("m") then [
      {
        id: "start_m",
        type: "f8"
      },
      {
        id: "end_m",
        type: "f8"
      }
    ] else [] end
  )

On utilise là aussi un tableau vide en cas d'absence de mesure et pas empty pour ne pas se retrouver avec une séquence qui deviendrait complètement vide après l'addition.

Autres courbes

Pour les autres types de courbes, il faut aussi utiliser rtrimstr("m") pour pouvoir utiliser le placement affine, et ajouter aussi les deux attributs de mesure en début et fin de courbe. Comme cela ferait de la répétition, on peut utiliser une variable pour stocker la liste des deux attributes à ajouter, et utiliser cette variable dans toutes nos courbes :

def dimension_types: . as $dimension | (
  if contains("m") then [
    {
      id: "start_m",
      type: "f8"
    },
    {
      id: "end_m",
      type: "f8"
    }
  ] else [] end
) as $curve_attributes | {
  # ...
  "nurbs_curve_xy\(.)": {
    seq: (
      # ...
      + $curve_attributes
    )
  },
  "elliptical_curve_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m")"
      }
      # ...
    ] + $curve_attributes])
  },
  "clothoid_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m")"
      }
      # ...
    ] + $curve_attributes])
  },
  "spiral_curve_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m")"
      }
      # ...
    ] + $curve_attributes])
  }
};

Collections de géométries

Notre dernier type à traiter est la collection de géométries. La collection de géométries a la particularité qu'elle ne peut contenir que les géométries qui ont les mêmes dimensions qu'elle : une collection de géométries en XYZ ne pourra pas contenir de géométries en XYM par exemple. Pour gérer ce cas, nous allons devoir disposer d'un nouveau type geometry_xy… qui ne contient que les géométries d'une dimension donnée. Ce type contiendra donc une réplique du switch-on global, qui contient déjà pas mal de conditions. Pour commencer, il utilise une variable $types à laquelle nous n'aurons ici pas accès, donc nous allons déjà la déplacer dans une autre fonction :

def geometry_switch_types: curves + surfaces + {
  "geometry_type::point": "point",
  "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::multi_curve": "multi_curve",
  "geometry_type::multi_surface": "compound_surface"
};

Je n'ai pas voulu baptiser la fonction types, car elle aurait un nom beaucoup trop abstrait. Pour le véritable type geometry, la gestion des cas se raccourcit donc un peu :

cases: (
  ["", "z", "m", "zm"]
  | map(. as $dimension | geometry_switch_types | dimension_suffix($dimension))
  | add + {
  "geometry_type::vector_xy": "point_xy",
  "geometry_type::vector_xyz": "point_xyz",
  "geometry_type::affine_placement_xy": "affine_placement_xy",
  "geometry_type::affine_placement_xyz": "affine_placement_xyz",
  "geometry_type::brep_solid_xyz": "brep_solid_xyz"
})

Pour définir notre géométrie dimensionnée, il va nous falloir prendre en charge ces cinq cas particuliers. On peut faire ça avec de nouveau quelques if :

"geometry_xy\(.)": ({
  seq: ({
    "switch-on": "type",
    cases: (
      (geometry_switch_types | dimension_suffix($dimension))
      + if contains("m") then {} else (
        {
          "geometry_type::vector_xy\(.)": "point_xy\(.)",
          "geometry_type::affine_placement_xy\(.)": "affine_placement_xy\(.)"
        } + if contains("z") then {
          "geometry_type::brep_solid_xy\(.)": "brep_solid_xy\(.)"
        } else {} end
      ) end
    )
  } | wkb_seq)
} | endianize)

On commence par utiliser à nouveau dimension_suffix pour obtenir tous les cas pour les géométries courantes qui acceptent toutes les dimensions. Ensuite, s'il y a la dimension M, que ce soit pour XYM ou XYZM, on n'a aucun cas particulier à ajouter. Mais si cette dimension n'est pas là, on ajoute toujours le vecteur et le placement affine. Et si en plus la dimension Z est bien là, on est dans le seul cas de XYZ, et on ajoute donc le solide à représentation surfacique.

Et avec ce dernier type de géométrie, on arrive enfin au bout de la gestion des dimensions dans le Well-Known Binary ISO.

Script final

#!/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: .
  }
];

def curves: {
  "geometry_type::line_string": "line_string",
  "geometry_type::circular_string": "line_string",
  "geometry_type::compound_curve": "multi_curve",
  "geometry_type::circle": "line_string",
  "geometry_type::geodesic_string": "line_string",
  "geometry_type::elliptical_curve": "elliptical_curve",
  "geometry_type::nurbs_curve": "nurbs_curve",
  "geometry_type::clothoid": "clothoid",
  "geometry_type::spiral_curve": "spiral_curve"
};

def surfaces: {
  "geometry_type::polygon": "polygon",
  "geometry_type::curve_polygon": "multi_curve",
  "geometry_type::polyhedral_surface": "multi_polygon",
  "geometry_type::tin": "tin",
  "geometry_type::triangle": "polygon",
  "geometry_type::compound_surface": "compound_surface"
};

def geometry_switch_types: curves + surfaces + {
  "geometry_type::point": "point",
  "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::multi_curve": "multi_curve",
  "geometry_type::multi_surface": "compound_surface"
};

def dimension_suffix(suffix): with_entries({
  key: "\(.key)_xy\(suffix)",
  value: "\(.value)_xy\(suffix)"
});

def dimension_types: . as $dimension | (
  if contains("m") then [
    {
      id: "start_m",
      type: "f8"
    },
    {
      id: "end_m",
      type: "f8"
    }
  ] else [] end
) as $curve_attributes | {
  "point_xy\(.)": {
    seq: [
      {
        id: "x",
        type: "f8"
      },
      {
        id: "y",
        type: "f8"
      },
      if contains("z") then {
        id: "z",
        type: "f8"
      } else empty end,
      if contains("m") then {
        id: "m",
        type: "f8"
      } else empty end
    ]
  },
  "line_string_xy\(.)": {
    seq: ({ id: "points", type: "point_xy\(.)" } | counted)
  },
  "polygon_xy\(.)": {
    seq: ({ id: "rings", type: "line_string_xy\(.)" } | counted)
  },
  "wkb_point_xy\(.)": ({ seq: ("point_xy\(.)" | wkb_seq) } | endianize),
  "wkb_line_string_xy\(.)": ({ seq: ("line_string_xy\(.)" | wkb_seq) } | endianize),
  "wkb_polygon_xy\(.)": ({ seq: ("polygon_xy\(.)" | wkb_seq) } | endianize),
  "multi_point_xy\(.)": {
    seq: ({ id: "points", type: "wkb_point_xy\(.)" } | counted)
  },
  "multi_line_string_xy\(.)": {
    seq: ({ id: "line_strings", type: "wkb_line_string_xy\(.)" } | counted)
  },
  "multi_polygon_xy\(.)": {
    seq: ({ id: "polygons", type: "wkb_polygon_xy\(.)" } | counted)
  },
  "geometry_collection_xy\(.)": {
    seq: ({ id: "geometries", type: "geometry_xy\(.)" } | counted)
  },
  "tin_xy\(.)": {
    seq: (
      ({ id: "triangles", type: "wkb_polygon_xy\(.)" } | counted("triangle_"))
      + ({ id: "elements", type: "tin_element" } | counted("element_"))
      + [
        {
          id: "max_side_length",
          type: "f8"
        }
      ]
    )
  },
  "elliptical_curve_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m"))"
      },
      {
        id: "u_axis_length",
        type: "f8"
      },
      {
        id: "v_axis_length",
        type: "f8"
      },
      {
        id: "start_angle",
        type: "f8"
      },
      {
        id: "end_angle",
        type: "f8"
      }
    ] + $curve_attributes)
  },
  "nurbs_curve_xy\(.)": {
    seq: (
      [
        {
          id: "degree",
          type: "u1"
        }
      ]
      + ({ id: "control_points", type: "nurbs_point_xy\(rtrimstr("m"))" } | counted("control_point_"))
      + ({ id: "knots", type: "knot" } | counted("knot_"))
      + $curve_attributes
    )
  },
  "clothoid_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m"))"
      },
      {
        id: "scale_factor",
        type: "f8"
      },
      {
        id: "start_distance",
        type: "f8"
      },
      {
        id: "end_distance",
        type: "f8"
      }
    ] + $curve_attributes)
  },
  "spiral_curve_xy\(.)": {
    seq: ([
      {
        id: "reference_location",
        type: "wkb_affine_placement_xy\(rtrimstr("m"))"
      },
      {
        id: "length",
        type: "f8"
      },
      {
        id: "start_distance",
        type: "f8"
      },
      {
        id: "end_distance",
        type: "f8"
      },
      {
        id: "spiral_type",
        type: "wkb_string"
      }
    ] + $curve_attributes)
  },
  "wkb_curve_xy\(.)": ({
    seq: (
      {
        "switch-on": "type",
        cases: (curves | dimension_suffix($dimension))
      } | wkb_seq
    )
  } | endianize),
  "wkb_surface_xy\(.)": ({
    seq: (
      {
        "switch-on": "type",
        cases: (surfaces | dimension_suffix($dimension))
      } | wkb_seq
    )
  } | endianize),
  "multi_curve_xy\(.)": {
    seq: ({ id: "curves", type: "wkb_curve_xy\(.)" } | counted)
  },
  "compound_surface_xy\(.)": {
    seq: ({ id: "surfaces", type: "wkb_surface_xy\(.)" } | counted)
  },
  "geometry_xy\(.)": ({
    seq: ({
      "switch-on": "type",
      cases: (
        (geometry_switch_types | dimension_suffix($dimension))
        + if contains("m") then {} else (
          {
            "geometry_type::vector_xy\(.)": "point_xy\(.)",
            "geometry_type::affine_placement_xy\(.)": "affine_placement_xy\(.)"
          } + if contains("z") then {
            "geometry_type::brep_solid_xy\(.)": "brep_solid_xy\(.)"
          } else {} end
        ) end
      )
    } | wkb_seq)
  } | endianize)
} + if contains("m") then {} else {
  "affine_placement_xy\(.)": {
    seq: (
      [
        {
          id: "location",
          type: "point_xy\(.)"
        }
      ] + ({ id: "reference_directions", type: "point_xy\(.)" } | counted)
    )
  },
  "wkb_affine_placement_xy\(.)": ({ seq: ("affine_placement_xy\(.)" | wkb_seq) } | endianize),
  "nurbs_point_xy\(.)": ({
    seq: [
      {
        id: "point",
        type: "wkb_point_xy\(rtrimstr("m"))"
      },
      # One bit is ignored here due to unclear specification
      {
        id: "weight",
        type: "f8"
      }
    ]
  } | endianize)
} end;

{
  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",
        "8": "circular_string",
        "9": "compound_curve",
        "10": "curve_polygon",
        "11": "multi_curve",
        "12": "multi_surface",
        "15": "polyhedral_surface",
        "16": "tin",
        "17": "triangle",
        "18": "circle",
        "19": "geodesic_string",
        "20": "elliptical_curve",
        "21": "nurbs_curve",
        "22": "clothoid",
        "23": "spiral_curve",
        "24": "compound_surface"
      }
      | to_entries
      | [
        . as $entries
        | [
          [0, ""],
          [1, "z"],
          [2, "m"],
          [3, "zm"]
        ][]
        | . as $dimension
        | $entries[]
        | {
          key: (.key | tonumber + $dimension[0] * 1000 | tostring),
          value: "\(.value)_xy\($dimension[1])"
        }
      ] | from_entries
      | . + {
        "101": "vector_xy",
        "102": "affine_placement_xy",
        "1101": "vector_xyz",
        "1102": "affine_placement_xyz",
        "1025": "brep_solid_xyz",
        "1000001": "circular_string_xy",
        "1000002": "compound_curve_xy",
        "1000003": "curve_polygon_xy",
        "1000004": "multi_curve_xy",
        "1000005": "multi_surface_xy"
      }
    )
  },
  types: {
    geometry: ({
      seq: ({
        "switch-on": "type",
        cases: (
          ["", "z", "m", "zm"]
          | map(. as $dimension | geometry_switch_types | dimension_suffix($dimension))
          | add + {
          "geometry_type::vector_xy": "point_xy",
          "geometry_type::vector_xyz": "point_xyz",
          "geometry_type::affine_placement_xy": "affine_placement_xy",
          "geometry_type::affine_placement_xyz": "affine_placement_xyz",
          "geometry_type::brep_solid_xyz": "brep_solid_xyz"
        })
      } | wkb_seq),
      types: (
        ["", "z", "m", "zm"]
        | map(dimension_types)
        | add + {
          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),
          knot: ({
            seq: [
              {
                id: "value",
                type: "f8"
              },
              {
                id: "multiplicity",
                type: "u1"
              }
            ]
          } | endianize),
          wkb_shell_xyz: ({
            seq: (
              {
                "switch-on": "type",
                cases: ({
                  "geometry_type::polyhedral_surface": "multi_polygon",
                  "geometry_type::compound_surface": "compound_surface"
                } | [dimension_suffix("z"), dimension_suffix("zm")] | add)
              } | wkb_seq
            )
          }),
          brep_solid_xyz: {
            seq: ({ id: "shells", type: "wkb_shell_xyz" } | counted)
          }
        }
      )
    } | endianize)
  }
}

Problèmes connus

Dans l'éventualité où quelqu'un serait assez fou pour reprendre mon script et s'en servir pour lire des fichiers WKB ISO, d'abord, je vous invite à me contacter pour m'indiquer où vous avez réussi à trouver une implémentation réelle du WKB ISO. Ensuite, tenez compte des problèmes suivants, qui ont été survolés au fil des moult parties de cette histoire :

• Ce schéma a été écrit à partir d'un brouillon du standard datant de 2015, et pourrait ne pas pleinement correspondre à la version finalisée ISO 13249-3:2016.
• Ce schéma n'a pas pu être testé aussi bien que les deux autres variantes du format WKB, vu l'absence manifeste d'implémentations du standard.
• Un unique bit est ignoré dans la définition des points NURBS, en raison de son manque de spécification.
• Le schéma généré ne correspond pas parfaitement au guide de style de Kaitai Struct, notamment en raison de limitations avec oq.
• Les géométries vides ne sont pas prises en charge.
• Aucune contrainte sur les valeurs des champs n'est appliquée, puisque la validation n'est pas prise en charge par Kaitai Struct ; par exemple, les triangles sont définis comme des polygones devant avoir strictement trois points, mais ce schéma n'en fait pas la validation.

Conclusion

Après tant de dur labeur, ce script de 463 lignes nous génère un schéma Kaitai Struct de 1643 lignes. Avec tout cet effort de factorisation, on a donc divisé par presque 4 la quantité de code, même si on a probablement multiplié par bien plus que 4 la difficulté de compréhension. À l'attention du moi du futur qui trouvera un bug dans ce script et essaiera de le comprendre pendant des heures : de rien.

Pour en finir une bonne fois pour toutes avec le Well-Known Binary, on s'attaquera la prochaine fois à la troisième et dernière variante ; l'Extended Well-Known Binary, la variante inventée par PostGIS, non standardisée, et pourtant la plus couramment utilisée.

Commentaires

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