T-SQL Tuesday 2 Spatial Puzzles
SQLBlog blogger Adam Machanic recently posted an invitation for people to contribute articles on the subject of "puzzling" T-SQL, as part of T-SQL Tuesday.
I thought that it might be interesting to use the SQL Server 2008 spatial datatypes to demonstrate and solve two fairly well-known puzzles that I remember from my childhood... the first is a visual puzzle, for which I'll be using the geometry datatype; and the second is a riddle/logic puzzle, in which I'll be calling upon the geography datatype. I hope that you enjoy them.
Puzzle #1: The Disappearing SquareThis puzzle uses a variety of methods of the geometry datatype, and the the Spatial Results tab of SQL Server Management Studio. SQL Server 2008 only!
The PuzzleTo demonstrate this puzzle, first of all create a table and insert four simple geometry shapes into it, as follows:
DECLARE @table1 TABLE( id CHAR(1), shape geometry ); INSERT INTO @table1 VALUES ('A','POLYGON((0 0, 8 0, 8 3, 0 0))'), ('B','POLYGON((8 0, 13 0, 13 2, 10 2, 10 1, 8 1, 8 0))'), ('C','POLYGON((8 3, 8 1, 10 1, 10 2, 13 2, 13 3, 8 3))'), ('D','POLYGON((8 3, 13 3, 13 5, 8 3))');
SELECT id, shape FROM @table1;
DECLARE @table2 TABLE ( id CHAR(1), shape geometry ); INSERT INTO @table2 VALUES ('A','POLYGON((5 2, 13 2, 13 5, 5 2))'), ('B','POLYGON((8 0, 13 0, 13 2, 10 2, 10 1, 8 1, 8 0))'), ('C','POLYGON((5 2, 5 0, 7 0, 7 1, 10 1, 10 2, 5 2))'), ('D','POLYGON((0 0, 5 0, 5 2, 0 0))'); SELECT id, shape FROM @table2;
Note that all of these shapes are identical to those used in the first example - they've just been rearranged. However, the triangle formed when the pieces are fitted together now contains a "hole" - 1 unit wide by 1 unit high.So, where has the hole appeared from, and what is missing?
The SolutionThe area of a right-angled triangle can be calculated as half of the base multiplied by the height. Both 'triangles' appear to be 13 units wide x 5 units high, so we would expect them to have an area of 32.5 units. Let's test this:
SELECT SUM(shape.STArea()) FROM @table1; SELECT SUM(shape.STArea()) FROM @table2;
The total area of the individual shapes contained in both triangles is the same - 32 units. So the area of the bottom triangle, when including the 'missing' one unit square, is 33 units.
In other words, although the two triangles appear similar, they are not the same, and neither one is the 13x5 right-angled triangle they appear to be. The first triangle is slightly smaller, and the second triangle is slightly larger.
To investigate further, we can find the difference between these triangles and the "true" 13 x 5 right-angled triangle defined as follows:
DECLARE @truetriangle geometry = geometry::STPolyFromText('POLYGON((0 0, 13 0, 13 5, 0 0))', 0);
We can find the difference by first creating a union aggregate of all the shapes in each table, and then comparing this to the true triangle using the STSymDifference method (note I use the STConvexHull() method on the second triangle in order to fill in the missing 'hole'):
-- Create union of all individual shapes in first table DECLARE @triangle1 geometry = 'GEOMETRYCOLLECTION EMPTY'; SELECT @triangle1 = @triangle1.STUnion(shape) FROM @table1; -- Create union of all individual shapes in second table (filling in the gap) DECLARE @triangle2 geometry = 'GEOMETRYCOLLECTION EMPTY'; SELECT @triangle2 = @triangle2.STUnion(shape).STConvexHull() FROM @table2; -- Work out the difference from a true 13 x 5 triangle SELECT @triangle2.STDifference(@truetriangle) UNION ALL SELECT @truetriangle.STDifference(@triangle1);
The results illustrate two thin slivers of area where the two shapes differ from the true triangle, lying along the hypoteneuse. While both shapes appear to be right-angled triangles, they are in fact polygons, since the hypotenuese of each is not a straight line. You can check this by calling STNumPoints() on both @triangle1 and @triangle2.
The hypoteneuse of the first triangle is slightly concave, hence why the area is only 32 units and not 32.5 units as expected. The hypoteneuse of the second triangle is slightly convex, leading to a total area of 33 units (which, when you subtract the 1 unit 'missing' square, gives the same total shape area of 32 units).
The illusion is caused by the fact that the gradients of the component triangles A and D are not the same, therefore swapping them over affects the overall area of the shape. However, they are similar enough that your brain doesn't perceive the difference between them, and assumes that you're looking at a right-angled triangle in both cases.
Puzzle #2: The HunterThis logic puzzle relates to moving around on the surface of the earth, which makes it ideal to demonstrate some of the methods of the geography datatype.
The PuzzleThere seem to be several variations on this puzzle, but the version I know is as follows: "A hunter starts at a location. He walks one mile south, one mile east, and then one mile north. He ends up back where he started, and sees a bear. What colour is the bear?"
Before worrying about the colour of the bear, we need to resolve the apparent paradox in the positioning of the hunter. He has moved one mile south, one mile east, and one mile north, and ended up back where he started. Where could he have been in order for this to be true?
The commonly-known answer is that the hunter started at the North Pole, the bear is therefore a Polar bear and is white (don't let it worry you that there are no polar bears at the north pole!). Let's test whether this answer fits the criteria using the geography datatype.
Firsty, we define the start point, @p0, at the North Pole. All lines of longitude converge at the North Pole, so I'll use an arbitrary longitude value of 0:
DECLARE @p0 geography = geography::Point(90, 0, 4326);
We now need to declare another point, @p1, one mile due South of the start.
- Travelling south reduces latitude, so @p1.Lat < @p0.Lat.
- Travelling due south involves maintaining a constant longitude, so @p1.Long = @p0.Long.
- The coordinates in this example use SRID 4326, so the results of any linear calculations are stated in metres. 1 mile = 1,609 metres (approx.), so we need @p0.STDistance(@p1) = 1609.
Solving these criteria leads to the following point:
We can check that this point does indeed meet the criteria as follows:
DECLARE @p1 geography = geography::Point(89.98559, 0, 4326);
SELECT CASE WHEN @p1.Lat < @p0.Lat AND @p1.Long = @p0.Long THEN 'p1 lies due south of p0' END, CASE CAST(@p0.STDistance(@p1) AS INT) WHEN 1609 THEN 'p1 lies one mile from p0' END;
The next point needs to lie one mile due east of @p1. Therefore, it must lie on the same latitude as @p1, but have a greater longitude (assuming that the antimeridian is not crossed). Using the same logic for the previous point, we can deduce that this point lies at:
DECLARE @p2 geography = geography::Point(89.98559, 60, 4326);
Finally, we need to establish the final point, @pf, which must lie one mile due north of the last point. To meet the final criteria of the puzzle, this point must be the same as the point at which the hunter stated, so @pf = @p0. We can test this in the following code:
DECLARE @pf geography = geography::Point(90, 60, 4326); SELECT CASE WHEN @pf.Lat > @p2.Lat AND @pf.Long = @p2.Long THEN 'pf lies due north of p2' END, CASE CAST(@pf.STDistance(@p2) AS INT) WHEN 1609 THEN 'pf lies one mile from p2' END, CASE WHEN @p0.STEquals(@pf) = 1 THEN 'pf is the same as p0' END;
Using the methods of the geography datatype, we have proven that the North Pole is a valid solution to this puzzle. However, it is not the only solution - there are, in fact, an infinite number of locations on the earth's surface that would meet the criteria of the puzzle...
...Consider the second step of the hunter's journey - walking due east along a parallel of the earth - a line of constant latitude. As you approach the poles, the circumference of the parallels of the earth become increasingly smaller. Starting at a point just north of the south pole, it is possible to walk east right around the earth along a circle that is one mile in circumference. This occurs at a latitude of about -89.9977, as can be shown by the following:
DECLARE @linestring geography = geography::STLineFromText(' LINESTRING( 0 -89.9977, 15 -89.9977, 30 -89.9977, 45 -89.9977, 60 -89.9977, 75 -89.9977, 90 -89.9977, 105 -89.9977, 115 -89.9977, 120 -89.9977, 135 -89.9977, 150 -89.9977, 165 -89.9977, 180 -89.9977, 195 -89.9977, 200 -89.9977, 210 -89.9977, 225 -89.9977, 240 -89.9977, 255 -89.9977, 270 -89.9977, 285 -89.9977, 300 -89.9977, 315 -89.9977, 330 -89.9977, 345 -89.9977, 360 -89.9977 ) ', 4326); SELECT @linestring, @linestring.STLength();
This linestring is 1,609 metres long - one mile, but follows a line of constant latitude right around the earth. So, if the hunter starts at any point that is one mile north of this line, they would first walk one mile south onto the line, then one mile east along the line (taking them once around the earth), and finally one mile north again to return to their original starting point.
The following code illustrates an example of just one such point that lies one mile north of the line:
DECLARE @z geography = geography::Point(-89.98329, 0, 4326); SELECT @z.STDistance(@linestring);
In fact, not only are there an infinite number of points that lie one mile north of this line that satisfy the puzzle, but there are also an infinite number of lines along which it can be done: Consider the line that goes around the South pole that is 1/2 mile in length, for example, or 1/3 mile. Walking due east for one mile along any of these lines will take you on some number of rotations of the earth but always return you to the starting point. In all these cases, the middle step of "walking due east for one mile" effectively becomes nullified, leaving the puzzle as walking due south for one mile and then due north for one mile, which clearly returns you to the start location.