Grouper des formes géographiques

Question

J'utilise Dundas Maps et j'essaie de dessiner une carte du monde où les pays sont regroupés en régions spécifiques à une implémentation métier.

J'ai des données de forme (points et segments) pour chaque pays dans le monde. Je peux combiner des pays en régions en ajoutant tous les points et segments pour les pays d'une région à une nouvelle forme de région.

foreach(var region in GetAllRegions()){ 
    var regionShape = new Shape { Name = region.Name }; 
    foreach(var country in GetCountriesInRegion(region.Id)){ 
     var countryShape = GetCountryShape(country.Id); 
     regionShape.AddSegments(countryShape.ShapeData.Points, countryShape.ShapeData.Segments); 
    } 
    map.Shapes.Add(regionShape); 
} 

Le problème est que les lignes frontalières de pays encore apparaissent dans une région et je veux les supprimer de sorte que seules les frontières régionales apparaissent.

Les polygones Dundas doivent commencer et se terminer au même point. C'est le cas pour toutes les formes de pays. Maintenant, j'ai besoin d'un algorithme qui peut:

• Déterminer où les frontières de pays se croisent à une frontière régionale, de sorte que je peux rejoindre les segments de la frontière régionale.
• Déterminez les frontières de pays qui ne sont pas des frontières régionales afin de pouvoir les ignorer.
• Trier les points régionaux résultants afin qu'ils décrivent séquentiellement les limites de forme.

Ci-dessous est où je suis arrivé à ce jour avec la carte. Vous pouvez voir que les frontières du pays doivent encore être supprimées. Par exemple, la frontière entre la Mongolie et la Chine devrait être écartée, tandis que la frontière entre la Mongolie et la Russie devrait être maintenue.

La raison pour laquelle je dois conserver une bordure régionale est que les couleurs de la région seront significatives pour la transmission de l'information mais que les régions adjacentes peuvent être de la même couleur. Les régions peuvent changer pour inclure ou exclure des pays et c'est pourquoi la mise en forme régionale doit être dynamique.

EDIT: Je sais maintenant que ce que je cherche est une union de polygones. David Lean explains how to do it en utilisant les fonctions spatiales dans SQL Server 2008 qui pourrait être une option mais mes efforts se sont arrêtés car l'union de polygones qui en résulte est si complexe que SQL la tronque à 43 680 caractères. J'essaie maintenant soit de trouver une solution de contournement pour cela ou de trouver un moyen de faire l'union dans le code.

Answer 1

Lors du regroupement des pays, j'espère être là pas de chevauchement - vous pouvez prendre un algorithme assez naïf qui cherche des sommets partagés - une vue simple serait de parcourir les points sur un polygone, voyez s'il se trouve sur l'un de vos autres polygones et partage le même point suivant ou précédent pour voir s'il y a correspondance. Ensuite, il suffit de supprimer le sommet partagé pour créer votre union

Answer 2

Supposons que les pays voisins partagent des sommets et des arêtes communs (sinon, le problème devient beaucoup plus difficile).

Pour chaque région, parcourez les zones correspondant aux pays de la région et créez une liste de sommets et d'arêtes. Chaque arête doit avoir des pointeurs vers les deux sommets qui sont ses points de terminaison, et chaque sommet doit avoir des pointeurs vers les arêtes dont il est un point de terminaison. Lorsque vous ajoutez des sommets à la liste, assurez-vous qu'ils sont des sommets uniques. En d'autres termes, si vous ajoutez un sommet avec les coordonnées (x,y), s'il existe déjà un tel sommet dans la liste, n'en ajoutez pas un nouveau. Cela signifie que vous devez potentiellement vérifier chaque nouveau sommet par rapport à ceux déjà dans la liste.Vous pouvez accélérer cela en divisant la zone de délimitation de la région en n x n cases dans lesquelles vous pouvez stocker des sommets. Quand un nouveau sommet entre, regardez dans sa corbeille et comparez-le avec les autres vertices de cette corbeille. Lorsque vous ajoutez des arêtes à la liste des arêtes, faites la même chose: si un arête (v0, v1) est ajoutée, vérifiez s'il existe une arête existante (v0, v1) ou (v1, v0) . Sauf dans ce cas, éliminez le bord existant de la liste et n'ajoutez pas le nouveau bord. C'est parce que ces deux bords «s'annulent» - ils viennent des pays voisins. Et n'oubliez pas d'éliminer les pointeurs de bord dans la liste des vertex qui correspondent au bord supprimé.

Lorsque vous le faites, vous devriez avoir une liste d'arêtes non partagées par deux pays. Ce sont les bords qui forment la frontière de la région. Vous devriez également avoir une liste de sommets, certains pointant vers deux bords, et d'autres pointant vers aucun bord. Les anciens sommets sont à la frontière de la région.

Sélectionnez maintenant un bord de la liste des arêtes et supprimez-le (et supprimez les pointeurs de bord correspondants des sommets qui sont ses extrémités) à partir de l'edgelist. Aller à l'un des points d'extrémité du sommet, et il pointera vers un autre bord. De cette façon, vous marcherez d'un bord à l'autre le long des limites de la région. Ajoutez ces arêtes à votre regionShape lorsque vous les supprimez de votre edgelist. Finalement, vous reviendrez à l'extrémité de votre premier bord et vous aurez une boucle fermée. S'il reste des arêtes dans l'edgelist, recommencez le processus pour extraire une autre boucle de bordure et continuez jusqu'à ce que toutes les boucles de bordure aient été extraites et que l'edgelist soit vide.

J'ai mentionné une optimisation, qui consiste à organiser spatialement les sommets dans des cases afin que vous puissiez les tester plus rapidement. Une autre optimisation consiste à éviter de supprimer physiquement les bords des listes, mais simplement de les marquer comme 'supprimés'.