QGIS Path – Building the Shortest Path Between Two Points Inside Polygon Using QGIS

Question

With QGIS I need to build the shortest route between two points inside a polygon. I have a vector polygon layer and I need to build a path inside it from the starting point to the ending point. How can I do this?

I found that the vector layer needs to be rasterized, but I don’t understand what to do next. Existing tools are based on vector line layers. I studied so much information and nothing helps. I would write a Python module or use ready modules.

Answer 1

There are probably better approaches available, however I am suggesting the following intuitive workaround for Vector Data.

Let's assume there is a point layer (two features), and a polygon layer (one feature), see the image below.

Step 1. Apply the "Polygon Divider" plugin to break the original polygon feature into pieces of equal areas. Alternatively, one can use the "Create grid" geoalgorithm and overlap it with the initial polygon feature

Step 2. Select all objects from the previous output, without overlap with original points. Afterward, get "Centroids" for the selected pieces only

Step 3. "Extract vertices" of the original polygon

Step 4. Merge original points with outcomes of Steps 2 and 3 with the "Merge vector layers" tool

On this step it is vital to mention, that the next approach should be chosen wisely, depending on precision/tolerance/complexity etc.

---

Approach #1

Step 5. Triangulate points with the "Voronyi/Delaunay triangulation"

Step 6. "Extract by location" triangles, that are within the original polygon

Step 7. Convert these triangles to polylines, with "Polygons to lines"

Step 8. "Explode lines" from the previous step, and also "Delete duplicate geometries"

Step 9. Apply the "Shortest path (point to point)" and get the output like this:

Simplify and/or smooth if needed.

---

Approach #2

Step 5. Use the "Geometry by expression" together with this expression:

collect_geometries(
    array_filter(
        array_foreach(
            overlay_nearest(
                layer:='points_to_test', -- change accordingly
                expression:=@geometry,
                limit:=10 -- adjust properly
                ),
            make_line($geometry, @element)
            ),
        within(@element, aggregate(
                                layer:='polygon', -- change accordingly
                                aggregate:='collect',
                                expression:=$geometry
                                )
            )
        )
    )

Step 6. "Multipart to singleparts", and if required "Delete duplicate geometries"

Step7. Apply the "Shortest path (point to point)" and get the output like this:

Simplify and/or smooth if needed.

---

Approach #3

Step 5. Create all possible line connections between merged points like in this tread Creating all possible line segments between all points using QGIS. And after extract only hub lines that are within the original polygon. Do not forget about the spatial index. And also be careful with polygon edges, do not skip them. Apply the "Multipart to singleparts" if needed

Step 6. Apply the "Shortest path (point to point)" and get the output like this:

---

Once can also compare the results in the end. With some pros&cons one will find a suitable approach.

---

Notes:

• for the Step 1 the area value has to be chosen wisely
• this workflow was only performed on a single polygon and two points, not multiple inputs of each layer
• this workflow can be converted into a QGIS-model or pure PyQGIS code for automized routine work
• mind some issues, that could happen. This one evoked after diving the polygon
• In the first approach, triangulation result may not always correspond to the initial polygon
• In the second approach, some polygon sides can be skipped'

---

References:

• Splitting all lines in layer at vertices using QGIS