Thursday, March 18, 2010

Splitting a polygon using SQL Server Spatial queries

A recent project involved drawing regions on a map of a country using the Bing Maps Silverlight control. The user could zoom in to a suburb and draw a region (polygon) around an area on the map. Another feature, and hence the purpose of this blog post, involved enabling a user to draw a line through a region (polygon) and split the region in two: how was that splitting done?
Note: you will probably need some database experience and ideally some Bing/Google Maps experience for this to make sense

A quick intro to SQL Server Spatial queries

SQL Server 2008 introduced support for geo-spatial data. The two new spatial data types are:
  • Geometry: supports flat data surfaces. The following will create a polygon and a line and you can see that our resulting rectangle and line are straight:

DECLARE @Geometry GEOMETRY = 'POLYGON((10 10, 40 10, 40 40, 10 40, 10 10))'
DECLARE @Linestring GEOMETRY = 'LINESTRING(5 5, 50 50)'
SELECT @Geometry
SELECT @Linestring

  • Geography: enables you to define a region on a curved 3D surface. If you consider that the surface of the world is curved (the globe being a sphere), then you can appreciate that this data type is the type to use for storing geographic data accurately.  Notice how, in the following example, the square “bulges” and the line is curved, even though the polygon and linestring points are the same as the geometry data above.

DECLARE @Geography GEOGRAPHY = 'POLYGON((10 10, 40 10, 40 40, 10 40, 10 10))'
DECLARE @Linestring GEOGRAPHY = 'LINESTRING(5 5, 50 50)'
SELECT @Geography
SELECT @Linestring

There are many sites around the web which display the difference between the two types in nice pretty images. Also, John Nelson's site describes why you would want to use one over the other and Craig Dunn’s site gives a wealth of useful information about SQL Server Spatial queries.

Splitting basic geographic data

To split a polygon in two, we are going to use a linestring. Lets take the above geographic polygon and use the above geographic linestring to perform the split. Do you remember Set Theory (Intersection, Difference, etc.) from school? Well, to make the split happen we are going to get the difference between the polygon and the linestring:

DECLARE @Geography GEOGRAPHY = 'POLYGON((10 10, 40 10, 40 40, 10 40, 10 10))'
DECLARE @Linestring GEOGRAPHY = 'LINESTRING(5 5, 50 50)'
DECLARE @SplitRegion GEOGRAPHY = @Geography.STDifference(@Linestring.STBuffer(100000.0000)) 
SELECT @SplitRegion

We are using the built in STDifference() method to perform the split and we are giving the linestring a little bit of padding using STBuffer() to help make the split happen. I'd suggest you tweak the STBuffer value to suit your needs: depending on your polygon, you might find that a value of 0.0001 is all you need.
The resulting @SplitRegion object above is a MultiPolygon with two inner polygons defined. We can add the following to our above query to loop through each of the polygons:
DECLARE @i int = 1;
WHILE @i <= @SplitRegion.STNumGeometries() 
    DECLARE @InnerGeography GEOGRAPHY = @SplitRegion.STGeometryN(@i)
    SELECT @InnerGeography
    -- Next polygon
    SET @i = @i + 1

A more complex example

Lets for example, imagine that a company has two offices in Ireland with both offices maintaining a different range of customer and supplier locations. One office manages the bottom part of the country, the other office manages the rest of the country.
Each of these customer/supplier locations could be stored in a SQL Server spatial-aware database and another table could store a polygon shape of the country.
You could then split that polygon shape of the country based on where the zone of influence ends for the offices and use the resulting data to draw on a Bing/Google map which customers and suppliers belong to which office.