Suite

Trouver le chemin le plus court tout en évitant les entités surfaciques

Trouver le chemin le plus court tout en évitant les entités surfaciques


Je développe une extension à ArcMap où j'ai un ensemble d'entités surfaciques statiques et concaves et j'essaie de trouver le chemin le plus court entre 2 points sans traverser aucun des polygones.

Existe-t-il un algorithme pour faire cela ?


Si vous disposez de l'extension Spatial Analyst et que cela ne vous dérange pas de travailler avec des représentations raster de vos données, vous pouvez utiliser Cost Path Analysis. Les détails et d'autres options peuvent être trouvés dans la rubrique d'aide et la barre latérale associée à l'aide.


Une fois, j'ai implémenté un algorithme qui calcule un polygone qui inclut l'aire d'un plan (avec des obstacles polygonaux) qui peut être atteint à une certaine distance. Ce qui m'a le plus aidé, c'est de réaliser que problèmes de chemin le plus court dans un avion en évitant les obstacles peuvent être considérés comme des problèmes de visibilité. Bien qu'ils ne soient pas souvent abordés dans un contexte SIG, les problèmes de visibilité sont très répandus et bien documentés en géométrie computationnelle.

Vous pouvez adopter deux approches pour résoudre le problème :

  1. Vous pouvez soit trouver le chemin le plus court en utilisant uniquement les polygones pertinents en utilisant un index spatial comme un R-Tree pour vos polygones afin d'accélérer les choses.

  2. Vous pouvez créer un graphique sur tous vos polygones, puis trouver le chemin le plus court dans ce graphique.

L'approche 1. est meilleure si vous ne pouvez pas conserver l'état interne entre les moments où votre algorithme est utilisé. Si vous devez calculer beaucoup de chemins les plus courts et que les polygones restent les mêmes, approchez-vous de 2. c'est mieux.

L'approche 1. est ce que j'ai fait pour mon algorithme. Ce que j'ai fait c'est en gros ça :

  1. Tracez une ligne entre le point de départ et le point d'arrivée.
  2. Voir s'il coupe l'intérieur d'au moins un polygone. S'il ne se croise pas, c'est votre chemin le plus court.
  3. S'il se croise, prenez le segment d'intersection du polygone qui est le plus proche du point de départ.
  4. Itérer à travers les sommets du polygone vers la gauche et vers la droite jusqu'à ce qu'une ligne entre le sommet et l'extrémité n'intersecte pas l'intérieur du polygone ou jusqu'à ce que la ligne directe entre le sommet intersecte avec un autre polygone. Si vous croisez un autre polygone, passez à l'étape 2 avec ce polygone. Sinon, passez à l'étape 1 et souvenez-vous de la longueur entre le point de départ et le sommet qui est maintenant le nouveau point de départ.

L'approche 2. est probablement mieux adaptée au problème décrit ici et devrait être plus facile à mettre en œuvre.

Le graphique dont vous avez besoin pour le routage dans un plan avec des polygones comme obstacles est le graphique de visibilité. La méthode par force brute pour construire cela est assez simple. Vous calculez d'abord l'enveloppe convexe de vos polygones. Les sommets qui ne se trouvent pas sur l'enveloppe convexe n'ont pas besoin de faire partie du graphique de visibilité. Les sommets sur l'enveloppe convexe sont les nœuds du graphe de visibilité. Ensuite, vous tracez une ligne entre toutes les paires de sommets et voyez si cette ligne coupe l'intérieur d'un polygone. Si la ligne ne coupe pas l'un des polygones, il s'agit d'une arête dans le graphique de visibilité.

Vous devez ajouter votre point de départ et d'arrivée au graphique de visibilité. Ensuite, vous pouvez utiliser un algorithme de plus court chemin pondéré à source unique. L'algorithme de Dijkstra fera parfaitement l'affaire. Si vous vous attendez à de nombreuses requêtes sur le chemin le plus court, cela peut valoir la peine d'utiliser un algorithme qui calcule tous les chemins les plus courts et calcule à l'avance les chemins les plus courts entre toutes les paires de nœuds dans le graphique de visibilité.

Bien entendu, le graphe de visibilité peut être utilisé avec des outils de routage existants, vous n'avez donc pas à implémenter l'algorithme du chemin le plus court si vous avez accès à un tel outil. (Vous rencontrez toujours le problème de devoir ajouter vos points de départ et d'arrivée s'ils ne font pas déjà partie du réseau)


Voici un exemple de code utilisant ArcObjects pour trouver le chemin le plus court (à l'aide de RasterDistanceOP). Ce n'est peut-être pas exactement ce que vous voulez, mais cela peut vous donner un point de départ.

Comment trouver le chemin le plus court à l'aide de RasterDistanceOp


Les premières pensées qui me sont venues à l'esprit sont celles-ci :

  1. Déterminez les limites maximales de toutes les fonctionnalités, y compris les points de début et de fin, tamponnez-les un peu pour vous assurer qu'il y a de la place autour de toutes les fonctionnalités. Faire un élément rectangulaire, b, à partir de ces limites.
  2. Soustraire les caractéristiques de blocage de b.
  3. Tesselate b en triangles, en s'assurant que les sommets de début et de fin sont des sommets dans ce nouveau maillage triangulaire, m.
  4. Générer les polygones de Voronoi, t (qui devraient être tous des triangles) de m.
  5. Les bords de t former un réseau sur lequel vous pouvez exécuter un algorithme de chemin le plus court.

Cela peut ne pas générer le meilleur chemin le plus court, car cela dépend de la façon dont le tesselator fait son travail, et dans tous les cas, il prendra une ligne médiane plutôt que la ligne de course. Mais il est concevable qu'une fois le chemin le plus court généré, vous puissiez déplacer ou supprimer des sommets, tester chaque arête affectée pour l'intersection avec les entités bloquantes et annuler l'opération si elle les coupe.


Le problème est compliqué. Il existe une nouvelle implémentation générique : l'algorithme du plus court chemin euclidien

Cela fonctionne pour tous les ensembles d'objets surfaciques maillés


Si cela ne vous dérange pas de traduire du C, vous pouvez essayer le script sur http://alienryderflex.com/shortest_path/


Voir la vidéo: 7 STATUES QUI ONT ÉTÉ FILMÉES EN TRAIN DE BOUGER ʘʘ