This is part three in a series:
- Part 1, Introduction
- Part 2, Local Data
- Part 3, Getting Around
- Part 4, Data Sets
- Part 5, Resources
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.