Saturday, October 25, 2008

Dave does Data (Under construction - don't read yet) : SQL 2008 Spatial Samples, Part n-2 on n - Geometric “Set Theory” Methods

 

SQL 2008 Spatial Samples, Part n-2 on n - Geometric “Set Theory” Methods

This post covers the following methods: STUnion, STIntersection, STDifference, STSymDifference, STCentroid / STEnvelopeCentre, STPointOnSurface, STBoundary.

Overview of Geometric "Set Theory" Methods

These Methods help to understand the relationship between spatial objects & also to create new objects that show that relationship.

Note: The sample code in the post shows more complex shapes than the diagrams attached. Try cutting the code into SSMS & look at the results..

Method .STUnion()

  • Combines to Spatial Objects.
    • Creates a "Binary OR" of the two objects (shapes, lines, points).
  • Works with both GeometryGeography objects
  • Sister method of .STIntersection Method.

    Syntax: geo1.STUnion(geo2)

Example use: Combine all "Mobile Phone Tower" coverage areas to show "complete phone coverage" for an area.
STUnion

-- ==< Sample: STUnion >===
DECLARE @a GEOMETRY = 'POLYGON((1 0, 1 8, 6 4, 1 0))'
DECLARE @b GEOMETRY = 'POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5) )'

SELECT @a.STUnion(@b) as 'STUnion', 'STUnion' as Labels

SELECT @a as geo, 'A' as Labels
UNION ALL SELECT @b, 'B'

Tip: How to “Union” many rows



Quite frequently you may want to aggregate a set of base shapes into a larger region. Unfortunately it seems the Open Geospatial Consortium did not spec out their functions to take an entire set of Spatial Objects as a parameter, just one at a time. While that is fine when using them in your code (VB, C# etc), it is less desirable when working with a relational database which comes with an extremely fast way to process "Sets" of data.

This is a sample of using TSQL apply a Spatial Method to a set of rows. While an aggregate UNION of rows is more frequently used than any of the other methods ie: STDifference, this approach will work for them too. Personally I’m not a big fan of the Cursor Approach to geometric shape manipulation. I did write a Set Based solution to finding the total envelope of a collection of shapes. <see my comments on .Reduce in another Post>. It is at worse 50% faster & so far at best 1,037 TIMES faster than the cursor algorithm below. I’m am looking for a better algorithm for Unions too, I expect that the solution will be an CLR Aggregate function.

Still, aggregating shapes is a mathematically complex problem with many interesting niche scenarios. In the absence of a better solution, if you do find this is not performing well, I’d suggest you look at a variety of alternatives designs. Eg:


  1. Pre-Aggregate your Union shapes, perhaps a batch job off-hours.
  2. Off-load the Server CPU, Run the UNION on the Client,
  3. Run multiple parallel queries each selecting a different subset of the rows, UNION the rows each subset in parallel & then UNION the subsets together.
  4. Use Reduce to strip the detail from your polygons, Union them. Find the boundary, use STRelate to find all the Reduced polygons that live on the aggregate border. Union all the originals of those together & generate a very accurate external border. This is a long process & clearly only worthwhile when you are joining 1,000’s of highly detailed shapes with no internal holes.
  5. Combine some of the alternatives above, ie: 1 & 3, perhaps pre-aggregate some of the shapes.

Note: I've seen similar code sample posts in the Internet using hints like "WITH (NOLOCK)". Using Hints is an extremely poor practice. DO NOT DO IT unless you have strong empirical evidence, that you needed it to solve an issue on YOUR system. Even then you should document in the code; What you tested, the difference you found, the version you tested it on & maybe the alternatives you considered. NOLOCK in particular can has some really nasty side-effects & should be used with caution.

Sample code: loops thru a resultset generating a larger UNIONed Region.

DECLARE @thisGeom geometry;
DECLARE @totalGeom geometry;
DECLARE @firstRow INT = 1 -- Used as BOOLEAN = TRUE

DECLARE GeomCursor CURSOR FAST_FORWARD FOR SELECT [geom] FROM [dbo].[NSW_Suburbs_region]; -- WITH (NOLOCK);
OPEN GeomCursor;
FETCH NEXT FROM GeomCursor INTO @thisGeom;
WHILE @@FETCH_STATUS = 0
BEGIN
IF (@firstRow = 1) BEGIN -- First Row Returned
SET @totalGeom = @thisGeom;
SET @firstRow = 0; -- FALSE
END ELSE BEGIN
SET @totalGeom = ( SELECT @totalGeom.STUnion(@thisGeom)) ;
END;
FETCH NEXT FROM GeomCursor INTO @thisGeom;
END;
CLOSE GeomCursor;
DEALLOCATE GeomCursor;

SELECT @totalGeom -- The total Union of the resultset

Method .STIntersection()



  • Find the area where the 2 Objects overlap. (show what is in both)

    • Creates a "Binary AND" of the two objects (shapes, lines, points).

  • Works with both GeometryGeography objects
  • Opposite method of .STSymDifference Method.


    Syntax: geo1.STIntersection(geo2)



Example use: Show suburbs with > 5% Jewish population together with our Stores that promote "Ham & Pineapple" Pizza's
STIntersection

-- ==< Sample: STIntersection >===
DECLARE @a GEOMETRY = 'POLYGON((1 0, 1 8, 6 4, 1 0))'
DECLARE @b GEOMETRY = 'POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5) )'

SELECT @a.STIntersection(@b) as 'STIntersection', 'STIntersection' as Labels

SELECT @a as geo, 'A' as Labels
UNION ALL SELECT @b, 'B'

Method .STSymDifference()



  • Find the area where the 2 Objects do not overlap. (what is one or other but not in both)

    • Creates a "Binary XOR" of the two objects (shapes, lines, points).
    • Creates a multishape "GeometryCollection" which only has either 1 region or the other. Any intersection containing both shapes is removed.
    • Short for Symmetric Difference

  • Works with both GeometryGeography objects
  • Opposite method of .STIntersection Method.

    Syntax: geo1.STSymDifference(geo2)



Example use: In a new land development, Show all blocks of land with Electricity connected, combined with block of land with Water & sewerage connected. This would highlight blocks that need the least investment to bring them up to saleable condition.
SymDifference

-- ==< Sample: STSymDifference >===
DECLARE @a GEOMETRY = 'POLYGON((1 0, 1 8, 6 4, 1 0))'
DECLARE @b GEOMETRY = 'POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5) )'

SELECT @a.STSymDifference(@b) as 'STSymDifference', 'STSymDifference' as Labels

SELECT @a as geo, 'A' as Labels
UNION ALL SELECT @b, 'B'

Method .STDifference()



  • Remove the parameter shape from this shape.

    • Equivalent of Subtraction (Arithmetic's minus operation).
    • Unlike the other methods in this post, the order is important. A.STDifference(B) yields a different result to B.STDifference(A)

  • Works with both GeometryGeography objects
  • Sister method of .STSymDifference Method.

    Syntax: geo1.STDifference(geo2)



Example use: Show areas of the city which do not have good mobile phone coverage "Dead Zones". ie: Use STUnion to get the complete coverage area & then use STDifference to subtract it from a map of the city. 
STDifference

-- ==< Sample: STDifference >===
DECLARE @a GEOMETRY = 'POLYGON((1 0, 1 8, 6 4, 1 0))'
DECLARE @b GEOMETRY = 'POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5) )'

SELECT @a.STDifference(@b) as 'STDifference', 'A.STDifference(B)' as Labels
SELECT @b.STDifference(@a) as 'STDifference', 'B.STDifference(A)' as Labels

SELECT @a as geo, 'A' as Labels
UNION ALL SELECT @b, 'B'

Method .STCentroid()



  • Geometric centre of a (multi)Polygon.

    • Null for Points & Lines.

  • Works with Geometry objects only. It is not a method of Geography Objects.
  • Similar to geography method STEnvelopeCentre()
  • Not good for placing labels on shapes, use STPointOnSurface.


    Syntax: geo1.STCentroid()



Example use: Centre the Map display around this object.
STCentriod

-- ===< Samples for STCentroid & STPointOnSurface >===
-- Sample 1: STCentroid not affected by interior holes.
DECLARE @g AS GEOMETRY;
SET @g = 'POLYGON( (1 1, 9 1, 9 9, 1 9, 1 1),(2 2, 4 2, 4 4, 2 4, 2 2))'
SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.STCentroid().STBuffer(0.2), @g.STCentroid().ToString(), 'STCentroid'
UNION ALL
SELECT @g.STPointOnSurface().STBuffer(0.2), @g.STPointOnSurface().ToString(), 'STPointOnSurface'
go

-- Sample 2: STCentroid might put labels in the interior holes.
DECLARE @g AS GEOMETRY;
SET @g = 'POLYGON( (1 1, 9 1, 9 9, 1 9, 1 1),(4 4, 6 4, 6 6, 4 6, 4 4))'
SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.STCentroid().STBuffer(0.2), @g.STCentroid().ToString(), 'STCentroid'
UNION ALL
SELECT @g.STPointOnSurface().STBuffer(0.2), @g.STPointOnSurface().ToString(), 'STPointOnSurface'
go

-- Sample 3: STCentroid not so good for labels on Crescent shapes either
DECLARE @g AS GEOMETRY;
SET @g = 'POLYGON( (1 1, 2 1, 5 3, 7 6, 5 9, 2 11, 1 11, 5 6, 1 1))'
SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.STCentroid().STBuffer(0.2), @g.STCentroid().ToString(), 'STCentroid'
UNION ALL
SELECT @g.STPointOnSurface().STBuffer(0.2), @g.STPointOnSurface().ToString(), 'STPointOnSurface'


Method .STPointOnSurface()



  • Returns a point somewhere on the surface of the object.

    • Usually above & slightly to the left of the centre.

  • Handy for placing Labels on an object. Especially Complex Polygons with a hole in the centre &/or Crescent shaped objects, where the STCentroid returns a point that is not within the shape.
  • For MultiPoints & Lines it returns the same point as .STEndPoint().
  • Works with Geometry objects only. It is not a method of Geography Objects.

    • For Geography:

      • Use .STEndPoint for geography Lines & Points.
      • Use a negative value for STBuffer, grab one of the points & test it is ok using STIntersects.

  • Companion method to STCentroid

    Syntax: geo1.STPointOnSurface()



Example use: Drawing icons & labels on a shape.
See .STCentroid above for Sample picture & Code.


Method .STEnvelopeCentre()



  • Approximate centre of a geography object.

    • Unlike STCentroid it works for (multi)Points & Lines as well as Polygons.
    • I stress it is not a perfect Geometric centre, but often good enough.

  • Works with Geography objects only. It is not a method of Geometry Objects.
  • Similar to geometry method STCentroid()
  • Not always reliable for placing labels on shapes, but no geography equivalent to STPointOnSurface.

    Syntax: geo1.STEnvelopeCentre()



Example use: Centre the Map display around this object. Or perhaps Find the approximate centre of a lot of Points in a MultiPoint object.

-- ==< Samples for STEnvelopeCentre being equivalent of STCentroid & STPointOnSurface >==
-- Sample 1: STEnvelopeCentre is not a perfect geometric centre
DECLARE @g AS GEOGRAPHY;
-- SET @g = 'POLYGON( (1 1, 9 1, 9 9, 1 9, 1 1),(4 4, 4 6, 6 6, 6 4, 4 4))' --
-- SET @g = 'POLYGON( (1 1, 90 1, 90 90, 1 90, 1 1),(4 4, 4 6, 6 6, 6 4, 4 4))' -- Interesting to see how far the centre moves when you remove the inner ring in lower left
SET @g = 'POLYGON( (10 1, 90 1, 90 90, 1 90, 10 1))' -- Interesting to see Centre is oval shaped at 55 Degrees

SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.EnvelopeCenter().STBuffer(200000), @g.EnvelopeCenter().ToString(), 'EnvelopeCenter'
Go

-- Sample 2: EnvelopeCenter is not quite the same as Geometry's STCentroid method
DECLARE @g AS GEOGRAPHY;
SET @g = 'POLYGON( (1 1, 2 1, 5 3, 7 6, 5 9, 2 11, 1 11, 5 6, 1 1))'
SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.EnvelopeCenter().STBuffer(20000), @g.EnvelopeCenter().ToString(), 'EnvelopeCenter'
go

-- Sample 3: It works with lines
DECLARE @g AS GEOGRAPHY;
SET @g = 'LINESTRING( 1 1, 2 1, 5 3, 7 6, 5 9, 2 11, 1 11, 5 6, 1 1)'
SELECT @g as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.EnvelopeCenter().STBuffer(20000), @g.EnvelopeCenter().ToString(), 'EnvelopeCenter'
go

-- Sample 4: It works with Points - but notice it is in a different position.
DECLARE @g AS GEOGRAPHY;
SET @g = 'MULTIPOINT( (1 1), (2 1), (5 3), (7 6), (5 9), (2 11), (1 11), (5 6), (1 1))'
SELECT @g.STBuffer(15000) as Geo, @g.ToString() as WKT, 'Exterior' as Method
UNION ALL
SELECT @g.EnvelopeCenter().STBuffer(20000), @g.EnvelopeCenter().ToString(), 'EnvelopeCenter'




Method .STBoundary()



  • Returns :-

    • Perimeter of a polygon, as a Linestring
    • Start/End Points of a Line. As a MultiPoint( (End X,Y), (Start X,Y) )

      • NB: If the line is closed ie: Start & End are the same, then returns Empty

  • Works with Geometry objects only. It is not a method of Geography Objects.


Syntax: geo1.STBoundary(geo2)



Example use: Handy to convert a Polygon to Line
STBoundary

-- ========< Test 1 - Closed Shapes - Polygon >=========================================
DECLARE @g geometry;
SET @g = geometry::STGeomFromText('Polygon((0 0, 2 0, 4 3, 2 2, 0 2,0 0))', 0);
-- Show Boundary of a Polygon
SELECT @g.STBoundary(),@g.STBoundary().ToString(), 'STBoundary of Polygons'
go

-- ========< Test 1 - Closed Shapes - Closed Line = Empty >=========================================
DECLARE @g geometry;
SET @g = geometry::STGeomFromText('Polygon((0 0, 2 0, 4 3, 2 2, 0 2,0 0))', 0);
-- Show Boundary of a Closed LineString = Empty
SELECT @g.STBoundary().STBoundary(),@g.STBoundary().STBoundary().ToString(), 'STBoundary of Closed LineStrings';
go

-- ========< Test 2 - Open Lines & Points >===================================
DECLARE @g geometry;
SET @g = geometry::STGeomFromText('MULTILINESTRING( (1 0, 2 0, 2 2, 0 2, 0 0, 1 1),
(5 7, 7 7, 7 9, 5 9, 5 7),
(11 1, 13 1, 13 3, 11 3, 11 1, 9 4 ) )', 0);

-- Show Boundary of a MultiLineString is just End & Start Points.
SELECT @g,@g.ToString()
UNION ALL
-- Note: Closed LineStrings aren't there.
SELECT @g.STBoundary().STBuffer(0.1),@g.STBoundary().ToString()
UNION ALL
-- Show Boundary of Points = Empty
SELECT @g.STBoundary().STBoundary(),@g.STBoundary().STBoundary().ToString();

More info



For more info see SQL Server 2008 Books Online Geometry Data Type Method Reference


Dave does Data (Under construction - don't read yet) : SQL 2008 Spatial Samples, Part n-2 on n - Geometric “Set Theory” Methods

1 comment:

Davele said...

If you are going to republish my blog ie:(rip-off & pretend it is your own work).
At least you could use the final copy & not the 1st draft (that was why it said "Don't read yet")

For the complete series of 13 Spatial tutorial articles search on "Dave does Data". or use this URL "http: blogs.msdn.com b davidlean archive 2008 11 01 sql-2008-spatial-samples-part-1-of-9-how-to-learn-sql-spatial.aspx" It didn't like me posting this URL so put a slash where each or the space characters are.

Blog Archive