Calculateur de distance par mer, coordonnées intermédiaires?

Question

Comment calculer la distance entre 2 coordonnées par mer? Je veux aussi pouvoir tracer une route entre les deux coordonnées. Seule la solution que j'ai trouvée jusqu'ici consiste à diviser une carte en pixels, à identifier chaque pixel comme étant LAND ou SEA, puis à essayer de trouver le chemin en utilisant l'algorithme A *. Transformez ensuite les pixels en coordonnées relatives.

Je peux acheter des progiciels mais aucun n'a d'extension en ligne. Un service qui calcule les distances entre les ports maritimes et trace le chemin sur une carte est searates.com

Answer 1

Il vous faudra à peu près diviser la mer en pixels et faire quelque chose comme A *. Vous pouvez l'optimiser un peu en fusionnant des pixels contigus dans des zones plus grandes, mais si vous gardez tout les carrés, cela facilitera probablement la recherche. La recherche ne serait plus de style Manhattan, mais si vous aviez des carrés assez grands, le temps de décision de connexion supplémentaire serait plus que compensé. Alternativement, vous pouvez développer itérativement des polygones de tous vos ports, en construisant des polygones convexes (de sorte que n'importe quel point dans le polygone soit accessible à partir de n'importe quel autre sans sortir, vous voulez éviter la forme PacMan, par exemple), bien qu'il s'agisse d'un raffinement/complication/optimisation de l'approche des «carrés» que j'ai mentionnée pour la première fois. La clé est que vous savez une fois que vous êtes dans une zone que vous pouvez atteindre n'importe où ailleurs dans cette zone.

Je ne sais pas si cela aide, désolé. Ça a été une longue journée. Bonne chance, cependant. Cela ressemble à un problème amusant!

Editer: Oublié de mentionner, vous pouvez également pré-traiter votre zone dans un quadtree. C'est-à-dire, prenez votre carte entière et divisez-la en deux verticalement et horizontalement (vous n'avez pas besoin de faire les deux divisions en même temps, et si vous voulez passer du temps à faire de meilleurs scindages, vous pouvez le faire plus tard) , et faites cela récursivement jusqu'à ce que chaque nœud soit entièrement terrestre ou maritime. A partir de là, vous pouvez créer un réseau de connexions trivial (il suffit de connecter les feuilles voisines), et le A * devrait être assez facile à implémenter à partir de là. Ce sera probablement le moyen le plus facile de mettre en œuvre ma première suggestion de toute façon. :)

Answer 2

Méfiez-vous du fait que les cartes peuvent déformer les distances. Par exemple, dans un Mercator, les segments de projection éloignés de l'équateur représentent moins la distance réelle que les segments proches de l'équateur de même longueur. Si vous affectez simplement un coût uniforme à vos pixels/carrés/etc, vous vous retrouverez avec un routage non optimal et des calculs de distance erronés. Si vous projetez une grille sur votre carte (les pixels étant juste une grille particulière parmi plusieurs possibles) et recherchez le chemin optimal en utilisant A *, tout ce que vous devez faire pour que l'algorithme de recherche se comporte correctement est défini le poids du bord selon la distance réelle le long de la surface de la sphère (terre) et non la distance sur la carte.

Attention, il ne suffit pas de dire «mer ou non-mer» pour déterminer la navigabilité. Il y a aussi des problèmes de profondeur, d'acheminement du trafic (par exemple, le trafic maritime a pensé que la Manche est divisée en voies) et de considérations politiques (eaux territoriales, etc.). Vous souhaitez également ajouter manuellement des itinéraires pour les chaînes trop petites pour apparaître sur la carte (Panama, Suez) et ajuster leur coût pour couvrir les frais généraux encourus.

Answer 3

J'ai atteint une solution satisfaisante. C'est dans le sens de ce que vous avez suggéré et de ce que j'avais en tête au départ, mais il m'a fallu un certain temps pour comprendre le logiciel et les concepts SIG, je suis un débutant SIG.Si quelqu'un rencontre quelque chose de similaire, voici ma configuration: PostGIS pour PostgreSQL, les cartes de Natural Earth, le logiciel d'édition SIG qGis et OpenJUmp, les algorithmes de routage pgRouting.

Les cartes de la Terre Naturelle avaient besoin d'un traitement pour être utiles, j'ai rejoint les polys marins et les rivières pour pouvoir obtenir des chemins précis vers les points les plus à l'intérieur des terres. Ensuite, j'ai utilisé les graticules à 1 degré pour obtenir des chemins d'un continent à l'autre (j'ai besoin de trouver une solution plus élégante car certains chemins ressemblent à des cubes d'échecs). Toutes ces opérations peuvent être effectuées à partir de la ligne de commande en utilisant PostGIS, j'ai trouvé plus facile d'utiliser le logiciel de bureau (suivant, suivant). Une alternative aux cartes de la Terre Naturelle pourrait être l'OpenStreetMap, mais la décharge de planet.osm est autour de 200Go et cela m'a découragé.

Je pense que cette configuration résout également le problème de précision de la distance, PostGIS prend en compte la forme réelle de la Terre et les distances devraient être assez précises. J'ai encore besoin de faire quelques tests et réglages, mais je peux dire qu'il peut calculer et dessiner un itinéraire à partir de 2 points sur les côtes du monde (pas encore de petites îles isolées) et afficher les noms des points de routage (canaux, mers) , rivières, océans).