Spatial Data, Part 3: Getting Around

This is part three in a series:

Now that we have some local buildings represented in our database, let’s move around.

Getting Around

0. Get the Buildings

In the last step of Part 2, we saved three buildings into temp tables — #orig, #bloc, and #dest.

1. Shortest Path

select geom from #orig union all select geom from #dest union all select geom from #bloc union all
select (select geom from #orig).ShortestLineTo((select geom from #dest))

Let’s Find the Shortest Path to that Condemned Building.

The .ShortestLineTo method will find the shortest path, even taking into account the shapes of the buildings.

But it doesn’t care about any obstacles in its path, which is why we also stored that blocking building to continue our experiment.

2. Put an Envelope on the Obstacle

select (select geom from #bloc).STEnvelope().STBoundary()
union all select geom from #orig union all select geom from #dest union all select geom from #bloc

An envelope will look at the highest and lowest values for the height and the width of an object, and draw a box using those values. We can use this to help find a path around the obstacle.

3. Draw the Corners of the Envelope

select geom from #orig union all select geom from #dest union all select geom from #bloc union all
select geometry::Point((select geom from #bloc).STEnvelope().STPointN((1)).STX, (select geom from #bloc).STEnvelope().STPointN((3)).STY, 0).STBuffer(.0001) union all
select geometry::Point((select geom from #bloc).STEnvelope().STPointN((3)).STX, (select geom from #bloc).STEnvelope().STPointN((3)).STY, 0).STBuffer(.0001) union all
select geometry::Point((select geom from #bloc).STEnvelope().STPointN((3)).STX, (select geom from #bloc).STEnvelope().STPointN((1)).STY, 0).STBuffer(.0001) union all
select geometry::Point((select geom from #bloc).STEnvelope().STPointN((1)).STX, (select geom from #bloc).STEnvelope().STPointN((1)).STY, 0).STBuffer(.0001)

This command illustrates where the corners of that envelope are. After all, we don’t really want the entire envelope to find a way around the obstacle, just the endpoints.

4. Save Those Corners

if object_id('tempdb.dbo.#corn', 'u') is not null drop table #corn create table #corn (geom geometry)
insert into #corn
select geometry::Point(geom.STEnvelope().STPointN((1)).STX, geom.STEnvelope().STPointN((3)).STY, 0) from #bloc
union all
select geometry::Point(geom.STEnvelope().STPointN((3)).STX, geom.STEnvelope().STPointN((3)).STY, 0) from #bloc
union all
select geometry::Point(geom.STEnvelope().STPointN((3)).STX, geom.STEnvelope().STPointN((1)).STY, 0) from #bloc
union all
select geometry::Point(geom.STEnvelope().STPointN((1)).STX, geom.STEnvelope().STPointN((1)).STY, 0) from #bloc

Let’s save those into some temp tables, too, to make the following statements a bit easier to read.

5. Paths to the Corners

select geom from #orig union all select geom from #dest union all select geom from #bloc union all
select o.geom.ShortestLineTo(c.geom).STBuffer(.00001) from #orig o left outer join #corn c on 1=1

Being a method, the .ShortestLineTo can be applied to as many shapes (or points) that we want to give it, all in a single command.

By putting the corners into a temp table, we can draw all four lines at once.

6. Eliminate Overlaps

select geom from #orig union all select geom from #dest union all select geom from #bloc union all
select o.geom.ShortestLineTo(c.geom).STBuffer(.00001)
from #orig o left outer join #corn c on 1=1 left outer join #bloc b on 1=1
where o.geom.ShortestLineTo(c.geom).STIntersects(b.geom)=0

One of those paths goes through the building, which isn’t any help in getting around it. So by added a where clause so that .STIntersects is false, we only see the lines that don’t collide with the building.

Cool! We’re halfway there.

7. Add the Destination

select geom from #orig union all select geom from #dest union all select geom from #bloc union all
select o.geom.ShortestLineTo(c.geom).STUnion(c.geom.ShortestLineTo(d.geom)).STBuffer(.00001)
from #orig o left outer join #corn c on 1=1 left outer join #bloc b on 1=1 left outer join #dest d on 1=1
where o.geom.ShortestLineTo(c.geom).STIntersects(b.geom)=0
and c.geom.ShortestLineTo(d.geom).STIntersects(b.geom)=0

Since those three valid paths are also just geometric data objects, we can use them as the new “origin” for the next leg of our journey.

So, by finding the shortest lines from those lines to the destination building, joining the two line segments into a single object with the .STUnion method, we get:

If we were to apply the .STDistance() method to those paths, we’d see that the purplish path is 4.732 meters, and the blueish path is 5.055 meters.

Shortest Path

Typically, of course, the shortest path problem is focused on roads, not taking shortcuts through the grass.

That’s already been solved in a variety of ways. The most common approach is Dijkstra’s Algorithm.

Here are a couple of SQL implementations: one from Peter Larsson, and one from Hans Olav.

The key to making it quick is generally to pre-calculate all the distances. To a point. Computers these days can’t store the distance from every point on Earth to every other point on Earth, any more than every possible chess move on every board.

#corn