Grouping geographical shapes

Question

I am using Dundas Maps and attempting to draw a map of the world where countries are grouped into regions that are specific to a business implementation.

I have shape data (points and segments) for each country in the world. I can combine countries into regions by adding all points and segments for countries within a region to a new region shape.

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

The problem is that the country border lines still show up within a region and I want to remove them so that only regional borders show up.

Dundas polygons must start and end at the same point. This is the case for all the country shapes. Now I need an algorithm that can:

• Determine where country borders intersect at a regional border, so that I can join the regional border segments.
• Determine which country borders are not regional borders so that I can discard them.
• Sort the resulting regional points so that they sequentialy describe the shape boundaries.

Below is where I have gotten to so far with the map. You can see that the country borders still need to be removed. For example, the border between Mongolia and China should be discarded whereas the border between Mongolia and Russia should be retained.

The reason I need to retain a regional border is that the region colors will be significant in conveying information but adjacent regions may be the same color. The regions can change to include or exclude countries and this is why the regional shaping must be dynamic.

EDIT: I now know that I what I am looking for is a UNION of polygons. David Lean explains how to do it using the spatial functions in SQL Server 2008 which might be an option but my efforts have come to a halt because the resulting polygon union is so complex that SQL truncates it at 43,680 characters. I'm now trying to either find a workaround for that or find a way of doing the union in code.

Answer 1

When grouping countries, I'd hope there be no overlap -- you could take a fairly naive algorithm that looks for shared vertices - a simple view would be to iterate through the points on one polygon, see if it's on any of your other polygons, and shares the same next or previous point to see if there is a match. Then just remove the shared vertex to create your union

Answer 2

Assume that neighboring countries share common vertices and edges (if not, the problem becomes much more difficult).

For each region, go through the poylgons corresponding to countries in the region and create a list of vertices and edges. Each edge should have pointers to the two vertices that are its endpoints, and each vertex should have pointers to the edges of which it is an endpoint.

As you add vertices to the list, make sure they are unique vertices. In other words, if you are adding a vertex with coordinates (x,y), if there is already such a vertex in the list don't add a new one. This means you potentially have to check every new vertex against ones already in the list. You can speed this up by breaking up the bounding box of the region into, say, nxn bins in which you can store vertices. When a new vertex comes in, look up its bin and check it against the other vertices in that bin.

As you add edges to the edge list, do the same thing - if an edge (v0,v1) is being added, check to see whether there is an existing edge (v0,v1) or (v1,v0). Except in this case, eliminate the existing edge from the list, and don't add the new edge. That's because these two edges 'cancel' each other - they come from neighboring countries. And don't forget to eliminate the edge pointers in the vertex list that correspond to the deleted edge.

When you're do, you should have a list of edges not shared by two countries. These are the edges that form the border of the region. You should also have a list of vertices, some pointing to two edge, and others pointing to no edges. The former vertices are on the region border.

Now pick an edge from the edge list, and delete it (and delete the corresponding edge pointers from the vertices that are its endpoints) from the edgelist. Go to one of the vertex endpoints, and it will point to another edge. In this way, you'll walk from edge to edge along the region boundary. Add these edges to your regionShape as you delete them from your edgelist. Eventually you'll get back to the endpoint of your first edge and you'll have a closed loop.

If there are any edges remaining in the edgelist, start the process again to extract another border loop, and keep going until all the border loops have been extracted and the edgelist is empty.

I've mentioned one optimization, which is to organize the vertices spatially into bins so that you can more quickly test them equality. Another optimization is to avoid physically deleting edges from lists, but just to mark them as 'deleted'.