Misc

Spatial Operations in SQL Server 2008 (Katmai) – Union and Convex Hull

CODE EXAMPLES IN THIS POST WORK WITH THE NOVEMBER 2007 CTP (CTP 5) OF SQL SERVER 2008.

Say you would like to create a polygon out of a group of points. One way of doing this is to union the points together then create a convex hull from those points. A convex hull is a polygon that contains all the points of the geometries that it is made from. “The convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.” [Wikipedia:Convex Hull]

It is possible to create a convex hull from just two points, however in this case you will end up with a linestring rather than a polygon because a polygon requires a minimum of 3 points.

DECLARE @a geometry
DECLARE @b geometry

SELECT @a = geometry::STGeomFromText('POINT(0 0)',0),
       @b = geometry::STGeomFromText('POINT(10 10)', 0);

SELECT @a.STUnion(@b).STConvexHull().ToString();

Results in: LINESTRING (10 10, 0 0)

With an additional point a polygon can be created.

DECLARE @a geometry
DECLARE @b geometry
DECLARE @c geometry

SELECT @a = geometry::STGeomFromText('POINT(0 0)',0),
       @b = geometry::STGeomFromText('POINT(10 10)', 0),
       @c = geometry::STGeomFromText('POINT(20 0)', 0);

SELECT @a.STUnion(@b).STUnion(@c).STConvexHull().ToString();

Results in: POLYGON ((20 0, 10 10, 0 0, 20 0))

What you’ll notice is that the polygon has 4 points, but we only gave 3 to start with. That is because the first and last point in the polygon are the same.

If you were to look at the geometry that had been created with just the union operations before the convex hull was made then you’ll see it is a MultiPoint: MULTIPOINT ((10 10), (20 0), (0 0))

graph1Unioning different types of geometry together, such as a point, linestring and polygon (see figure on the right) will, if the geometries don’t overlap, result in a GeometryCollection. For instance the code:

DECLARE @a geometry
DECLARE @b geometry
DECLARE @c geometry

SELECT @a = geometry::STGeomFromText(
            'POLYGON ((25 5, 15 15, 5 5, 25 5))',0),
       @b = geometry::STGeomFromText(
            'POINT(5 10)', 0),
       @c = geometry::STGeomFromText(
            'LINESTRING(20 20, 30 5)', 0);

SELECT  @a.STUnion(@b).STUnion(@c).ToString();

 

Will result in the following: GEOMETRYCOLLECTION (POINT (5 10), LINESTRING (20 20, 30 5), POLYGON ((5 5, 25 5, 15 15, 5 5)))

Moving the point to a position within the polygon, such as POINT(15 10) will result in a geometry collection that does not contain a separate point. As the point is within the boundary of the polygon it does not need to be separately listed in the geometry collection. The actual geometry looks like this: GEOMETRYCOLLECTION (LINESTRING (20 20, 30 5), POLYGON ((5 5, 25 5, 15 15, 5 5)))

graph2Moving the linestring to travel from 5,10 to 30,10 (through the polygon) results in a geometry collection with two linestrings (see figure on the left). One that runs from 5,10 to the boundary of the polygon at 10,10 and the second that runs from the  boundary of the polygon at 20,10 to the original end point at 30,10. The resulting MultiGeometry looks like this: GEOMETRYCOLLECTION (LINESTRING (30 10, 20 10), LINESTRING (10 10, 5 10), POLYGON ((5 5, 25 5, 20 10, 15 15, 10 10, 5 5)))

DECLARE @a geometry
DECLARE @b geometry
DECLARE @c geometry

SELECT @a = geometry::STGeomFromText(
            'POLYGON ((25 5, 15 15, 5 5, 25 5))',0),
       @b = geometry::STGeomFromText(
            'POINT(15 10)', 0),
       @c = geometry::STGeomFromText(
            'LINESTRING(5 10, 30 10)', 0);

SELECT @a.STUnion(@b).STUnion(@c).ToString();

Other posts in this series:

2 thoughts on “Spatial Operations in SQL Server 2008 (Katmai) – Union and Convex Hull

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s