Agrupación de formas geográficas

Question

Uso Dundas Maps e intento dibujar un mapa del mundo en el que los países se agrupen en regiones específicas de la implementación de una empresa.

Tengo datos de forma (puntos y segmentos) para cada país del mundo. Puedo combinar países en regiones agregando todos los puntos y segmentos para países dentro de una región a una nueva forma de región.

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); 
} 

El problema es que las líneas fronterizas de los países siguen apareciendo dentro de una región y quiero eliminarlos de manera que sólo las fronteras regionales muestran.

Los polígonos Dundas deben comenzar y terminar en el mismo punto. Este es el caso para todas las formas de país. Ahora necesito un algoritmo que pueda:

• Determinar dónde se cruzan las fronteras de un país en un borde regional, de modo que pueda unirme a los segmentos de borde regionales.
• Determine qué fronteras de país no son fronteras regionales para que pueda descartarlas.
• Ordene los puntos regionales resultantes para que describan de forma secuencial los límites de la forma.

A continuación es donde he llegado hasta el momento con el mapa. Puedes ver que las fronteras de los países aún deben ser eliminadas. Por ejemplo, la frontera entre Mongolia y China debe descartarse, mientras que la frontera entre Mongolia y Rusia debe conservarse.

La razón por la que necesito conservar un borde regional es que los colores de la región serán significativos en el transporte de información, pero las regiones adyacentes pueden ser del mismo color. Las regiones pueden cambiar para incluir o excluir países, y esta es la razón por la que la configuración regional debe ser dinámica.

EDITAR: Ahora sé que lo que estoy buscando es un UNION de polígonos. David Lean explains how to do it usando las funciones espaciales en SQL Server 2008 que podría ser una opción, pero mis esfuerzos se han detenido porque la unión de polígonos resultante es tan compleja que SQL la trunca a 43,680 caracteres. Ahora estoy tratando de encontrar una solución para eso o encontrar una forma de hacer la unión en el código.

Answer 1

Al agrupar los países, yo espero no haya solapamiento - se puede tomar un algoritmo bastante ingenua que busca vértices compartidos - una visión simple sería iterar a través de los puntos de un polígono, ver si está en cualquiera de sus otros polígonos, y comparte el mismo punto anterior o siguiente para ver si hay una coincidencia. Luego simplemente elimine el vértice compartido para crear su unión

Answer 2

Suponga que los países vecinos comparten vértices y bordes comunes (si no, el problema se vuelve mucho más difícil).

Para cada región, vaya a través de los polígonos correspondientes a los países de la región y cree una lista de vértices y bordes. Cada borde debe tener punteros a los dos vértices que son sus puntos finales, y cada vértice debe tener punteros a los bordes de los cuales es un punto final.

Al agregar vértices a la lista, asegúrese de que sean vértices únicos. En otras palabras, si está agregando un vértice con las coordenadas (x,y), si ya existe dicho vértice en la lista, no agregue uno nuevo. Esto significa que potencialmente tiene que verificar cada nuevo vértice contra los que ya están en la lista.Puede acelerar esto dividiendo el cuadro delimitador de la región en, por ejemplo, n x n contenedores en los que puede almacenar vértices. Cuando entra un nuevo vértice, busca su contenedor y compruébalo con los otros vértices de ese contenedor.

Al agregar bordes a la lista de bordes, haga lo mismo: si se agrega un borde (v0, v1), verifique si hay un borde existente (v0, v1) o (v1, v0) . Excepto en este caso, elimine el borde existente de la lista y no agregue el nuevo borde. Eso se debe a que estos dos bordes se "cancelan" entre sí, provienen de países vecinos. Y no olvide eliminar los punteros de borde en la lista de vértices que corresponden al borde borrado.

Cuando lo haga, debe tener una lista de bordes no compartidos por dos países. Estos son los bordes que forman el borde de la región. También debería tener una lista de vértices, algunos apuntando a dos bordes y otros apuntando a sin bordes. Los primeros vértices están en el borde de la región.

Ahora elija un borde de la lista de bordes y elimínelo (y elimine los punteros de borde correspondientes de los vértices que son sus puntos finales) del edgelist. Vaya a uno de los puntos finales de vértice, y apuntará a otro borde. De esta forma, caminará de borde a borde a lo largo del límite de la región. Agregue estos bordes a su regiónForma a medida que los elimina de su edgelist. Eventualmente volverá al punto final de su primer borde y tendrá un ciclo cerrado.

Si quedan bordes en el edgelist, comience nuevamente el proceso para extraer otro bucle de borde y continúe hasta que se hayan extraído todos los bucles de borde y el edgelist esté vacío.

He mencionado una optimización, que es organizar los vértices espacialmente en contenedores para que pueda probarlos más rápidamente la igualdad. Otra optimización es evitar borrar físicamente los bordes de las listas, pero solo para marcarlos como 'eliminados'.