Dessiner une carte topographique

Question

Je travaille sur un projet de visualisation de données continues bidimensionnelles. C'est le genre de chose que vous pourriez utiliser pour étudier des données d'altitude ou des modèles de température sur une carte 2D. À la base, c’est vraiment une façon d’aplatir les 3 dimensions en deux dimensions plus couleurs. Dans mon domaine d'étude particulier, je ne travaille pas avec des données d'élévation géographique, mais c'est une bonne métaphore. Je vais donc m'en tenir à cela tout au long de cet article.

Quoi qu’il en soit, à ce stade, j’ai une "couleur continue". rendu que je suis très heureux avec:

Le dégradé est la roue chromatique standard, où les pixels rouges indiquent les coordonnées avec des valeurs élevées et les pixels violets indiquent les valeurs faibles.

La structure de données sous-jacente utilise des algorithmes d’interpolation très intelligents (si j’en dis moi-même) pour permettre de faire un zoom arbitraire et profond sur les détails de la carte.

À ce stade, je souhaite dessiner des courbes de niveau topographiques (à l’aide de courbes de Bézier quadratiques), mais je n’ai trouvé aucun ouvrage de qualité décrivant des algorithmes efficaces permettant de rechercher ces courbes.

Pour vous donner une idée de ce à quoi je pense, voici l'implémentation d'un homme pauvre (où le moteur de rendu utilise simplement une valeur RVB noire chaque fois qu'il rencontre un pixel qui intersecte une ligne de contour):

Il existe plusieurs problèmes avec cette approche, cependant:

• Les zones du graphique avec une pente plus raide donnent des lignes topo plus minces (et souvent brisées). Idéalement, toutes les lignes topo devraient être continues.

• Les zones du graphique avec une pente plus plate donnent des lignes topo plus larges (et souvent des régions entières de noirceur, en particulier au périmètre extérieur de la région de rendu).

Je cherche donc une approche de dessin vectoriel pour obtenir ces belles courbes parfaites de 1 pixel d'épaisseur. La structure de base de l’algorithme devra inclure les étapes suivantes:

1. À chaque élévation discrète sur laquelle je veux tracer une ligne topo, trouvez un ensemble de coordonnées où l'altitude à cette coordonnée est extrêmement proche (compte tenu d'une valeur epsilon arbitraire) par rapport à l'altitude souhaitée.

2. Éliminez les points redondants. Par exemple, si trois points sont parfaitement alignés, le point central est redondant car il peut être supprimé sans modifier la forme de la courbe. De même, avec les courbes de Bézier, il est souvent possible d’éliminer certains points d’ancrage en ajustant la position des points de contrôle adjacents.

3. Assemblez les points restants en une séquence, de sorte que chaque segment compris entre deux points se rapproche d'une trajectoire neutre en élévation et que deux segments de ligne ne se croisent jamais. Chaque séquence de points doit créer un polygone fermé ou intersecter le cadre de sélection de la région de rendu.

4. Pour chaque sommet, recherchez une paire de points de contrôle telle que la courbe résultante présente une erreur minimale par rapport aux points redondants éliminés à l'étape 2.

5. Assurez-vous que toutes les caractéristiques de la topographie visibles à l'échelle de rendu actuelle sont représentées par les lignes de topo appropriées. Par exemple, si les données contiennent un pic à haute altitude, mais avec un diamètre extrêmement petit, les lignes topo doivent toujours être tracées. Les entités verticales ne doivent être ignorées que si leur diamètre est inférieur à la granularité de rendu globale de l'image.

Mais même avec ces contraintes, je peux toujours penser à plusieurs heuristiques différentes pour trouver les lignes:

• Trouvez le point haut dans la boîte de rendu. À partir de ce point culminant, empruntez plusieurs trajectoires différentes. Chaque fois que la ligne transversale traverse un seuil d'altitude, ajoutez ce point à un compartiment spécifique à l'altitude. Lorsque le chemin de traverse atteint un minimum local, changez de cap et montez.

• Effectuez une traversée en haute résolution le long du cadre de délimitation rectangulaire de la région de rendu. À chaque seuil d'élévation (et aux points d'inflexion, là où la pente inverse la direction), ajoutez ces points à un godet spécifique à l'altitude. Une fois la traversée des limites terminée, commencez à tracer vers l'intérieur à partir des points limites de ces compartiments.

• Parcourez toute la région de rendu en prenant une mesure d'altitude à intervalles réguliers clairsemés. Pour chaque mesure, utilisez la proximité d'un seuil d'élévation comme mécanisme pour décider de prendre ou non une mesure interpolée de ses voisins. L'utilisation de cette technique fournirait de meilleures garanties de couverture sur toute la région de rendu, mais il serait difficile d'assembler les points résultants dans un ordre logique pour la construction de chemins.

Voilà donc certaines de mes pensées ...

Avant de me plonger dans une implémentation, je voulais voir si quelqu'un d'autre sur StackOverflow avait l'expérience de ce type de problème et pouvait fournir des indications pour une implémentation précise et efficace.

Modifier:

Je suis particulièrement intéressé par le " Gradient " suggestion faite par ellisbben. Et ma structure de données centrale (en ignorant certains des raccourcis d’interpolation d’optimisation) peut être représentée par la somme d’un ensemble de fonctions gaussiennes 2D, ce qui est totalement différentiable.

Je suppose qu’il me faut une structure de données pour représenter une pente en trois dimensions, ainsi qu’une fonction permettant de calculer ce vecteur de pente pour un point quelconque. De mémoire, je ne sais pas comment faire cela (bien que cela semble être une tâche facile), mais si vous avez un lien expliquant les calculs, je vous en serais très reconnaissant!

UPDATE:

Grâce aux excellentes contributions d’ellisbben et Azim, je peux maintenant calculer l’angle de contour pour tout point quelconque du champ. Tracer les vraies lignes du topo suivra sous peu!

Voici les rendus mis à jour, avec et sans le rendu topo basé sur les rasters ghetto que j'ai utilisé. Chaque image comprend un millier de points d'échantillonnage aléatoires, représentés par des points rouges. L'angle de contour en ce point est représenté par une ligne blanche. Dans certains cas, aucune pente n’a pu être mesurée au point donné (sur la base de la granularité de l’interpolation); le point rouge apparaît donc sans ligne de contour correspondante.

Profitez!

(REMARQUE: ces rendus utilisent une topographie de surface différente de celle des précédents, car je génère aléatoirement les structures de données à chaque itération, alors que je suis en train de prototyper, mais la méthode de rendu principale est la même. Je suis sûr que vous avez l’idée.)

Voilà un fait amusant: à la droite de ces rendus, vous verrez une série de courbes étranges aux angles horizontaux et verticaux parfaits. Ce sont des artefacts du processus d'interpolation, qui utilise une grille d'interpolateurs pour réduire le nombre de calculs (d'environ 500%) nécessaires à l'exécution des opérations de rendu principales. Toutes ces courbes étranges apparaissent à la frontière entre deux cellules de la grille de l’interpolateur.

Heureusement, ces artefacts importent peu. Bien que les artefacts soient détectables lors du calcul de la pente, le rendu final ne les remarquera pas, car il fonctionne à une résolution différente.

MISE À JOUR DE NOUVEAU:

Aaaaaaaa et comme dernière indulgence avant de m'endormir, voici une autre paire de rendus, l'un à la vieille école "couleur continue". style, et un avec 20 000 échantillons dégradés. Dans cet ensemble de rendus, j'ai éliminé le point rouge pour les échantillons ponctuels, car il encombrerait inutilement l'image.

Ici, vous pouvez vraiment voir les artefacts d'interpolation auxquels j'ai fait référence précédemment, grâce à la structure de grille de la collection d'interpolateurs. Je tiens à souligner que ces artefacts seront complètement invisibles lors du rendu final du contour (car la différence de magnitude entre deux cellules d'interpolateur adjacentes est inférieure à la profondeur de bits de l'image rendue).

Bon appétit !!

Answer 1

Le dégradé est un opérateur mathématique qui peut vous aider.

Si vous pouvez transformer votre interpolation en une fonction différentiable, la pente de la hauteur sera toujours dirigée dans la direction de la plus forte montée. Toutes les courbes de hauteur égale sont perpendiculaires au gradient de hauteur évalué en ce point.

Votre idée de partir du point le plus élevé est judicieuse, mais risque de manquer des fonctionnalités s'il y a plus d'un maximum local.

Je suggérerais

1. choisissez les valeurs de hauteur auxquelles vous allez tracer des lignes
2. créez un ensemble de points sur une grille fine et régulièrement espacée, puis parcourez chaque point par petites étapes dans la direction du dégradé vers la hauteur la plus proche à laquelle vous souhaitez tracer une ligne
3. créez des courbes en incrustant chaque point perpendiculairement au dégradé; éliminez les points en excès en supprimant un point lorsqu'une autre courbe s'en approche trop - mais pour éviter de détruire le centre du sablier comme des figures, vous devrez peut-être vérifier l'angle entre le vecteur orienté perpendiculairement à la pente pour les deux points. (Quand je dis orienté, je veux dire, assurez-vous que l'angle entre le gradient et la valeur perpendiculaire que vous calculez est toujours de 90 degrés dans la même direction.)

Answer 2

Vous pouvez également utiliser l’algorithme carrés de défilement , bien que vous peut vouloir lisser les résultats si vous utilisez une grille grossière.

Les courbes topographiques que vous souhaitez tracer sont les isosurfaces d'un champ scalaire sur 2 dimensions. Pour les isosurfaces en 3 dimensions, il existe l'algorithme des cubes défilés .

Answer 3

En réponse à votre commentaire à @erickson et à votre question sur le calcul du gradient de votre fonction. Au lieu de calculer les dérivées de votre fonction de 300 termes, vous pouvez procéder à une différenciation numérique comme suit.

Étant donné un point [x, y] dans votre image, vous pouvez calculer le gradient (direction de la plus forte pente)

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy) 

où dx et dy pourraient être l’espacement dans votre grille. La ligne de contour sera perpendiculaire au dégradé. Donc, pour obtenir la direction du contour, c, nous pouvons multiplier g = [v, w] par la matrice, A = [0 -1, 1 0] donnant

c = [-w,v]

Answer 4

J'ai moi-même voulu quelque chose comme ça, mais je n'ai pas trouvé de solution vectorielle.

Cependant, une solution basée sur les images raster n’est pas si mauvaise, surtout si vos données sont basées sur les images raster. Si vos données sont également vectorielles (en d’autres termes, si vous avez un modèle 3D de votre surface), vous devriez pouvoir effectuer de véritables calculs pour trouver les courbes d’intersection avec des plans horizontaux à différentes altitudes.

Pour une approche basée sur le raster, je regarde chaque paire de pixels voisins. Si l'un est au-dessus d'un niveau de contour et l'autre au-dessous, il est évident qu'une ligne de contour les sépare. Le truc que j’avais l'habitude d'anti-aliaser la ligne de contour consiste à mélanger la couleur de la ligne de contour en deux pixels, proportionnelle à leur proximité avec la ligne de contour idéalisée.

Peut-être que quelques exemples aideront. Supposons que le pixel actuel se trouve à une "altitude". de 12 pieds, un voisin est à une altitude de 8 pieds, et les lignes de contour sont tous les 10 pieds. Ensuite, il y a une ligne de contour à mi-chemin entre; peignez le pixel actuel avec la couleur de la ligne de contour à 50% d'opacité. Un autre pixel est à 11 pieds et a un voisin à 6 pieds. Colore le pixel actuel avec une opacité de 80%.

alpha = (contour - neighbor) / (current - neighbor)

Malheureusement, je n'ai pas le code à portée de main et il y a peut-être un peu plus que cela (je me souviens vaguement d'avoir aussi regardé les voisins en diagonale et d'ajusté avec sqrt (2) / 2 ). J'espère que cela suffit pour vous donner l'essentiel.

Answer 5

Je me suis dit que ce que vous essayez de faire serait assez facile à faire dans MATLAB, en utilisant la fonction de contour. Vous pouvez par exemple effectuer un post-traitement assez simple des approximations basse densité de vos contours.

Heureusement, GNU Octave, un clone MATLAB, implémente les différentes fonctions de traçage de contours. Vous pourriez examiner ce code pour trouver un algorithme et une implémentation mathématiquement fiables. Ou bien, vous pourriez simplement être en mesure de décharger le traitement sur Octave. Consultez la page sur en interface avec d'autres langues pour voir si cela serait plus facile.

Divulgation: Je n'ai pas beaucoup utilisé Octave, et je n'ai pas encore testé son tracé de courbes de niveau. Cependant, grâce à mon expérience avec MATLAB, je peux dire que cela vous donnera pratiquement tout ce que vous demandez en quelques lignes de code, à condition que vos données soient stockées dans MATLAB.

De même, félicitations pour avoir réalisé un complot très sinueux de type VanGough-esque.

Answer 6

Je vérifie toujours des endroits tels que http://mathworld.wolfram.com avant de me lancer à fond :)

Peut-être que leur section courbes pourrait vous aider? Ou peut-être l'entrée sur les cartes .

Answer 7

comparez ce que vous avez rendu avec une carte topographique du monde réel - elles me semblent identiques! je ne changerais rien du tout ...

Answer 8

Ecrivez les données sous forme de fichier HGT (très simple format numérique de données d'élévation utilisé par USGS) et utilisez l'outil gdal_contour gratuit et gratuit pour créer contours. Cela fonctionne très bien pour les cartes terrestres, la contrainte étant que les points de données sont des nombres signés 16 bits, ce qui correspond très bien à la plage de hauteur terrestre en mètres, mais peut ne pas être suffisant pour vos données, ce qui, je suppose, n'est pas un carte du terrain actuel - bien que vous mentionniez des cartes de terrain.

Answer 9

Je recommande l'approche CONREC :

• Créer une liste de segments de ligne vide
• Divisez vos données en carrés de grille réguliers
• Pour chaque carré de la grille, divisez-le en 4 triangles:
  • Pour chaque triangle, gérez les cas (a à j):
    • Si un segment de ligne traverse l'un des cas suivants:
      • Calculer ses points de terminaison
      • Stockez le segment de ligne dans la liste
• Tracez chaque segment de ligne dans la liste de segments

Si les lignes sont trop irrégulières, utilisez une grille plus petite. Si les lignes sont suffisamment lisses et que l'algorithme prend trop de temps, utilisez une grille plus grande.