1

I'm new to qgis and in here I want to find a path between two selected points on the map(Roads-vector layer). The points are selected by the user, using mouse clicks.

So here I used the astar algorithm to find path between two points.

*********************************astar.py************************************
import heapq

class AStar(object):
def init(self, graphAstar):
self.graphAstar = graphAstar

def heuristic(self, node, start, end):
    raise NotImplementedError

def search(self, start, end):
openset = set()
    closedset = set()
    current = start
    openHeap = []
    openset.add(current)
    openHeap.append((0,current))
    while openset:
    temp = heapq.heappop(openHeap)
    current = temp[1]
        if current == end:
            path = []
            while current.parent:
                path.append(current)
                current = current.parent
            path.append(current)
            return path[::-1]
        openset.remove(current)
        closedset.add(current)
        for node in self.graphAstar[current]:
            if node in closedset:
                continue
            if node in openset:
                new_g = current.gg + current.move_cost(node)
                if node.gg > new_g:
                    node.gg = new_g
                    node.parent = current
            else:
                node.gg = current.gg + current.move_cost(node)
                node.H = self.heuristic(node, start, end)
                node.parent = current
                openset.add(node)
        heapq.heappush(openHeap, (node.H,node))
    return None


class AStarNode(object):
    def __init__(self):
        self.gg = 0
        self.H = 0
        self.parent = None

    def move_cost(self, other):
        raise NotImplementedError

*****************************astar_grid.py*******************************

from astar import AStar, AStarNode
from math import sqrt

class AStarGrid(AStar):
    def heuristic(self, node, start, end):
        return sqrt((end.x - node.x)**2 + (end.y - node.y)**2)

class AStarGridNode(AStarNode):
    def __init__(self, x, y):
        self.x, self.y = x, y
        super(AStarGridNode, self).__init__()

    def move_cost(self, other):
        diagonal = abs(self.x - other.x) == 1 and abs(self.y - other.y) == 1
        return 14 if diagonal else 10

and in the main code, the following method is used to create graph from vector layer.

****************************plugin.py************************************

def make_graph(self, mapinfo):
    nodes = [[AStarGridNode(x, y) for y in range(mapinfo['height'])] for x in range(mapinfo['width'])]
    graphAstar = {}
    for x, y in product(range(mapinfo['width']), range(mapinfo['height'])):
        node = nodes[x][y]
        graphAstar[node] = []
        for i, j in product([-1, 0, 1], [-1, 0, 1]):
                if not (0 <= x + i < mapinfo['width']): continue
                if not (0 <= y + j < mapinfo['height']): continue
                graphAstar[nodes[x][y]].append(nodes[x+i][y+j])
    return graphAstar, nodes

And I called that method in FindRoutes method..

def findRoutes(self):
# QMessageBox.information( self.iface.mainWindow(),"Info", "in findRoutes function" )
# vl = qgis.utils.iface.mapCanvas().currentLayer()
vl=self.canvas.currentLayer()
director = QgsLineVectorLayerDirector( vl, -1, '', '', '', 3 )
properter = QgsDistanceArcProperter()
director.addProperter( properter )
# crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
crs = self.canvas.mapRenderer().destinationCrs()
builder = QgsGraphBuilder( crs )

global x1
global y1
global x2
global y2
pStart = QgsPoint( x1, y1 )
pStop = QgsPoint( x2, y2 )
graphAstar, nodes = self.make_graph({ "width": 8, "height": 8 })
paths = AStarGrid(graphAstar)

start, end = ??
path = paths.search(start, end)

How do I pass the start and end coordinates to the function above?

Passing them just as coordinates (start, end = pStart, pStop) does not work.

How do add them to the graph created as nodes?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.