town
envs
brainshitWell-Known Binary ISO avec Kaitai Struct, partie 3
Lucidiot —
Informatique —
2022-02-23
Quelques derniers types de géométries, en préparation pour le bouquet final.
Dans ce nouvel opus d'une série qui ne sera probablement pas suivie par grand monde, on va enfin terminer de traiter presque tous les types de géométries, et on va commencer à nettoyer notre script. Cet article sera un peu moins lourd que les autres puisqu'il contient surtout les quelques bribes restantes avant de traiter le sujet qu'on verra dans une quatrième et dernière partie : la gestion des quatre dimensions.
Ensemble de courbes
L'ensemble de courbes est l'équivalent de l'ensemble de lignes brisées, mais généralisé à toutes les courbes. Sachez qu'une ligne brisée est redéfinie ici comme étant une courbe, avec la particularité d'une interpolation linéaire entre ses points. On peut donc ranger dans un ensemble de courbes des lignes brisées, des spirales, des cercles, etc. sans problèmes.
L'ensemble de courbes a la même structure que les autres ensembles de points, lignes brisées ou polygones qu'on a pu voir précédemment ; on va donc simplement définir un nouveau switch-on pour restreindre les types autorisés à ceux définissant des courbes, et construire l'ensemble de courbes exactement comme on a construit les autres ensembles.
enums: {
geometry_type: {
# ...
"11": "multi_curve",
"1000004": "multi_curve"
}
}
# ...
types: {
geometry: {
seq: ({
switch-on: "type",
cases: {
# ...
"geometry_type::multi_curve": "multi_curve"
}
} | wkb_seq),
types: {
wkb_curve: ({
seq: (
{
"switch-on": "type",
cases: {
"geometry_type::line_string": "line_string",
"geometry_type::circular_string": "line_string",
"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"
}
} | wkb_seq
)
} | endianize),
multi_curve: {
seq: ({ id: "curves", type: "wkb_curve" } | counted)
}
}
}
}
Courbe composée
La courbe composée est une courbe composée de plusieurs courbes. Vous ne vous y attendiez pas, n'est-ce pas ?
Elle a exactement la même définition en WKB que l'ensemble de courbes qu'on vient de voir, mais avec la différence que le point final d'une courbe est censé être le point de départ de la suivante, afin d'assurer la continuité de la courbe composée. Ce n'est pas une contrainte qu'on peut vérifier simplement vu la complexité de certaines courbes, et Kaitai Struct ne prend de toute façon pas en charge les assertions pour l'instant, donc on va ignorer ça et juste réutiliser le type multi_curve qu'on vient tout juste de déclarer.
enums: {
geometry_type: {
# ...
"9": "compound_curve",
"1000002": "compound_curve"
}
}
# ...
types: {
geometry: {
seq: ({
switch-on: "type",
cases: {
# ...
"geometry_type::compound_curve": "multi_curve"
}
} | wkb_seq),
types: {
wkb_curve: ({
seq: (
{
"switch-on": "type",
cases: {
# ...
"geometry_type::compound_curve": "multi_curve"
}
} | wkb_seq
)
} | endianize)
}
}
}
On notera qu'il est tout à fait autorisé d'avoir une courbe composée composée de courbes composées.
Polygone courbe
Le polygone courbe est un polygone dont les anneaux sont des courbes composées. Je ne peux plus parler alors d'anneaux linéaires comme je l'ai parfois fait auparavant ; le polygone courbe est une généralisation du polygone permettant des anneaux qui ne sont plus forcément linéaires. Il se définit concrètement par une liste de courbes, exactement comme l'ensemble de courbes et la courbe composée, et a la contrainte que les courbes doivent se terminer là où elles commencent, pour pouvoir former des anneaux. Là encore, on ne peut pas tester cette contrainte comme ça, donc on va juste réutiliser le type existant.
enums: {
geometry_type: {
# ...
"10": "curve_polygon",
"1000003": "curve_polygon"
}
}
# ...
types: {
geometry: {
seq: ({
switch-on: "type",
cases: {
# ...
"geometry_type::curve_polygon": "multi_curve"
}
} | wkb_seq)
}
}
Surface composée
La surface composée est la même généralisation que pour la courbe composée, mais pour des polygones. Une surface peut être un polygone, un polygone courbe, un triangle, un réseau triangulaire irrégulier, une surface polyédrale, ou une surface composée. Avec la surface composée, toutes les surfaces doivent se joindre par des bords communs et doivent pouvoir donc former une seule surface commune quand elles sont considérées ensemble.
enums: {
geometry_type: {
# ...
"24": "compound_surface"
}
}
# ...
types: {
geometry: {
seq: ({
switch-on: "type",
cases: {
# ...
"geometry_type::compound_surface": "compound_surface"
}
} | wkb_seq),
types: {
wkb_surface: ({
seq: (
{
"switch-on": "type",
cases: {
"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"
}
} | wkb_seq
)
} | endianize),
compound_surface: {
seq: ({ id: "surfaces", type: "wkb_surface" } | counted)
}
}
}
}
Ensemble de surfaces
L'ensemble de surfaces est la même chose que la surface composée, à la différence qu'on peut faire n'importe quoi avec. On peut réutiliser le type compound_surface directement :
enums: {
geometry_type: {
# ...
"12": "multi_surface",
"1000005": "multi_surface"
}
}
# ...
types: {
geometry: {
seq: ({
switch-on: "type",
cases: {
# ...
"geometry_type::multi_surface": "compound_surface"
}
} | wkb_seq)
}
}
Déduplication de switch-on
Le but du script jq est de factoriser, de pouvoir construire un schéma Kaitai Struct qui serait autrement très fastidieux à écrire et très répétitif. Une répétition que j'ai pu constater ici est la présence des quelques switch-on qu'on a rajouté notamment pour la gestion des ensembles de courbes ou de surfaces. On pourrait rassembler ces cas particuliers de surfaces et de courbes avec les autres types qui ne sont pas associés à ceux-ci, pour avoir un switch-on un peu moins long sur le type général qu'est geometry.
Concrètement, juste avant qu'on ne commence l'énorme objet qui décrit notre schéma, on va définir quelques variables :
{
"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"
} as $curves
| {
"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"
} as $surfaces
| {
meta: {
id: "wkb_iso",
title: "ISO Well-Known Binary"
# ...
}
# ...
}
Ces deux variables $curves et $surfaces correspondent à toutes les courbes prises en charge par les ensembles de courbes et courbes composées, et toutes les surfaces des ensembles de surfaces et surfaces composées. On peut donc les réutiliser dans leurs types respectifs, qu'on a défini quelques paragraphes plus haut :
wkb_curve: ({
seq: (
{
"switch-on": "type",
cases: $curves
} | wkb_seq
)
} | endianize),
wkb_surface: ({
seq: (
{
"switch-on": "type",
cases: $surfaces
} | wkb_seq
)
} | endianize)
Enfin, et c'est là où on va économiser quelques lignes de répétition, on va les utiliser dans le switch-on du type geometry :
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",
"geometry_type::vector": "point",
"geometry_type::affine_placement": "affine_placement"
})
} | wkb_seq)
# ...
}
Gestion des géométries vides
Les géométries vides sont représentées en WKB standard de façon plus compliquée à gérer que le WKB standard, et encore plus compliqué que le WKT.
Ce n'était pas très bien documenté pour le WKB standard, mais quelques tests avec des implémentations existantes m'ont montré que les points vides (POINT EMPTY) sont représentés en tant que des points ayant des valeurs qui ne sont pas des nombres. Avec les nombres à virgule flottante de la norme IEEE 754 qu'on utilise, il existe des cas particuliers qui permettent de représenter notamment les infinis positifs et négatifs, mais aussi « pas un nombre », en anglais « not a number » et abrégé en NaN. Cette valeur particulière est généralement renvoyée quand des calculs partent complètement en vrille. Dans notre cas, NaN va signifier qu'il n'y a pas de coordonnées définies pour le point, donc qu'il est vide.
Pour toutes les autres géométries du WKB standard, qui sont toutes des listes plus ou moins complexes de points, le nombre d'éléments de la liste est toujours défini à zéro, donnant donc un ensemble vide.
Dans le WKB ISO, il n'est plus possible de se reposer seulement sur ce comportement, notamment parce que toutes les géométries ne sont pas forcément des listes. Je pense notamment à quasiment tous les types de courbes, qui ont des métadonnées supplémentaires comme un degré de polynôme, un placement affine, etc. Je suppose donc que c'est la raison pour laquelle les géométries vides sont représentées de façon bien moins pratique pour nous. Ce n'est qu'une supposition : aucune justification n'est fournie ni par OGC ni par ISO sur ces différences, et il n'existe à ma connaissance aucune implémentation du WKB ISO en lecture ou en écriture qui me permettrait de tester sur le terrain les géométries vides.
Les géométries vides sont abordées de façon assez sommaire et peu accessible dans le standard. Pour voir comment elles fonctionnent concrètement, il faut se référer à la fois à plusieurs pages de grammaire ABNF et à une liste comprenant plus de 200 éléments numérotés de a) à fx) et comprenant beaucoup de sous-listes et de sous-sous-listes. Voilà à quoi ressemble la grammaire qui définit un simple point, une fois qu'on la trouvée dans la page et qu'on l'extrait de tout ce mélange :
<point binary representation> ::= <byte order> <wkbpoint> [ <wkbpoint binary> ]
<wkbpoint> ::= <uint32>
<wkbpoint binary> ::= <wkbx> <wkby>
<wkbx> ::= <double>
<wkby> ::= <double>
On retrouve tous les champs maintenant assez habituels : le boutisme, l'identifiant du point, et les coordonnées X et Y. L'identifiant du point est défini ici seulement comme un uint32, un nombre entier non signé à 32 bits, et un tableau 50 pages plus loin indique sa valeur exacte.
La partie la plus importante de cette grammaire pour cette section, c'est [ <wkbpoint binary> ]. On ne fait pas que mettre des coordonnées X et Y ; avec des crochets, on rend le tout complètement optionnel.
La très longue liste de règles supplémentaires à appliquer pour lire du WKB contient des instructions pour interpréter un point comme étant vide, indiquant que si le <wkbpoint binary> est manquant, alors le point est considéré vide.
i) If
<point binary representation>immediately contains a<wkbpoint binary>, then<point binary representation>is the well-known binary representation for an ST_Point value that is produced by<wkbpoint binary>. ii) Otherwise,<point binary representation>produces an empty set of type ST_Point.—ISO/IEC 13249-3:2016 (2015 draft), 5.1.68 <well-known binary representation>, p. 218
Le problème dans cette histoire, c'est que Kaitai Struct ne prend pas du tout en charge de telles situations. Il n'existe pas de propriété qui permettrait d'indiquer qu'un champ est entièrement optionnel, notamment parce que ça rendrait la lecture d'un fichier binaire très complexe. S'il y a par exemple une collection de géométries, il faut deviner si la représentation binaire ressemble à ce qui pourrait être la suite de la géométrie actuelle, ou le début de la géométrie suivante. Cette complexité est peut-être une des raisons pour lesquelles le WKB ISO n'est implémenté nulle part !
Nous n'allons donc rien faire en ce qui concerne les géométries vides. Tant pis…
Script actuel
Script jq générant un schéma Kaitai Struct pour le WKB ISO, partie 3
#!/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: .
}
];
{
"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"
} as $curves
| {
"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"
} as $surfaces
| {
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",
"101": "vector",
"102": "affine_placement",
"1000001": "circular_string",
"1000002": "compound_curve",
"1000003": "curve_polygon",
"1000004": "multi_curve",
"1000005": "multi_surface"
}
},
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",
"geometry_type::vector": "point",
"geometry_type::affine_placement": "affine_placement"
})
} | 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"
}
]
)
},
affine_placement: {
seq: (
[
{
id: "location",
type: "point"
}
] + ({ id: "reference_directions", type: "point" } | counted)
)
},
wkb_affine_placement: ({ seq: ("affine_placement" | wkb_seq) } | endianize),
elliptical_curve: {
seq: [
{
id: "reference_location",
type: "wkb_affine_placement"
},
{
id: "u_axis_length",
type: "f8"
},
{
id: "v_axis_length",
type: "f8"
},
{
id: "start_angle",
type: "f8"
},
{
id: "end_angle",
type: "f8"
}
]
},
nurbs_point: ({
seq: [
{
id: "point",
type: "wkb_point"
},
# One bit is ignored here due to unclear specification
{
id: "weight",
type: "f8"
}
]
} | endianize),
knot: ({
seq: [
{
id: "value",
type: "f8"
},
{
id: "multiplicity",
type: "u1"
}
]
} | endianize),
nurbs_curve: {
seq: (
[
{
id: "degree",
type: "u1"
}
]
+ ({ id: "control_points", type: "nurbs_point" } | counted("control_point_"))
+ ({ id: "knots", type: "knot" } | counted("knot_"))
)
},
clothoid: {
seq: [
{
id: "reference_location",
type: "wkb_affine_placement"
},
{
id: "scale_factor",
type: "f8"
},
{
id: "start_distance",
type: "f8"
},
{
id: "end_distance",
type: "f8"
}
]
},
spiral_curve: {
seq: [
{
id: "reference_location",
type: "wkb_affine_placement"
},
{
id: "length",
type: "f8"
},
{
id: "start_distance",
type: "f8"
},
{
id: "end_distance",
type: "f8"
},
{
id: "spiral_type",
type: "wkb_string"
}
]
},
wkb_curve: ({
seq: (
{
"switch-on": "type",
cases: $curves
} | wkb_seq
)
} | endianize),
wkb_surface: ({
seq: (
{
"switch-on": "type",
cases: $surfaces
} | wkb_seq
)
} | endianize),
multi_curve: {
seq: ({ id: "curves", type: "wkb_curve" } | counted)
},
compound_surface: {
seq: ({ id: "surfaces", type: "wkb_surface" } | counted)
}
}
} | endianize)
}
}
# vim: et sw=2 ts=2Conclusion
Il ne reste plus qu'une dernière étape pour arriver au bout de la pire des 3 variantes du WKB : la gestion de trois et quatre dimensions. Il va nous falloir encore ajouter un niveau d'abstraction supplémentaire dans ce script ! Viendra ensuite la dernière variante, le EWKB, qui devrait être déjà bien plus simple.
Commentaires
Il n'y a pour l'instant aucun commentaire. Soyez le premier !