1

I need to find the path inside a polygon. It should be the equidistant path from the polygon boundaries. Unfortunately I can't rasterize the polygon. I thought it would be possible to construct a visibility graph from various points within the polygon. Then calculate the weight of its edges based on distance from the polygon boundary and apply Dijkstra algorythm to find the path. But I have no idea how to calculate a weight for graph edges. For the shortest path is a distance between the xy coordinates of start and end nodes. But what is it for the equidistant path from the polygon boundaries? I could calculate distance from the graph nodes to the closest point of a polygon boundary by geometry expression but seems the difference of this distances for two points is not the weight of a graph edge. May be somebody can help me?

The target part looks like this: enter image description here

A created a lot of points inside a polygon and then I connected then with edges (green edges): enter image description here

I used such geometry expression to calculate the distance of a point from the boundaries of the polygon:

cost = 1/distance($geometry,closest_point (overlay_within('polygon', boundary($geometry))[0], $geometry))

Then I tried to calculate weight of edge like this

weight = abs(G.nodes[node1]['cost'] - G.nodes[node2]['cost'])

and used Dijkstra’s algorithm but it works bad (red line): enter image description here

PolyGeo
  • 65,136
  • 29
  • 109
  • 338
redhat
  • 347
  • 6
  • 2
    Densify polygon boundaries. Compute voronoi polygons of vertices. Clip by parent polygon. Convert to lines. Delete lines that share line segment with polygon outline. Compute path between 2 points – FelixIP Jan 21 '24 at 19:11
  • 1
    Why can't you rasterize the polygon? Did you have a look here? https://gis.stackexchange.com/a/474196/88814 – Babel Jan 21 '24 at 19:19
  • Yes, it'is great way, but I need to understand how the least path plugin works and I don't. I understood that it is Dijkstra's algorithm with Manhattan distance (like A* algorithm). And it means that this plugin uses a graph. But how it calculates weights of edges with color and distance I really don't understand even with the plugin. And I tried to figure out it by building my own graph but I failed – redhat Jan 21 '24 at 19:34
  • And I wrote that I cannot rasterize it because now I need to figure out how it works – redhat Jan 21 '24 at 19:55
  • 2
    You can try with a medial axis - a concept of point set theory basically covering your scenario. Might not be exactly what you want, though. – geozelot Jan 21 '24 at 20:31
  • 1
    See help how to rasterize, it's quite easy: https://docs.qgis.org/3.34/en/docs/user_manual/processing_algs/gdal/vectorconversion.html#gdalrasterize And the answer linked above explains in detail how to proceed. – Babel Jan 22 '24 at 08:40
  • 1
    Just saying, if equidistancy is the key weight here, a respective most cost efficient path between any two non-'adjacent' points inside the polygon must be along the medial axis. – geozelot Jan 22 '24 at 09:43
  • @FelixIP Do you have any idea how to add start and end points into a Voronoi graph (if they don't lay on a middle line of Voronoi Diagram)? I almost draw a graph using Voronoi diagram but I don't know how to add them into a graph – redhat Jan 23 '24 at 16:52
  • 1
    Project points onto nearest edge and split edges at this points. This will add 6 edges to graph and 4 nodes. – FelixIP Jan 23 '24 at 18:46
  • @FelizIP Could you explain more how to project points? I'm new in QGIS and I know tools not so well. – redhat Jan 24 '24 at 18:09
  • 1
    https://gis.stackexchange.com/a/246551/156742 – Fee Jan 25 '24 at 03:17

0 Answers0