Raggruppamento di forme geografiche

Question

Utilizzo mappe di Dundas e cerco di disegnare una mappa del mondo in cui i paesi sono raggruppati in regioni specifiche dell'implementazione aziendale.

Ho dati di forma (punti e segmenti) per ogni paese del mondo. Posso combinare i paesi in regioni aggiungendo tutti i punti e i segmenti per i paesi all'interno di una regione a una nuova forma di regione.

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

Il problema è che le linee di confine dei paesi mostrano ancora in piedi all'interno di una regione e voglio rimuoverli in modo che solo i confini regionali si presentano.

I poligoni di Dunda devono iniziare e terminare nello stesso punto. Questo è il caso per tutte le forme del paese. Ora ho bisogno di un algoritmo che può:

• Determinare dove i confini di un paese si intersecano a una frontiera regionale, in modo da poter accedere ai segmenti di confine regionali.
• Determinare quali confini di paese non sono i bordi regionali in modo che sia possibile eliminarli.
• Ordinare i punti regionali risultanti in modo che descrivano in sequenza i contorni della forma.

Di seguito è dove sono arrivato fino ad ora con la mappa. Puoi vedere che i confini del paese devono ancora essere rimossi. Ad esempio, il confine tra la Mongolia e la Cina dovrebbe essere scartato, mentre il confine tra la Mongolia e la Russia dovrebbe essere mantenuto.

Il motivo per cui ho bisogno di mantenere un confine regionale è che i colori della regione saranno significativi nel trasmettere informazioni ma le regioni adiacenti potrebbero essere dello stesso colore. Le regioni possono cambiare per includere o escludere i paesi e questo è il motivo per cui la modellazione regionale deve essere dinamica.

MODIFICA: Ora so che quello che sto cercando è UNIONE di poligoni. David Lean explains how to do it utilizza le funzioni spaziali in SQL Server 2008 che potrebbe essere un'opzione, ma i miei sforzi si sono interrotti perché l'unione poligonale risultante è così complessa che SQL la tronca a 43.680 caratteri. Ora sto cercando di trovare una soluzione alternativa o di trovare un modo per realizzare l'unione nel codice.

Answer 1

Quando raggruppamento paesi, mi auguro non ci sia sovrapposizione - si potrebbe prendere un algoritmo piuttosto ingenua che cerca vertici condivisi - una visione semplice sarebbe per scorrere i punti su un poligono, vedi se è su uno dei tuoi altri poligoni e condivide lo stesso punto successivo o precedente per vedere se c'è una corrispondenza. Quindi rimuovi il vertice condiviso per creare la tua unione

Answer 2

Presumiamo che i paesi vicini condividano vertici e spigoli comuni (in caso contrario, il problema diventa molto più difficile).

Per ciascuna regione, scorrere le poiligoni corrispondenti ai paesi della regione e creare un elenco di vertici e spigoli. Ogni spigolo dovrebbe avere puntatori ai due vertici che sono i suoi punti finali, e ogni vertice dovrebbe avere puntatori ai bordi dei quali è un punto finale.

Come si aggiungono i vertici all'elenco, assicurarsi che siano vertici univoci. In altre parole, se si aggiunge un vertice con le coordinate (x,y), se esiste già un tale vertice nell'elenco non aggiungerne uno nuovo. Ciò significa che è potenzialmente necessario verificare ogni nuovo vertice rispetto a quelli già presenti nell'elenco.Puoi accelerare suddividendo il riquadro di delimitazione della regione in, ad esempio, n x n bin in cui è possibile memorizzare i vertici. Quando arriva un nuovo vertice, controlla il suo contenitore e confrontalo con gli altri vertici in quel contenitore.

Come si aggiungono i bordi all'elenco dei bordi, fare la stessa cosa: se si aggiunge uno spigolo (v0, v1), verificare se c'è uno spigolo esistente (v0, v1) o (v1, v0) . Tranne in questo caso, elimina il bordo esistente dall'elenco e non aggiungere il nuovo bordo. Questo perché questi due lati si "cancellano" l'un l'altro - vengono dai paesi vicini. E non dimenticare di eliminare i puntatori ai bordi nell'elenco dei vertici che corrispondono al bordo cancellato.

Quando lo fai, dovresti avere un elenco di spigoli non condivisi da due paesi. Questi sono i bordi che formano il confine della regione. Dovresti anche avere un elenco di vertici, alcuni che puntano a due bordi e altri che non puntano a bordi. Gli ex vertici sono sul confine della regione.

Ora selezionare un bordo dall'elenco dei bordi ed eliminarlo (ed eliminare i puntatori ai bordi corrispondenti dai vertici che sono i relativi endpoint) da lista edgelist. Vai a uno degli endpoint del vertice e punta a un altro bordo. In questo modo, camminerai da un bordo all'altro lungo il confine della regione. Aggiungi questi spigoli alla tua regione come quando li elimini dal tuo edgelist. Alla fine tornerai al punto finale del tuo primo vantaggio e avrai un ciclo chiuso.

Se ci sono dei bordi rimanenti in Lista edgelist, avviare di nuovo il processo per estrarre un altro ciclo di bordo e continuare fino a quando tutti i loop del bordo sono stati estratti e il gruppo di simboli è vuoto.

Ho menzionato un ottimizzazione, che consiste nell'organizzare i vertici spazialmente in contenitori in modo da poterli testare più rapidamente sull'uguaglianza. Un'altra ottimizzazione consiste nell'evitare di eliminare fisicamente i bordi dagli elenchi, ma solo per contrassegnarli come "eliminati".