Construire un polygone sur une zone accessible

Je travaille actuellement dans le domaine des isochrones et des algorithmes sous-jacents. Ce qui pose problème maintenant, ce n'est plus le calcul de l'isochrone elle-même, mais la visualisation des résultats.
Le résultat de mon algorithme isochrone sont des points et des bords. En fait, j'ai une solution qui fonctionne, mais pour 3873 bords et pour 1529 nœuds, les choses semblent prendre une éternité (environ 2,0 secondes sur mon ordinateur portable Lenovo T440s qui contient un processeur Core i7 2015 et un SSD assez rapide). Au lieu de quelques secondes, je veux quelque chose de plus comme msec :-).

Peut-être que quelqu'un peut m'aider à réduire le temps de calcul nécessaire pour construire les polygones qui visualisent les zones accessibles.

Mais attendez ... tout d'abord!
Voici une visualisation des bords que je suis le résultat du calcul de mon isochrone: Ces bords sont stockés dans une table de base de données PostGIS et sont de simples chaînes de lignes.

Ce que je veux montrer à l'utilisateur ressemble à ceci: Notez les zones déconnectées à l'extrême sud et à l'est de l'image. Ceux-ci doivent être dessinés comme des zones distinctes (donc aucune fusion n'est autorisée ici :-))

Actuellement, j'utilise cette requête:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

J'ai déjà fait des expériences et j'ai également lu beaucoup de documentation, mais je ne peux tout simplement pas trouver une meilleure solution.
À mes yeux, le gros problème est l'utilisation de ST_Union (comme indiqué dans la documentation, cette fonction peut être lente). La chose très intéressante est que le remplacer par ST_Collect semble ralentir le calcul de ST_Buffer afin que la requête suivante prenne encore plus de temps, bien qu'elle ne remplisse pas les zones entre les bords (elle crée seulement un tampon autour des lignes ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

Cela prend environ 3,8 secondes sur mon système (soit près de deux fois le temps). Ma première conclusion à partir de ce petit benchmark est que ST_Buffer devient incroyablement lent en ce qui concerne MultiLineStrings (encore plus lent que lors de la création de tampons pour chaque ligne et de la fusion des tampons - ce qui à mes yeux est juste bizarre)

J'ai également essayé d'utiliser des formes alpha (en utilisant l'implémentation de pgRouting), mais comme il n'y a pas de valeur alpha à définir (et en fait, je ne voudrais pas vraiment maintenant à quelle valeur définir une telle valeur), j'obtiens juste un grand polygone ( je perdrais donc les régions de l'extrême sud et de l'est en tant que régions distinctes, ce qui n'est pas ce que je veux).
Aussi ST_Polygonize (qui était la première chose qui m'est venue à l'esprit) n'a produit aucun résultat utilisable, mais peut-être que j'ai raté quelque chose ici ...

Existe-t-il un meilleur moyen de créer la zone affichée dans PostGIS? Peut-être aussi en utilisant du code java (jts) ou du code javascript côté client (jsts)? En fait, je pourrais vivre en perdant certains détails tant que les zones affichées dans mon résultat restent séparées et que le calcul devient (beaucoup) plus rapide.

Mis à part la sérialisation GeoJSON, ce qui suit prend environ 6,3 secondes sur mon ordinateur portable:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

En regardant les données dans OpenJUMP, j'ai remarqué pas mal de détails dans les segments de rue, par rapport au niveau de détail souhaité dans la sortie. Il semble que même une simplification à la volée de ces lignes puisse produire une grande accélération dans PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

ce qui ramène les choses à 2,3 secondes. Je pensais que je pourrais peut-être faire mieux en stockant la géométrie généralisée dans une colonne séparée, au lieu de la calculer à la volée, mais cela n'a en fait fourni aucun avantage supplémentaire.

En fonction de la quantité de code que vous êtes prêt à écrire, vous pouvez certainement faire mieux en Java, si rien d'autre, car vous pouvez profiter de plusieurs cœurs. (Pour ce que ça vaut, JTS effectue l'opération ci-dessus en 2,8 secondes). Une approche pourrait être d'étendre CascadedPolygonUnionpour que certaines opérations syndicales se déroulent en parallèle. (mise à jour - voici un ParallelCascadedPolygonUnion )

J'ai remarqué dans les exemples de données que les bords sont stockés avec des références à leurs nœuds de début et de fin, c'est-à-dire que vous avez un graphique pré-construit. Je soupçonne que vous pouvez générer ces polygones beaucoup plus rapidement si vous travaillez à partir du graphique au lieu d'utiliser des opérations de géométrie génériques. Par exemple, je pense que vous pourriez donc quelque chose comme ça:

1. identifier les composants connectés du graphique
2. pour chaque composant connecté, trouvez le nœud avec la coordonnée X minimale (garanti d'être à l'extérieur du composant)
3. parcourez les bords du composant, en tournant toujours à gauche (ou à droite) lorsque cela est possible. Cela vous donnera l'anneau extérieur de chaque composant.
4. polygoniser l'anneau extérieur et le tampon de manière appropriée.