top of page
  • alikilic9

How to Do Shortest Path Analysis With Own Data Using PostGIS

Updated: Nov 2, 2021

With this blog post, I tried to explain to you how to do this if you want the shortest path analysis with your own data in cases where you cannot use the Routing API feature, which is one of the Google and OSM Services.

1- Spatial Data Quality and Topological Relation

We store the road, natural gas pipeline, water channels, fiber optic cables, power transmission lines and similar objects that we define as geometric objects within the scope of Geographic Information Systems in our database as LineString geometry type.

The real data collected from the field is simplified and brought into a situation where spatial relations can be established with each other. In GIS, this relationship is called topological relationship and may vary according to different studies.

In network analyses, LineString geometries should not be related by any same geometry table from anywhere except the first and last point. It is important to eliminate errors because such relationships prevent the topological relationship from being healthy. In the picture below, you'll see a small part of a road line. Although it is very difficult to notice the topological error as the scale gets smaller in this picture, when you get closer to the connection points, it will be very easy to realize that the wrong topological relationship is established.

What it should be is the square in blue. The difference between the two examples; While the objects in the blue box are connected to each other in a snapped at the same point, in the red example these are not fully close with the linestring.

Apart from this, a second rule is; The topological relationship segments that should be included in the network analysis should be insert correctly. An A line may have other B lines connecting along its length. In this case, snap to the endpoint or startpoint of line B where line A snap to line B. Line A continues on own way again. You can see an example of this in the picture below.

In the picture above, the green Line is the A line, and the blue lines are named the B lines. I named their fragmented Lines as segments. The yellow dots in the graph mean the first and last vertex points of the lines. As you can see, if you need to understand the error in this picture; There is no vertex point to be snapped in the area surrounded by the red box. In order to eliminate such situations, you should bring the non-snapped ends together, or even break the non-segmented linestrings and bring them together with the ends of the other linestrings. You can read my articles below to resolve such errors with some database queries.

1 - Splitting Geometries from Vertex Points with PostGIS

2 - Splitting Lines With Intersecting Points Using PostGIS

If you think your existing data is suitable for network analysis, you can experiment with your own data. Apart from that, if you don't have any data for testing, I put a file for you to download. There are geojson, kml, shp and sql files named "Patika" in it. However, in this post, I want to teach the more important parts by using the patika.sql file.

Download ZIP • 20KB

2 - Installing PostGIS and PgRouting Plugins

It asks you which add-ons you want to install in the PostgreSQL installation, but perhaps you may not have passed this step quickly and installed it. In this case, the procedures you need to do are very easy and effortless. It will be enough to run pgAdmin and open the Query Tool in the database where you will add the geometry and run the following SQL codes.

When you run these codes, you will get the result "Query returned successfully". If it is already installed it will let you know. In addition, if there is a problem with your plugins, you can visit PostGIS Installation and PgRouting Installation pages for detailed installation information.

3 - Adding Spatial Data to the Database

You can open the patika.sql file in the zip file I gave you with a text editor and browse the SQL codes in it. Using the GISLayer WebGIS Editor that I prepared while creating these files, I exported the geometries as sql files suitable for postgresql and shared them to you. If you wish, you can also use this site to create your own road data and download and add it to your database. If you want to learn how to do it, you can read it from this link or you can watch it on Youtube by clicking this link.

It represents the patika.sql file that I have shared to you with the code below.

  • 1. line, i create the sequence for the primary key

  • created the patika db table between 2-4

  • I added geometric column at 5. line

  • In the 6th line, we create a spatial index. It is a feature that will speed up especially in large tables.

  • All the lines below are SQL insert codes that help you insert the geometries in WKT format

4 - Defining Segments Node Numbers

At this stage, we need to create two new columns where we can assign the node numbers according to the start and end of the lines with a topological relationship. The following SQL codes will help you add the source and target columns to the path table and create an index.

You need to get the CREATE INDEX result by running these codes in the Query Tool.

5- Starting Topological Relation Analyzes

We need to establish the topological relationship between the lines by using the pgr_createTopology function in PgRouting. The parameters of this function are in order; table name, tolerance (I recommend 0.0001), name of geometric column, primary key name of the table. When all this comes together, it will be enough to write a simple query like the following.

After running the code, you should see OK output. Also, a new table named patika_vertices_pgr will be created in your database based on your table name. If you don't get this result, there is a issue with your topological relationship. You need to fix the topological problems and try again.

6 - Finding the Shortest Path Between Start and Finish Points

You are now ready to query. Using Dijkstra's shortest path algorithm, we will write the SQL code that will allow you to find the shortest path that exists between two points with the pgr_dijkstra function. The view of our patika spatial table on the field is as follows. We will try to find the shortest path between the two yellow dots with the SQL we will write.

Coordinate of the point in the green box: POINT(27.00232 39.23222)

Coordinate of the point in the red box: POINT(27.01509 39.23592)

We use the following query to find which linestring the yellow dot in the green box is close to

You can also do this for the red Point and find the closest line, but this will not be necessary. You can find all segments in order by entering the coordinate information of your first and last point together with the SQL code I will give below.

After running the above code, it will give you an output like the one below. If I need to mention the columns in this output, respectively; seq is the row number, the node is the node number of the road where the node is located, the edge is the node number of the road to reach, cost is the length of the current road, agg_cost is the total path length in each step, geom is the geometry of your segments.

If you wish, you can run this query and produce a GeoJSON output by putting the SQL above where I wrote XXX below to get a full GeoJSON output.

You can copy the GeoJSON output from this query and add it to a file named shortestpath.geojson and use it. I am sharing the file of the result I got from the query below.

Download ZIP • 1KB

If you open the GISLayer Web Editor and extract the file from the zip and drop it on the map with drag and drop method, the green line below will be displayed on the map. You can change these colors as you wish.

Now, as a result, the operation seems to be successful, but we cannot say that it gave a 100% correct result because some paths could not be linked to topology. However, we can say that it worked correctly.

I hope this post was useful for you.

bottom of page