Add nodes into graph- Pathfinding

[Dil]

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)

My question is, how to pass the start and end coordinates to the function above? Because passing them just as coordinates (start, end = pStart, pStop) does not work.

How do add them to the graph created as nodes?

Or is there any easy way to do it?

Please help me to to find a solution to this problem.

Thank You

[Tim Sutton]

Hi Dil

Can you clarify what you actually need? A way for the user to interactively define points on the map?

Regards

--
Visit the InaSAFE project page at http://inasafe.org
Let us know of any issues you encounter at: https://github.com/AIFDR/inasafe/issues
---
You received this message because you are subscribed to the Google Groups "inasafe-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to inasafe-user...@googlegroups.com.
To post to this group, send email to inasaf...@googlegroups.com.
Visit this group at http://groups.google.com/group/inasafe-users.
To view this discussion on the web visit https://groups.google.com/d/msgid/inasafe-users/33c655da-f4ea-4c6b-8480-0d565751f09f%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Tim Sutton

-------------------------------------------------------------------------------------------

Visit http://linfiniti.com to find out about:
 * QGIS programming services
 * GeoDjango web development

 * QGIS Training
 * FOSS Consulting Services
Skype: timlinux Irc: timlinux on #qgis at freenode.net

Tim is a member of the QGIS Project Steering Committee
-------------------------------------------------------------------------------------------

[Dil]

Thank you for the reply. Sir I'm building a plugin and identifying available paths between two points, is one part of it. Actually I want to find the possible available routes between two points in map,when a disaster occurred and roads have been blocked due to disaster. And the identified routes should be less than or equal to a specified distance.(to reduce the findings) For example, highlighting the available roads(paths) between point A and point B which are less than 5km (if available). And the two points are selected by the user on map, using mouse clicks.
So to do that I thought to use astar algorithm, to atleast find one possible path between selected points on map.(Since I couldn't find any other way to do what I actually need)
So I used the coding above to do it and stuck in the middle.
Sir is there any another way to achieve what I need?
Thank You 

[Tim Sutton]

Hi

On Tue, May 27, 2014 at 7:39 AM, Dil <dilvit...@gmail.com> wrote:

Thank you for the reply. Sir I'm building a plugin and identifying available paths between two points, is one part of it. Actually I want to find the possible available routes between two points in map,when a disaster occurred and roads have been blocked due to disaster. And the identified routes should be less than or equal to a specified distance.(to reduce the findings) For example, highlighting the available roads(paths) between point A and point B which are less than 5km (if available). And the two points are selected by the user on map, using mouse clicks.
So to do that I thought to use astar algorithm, to atleast find one possible path between selected points on map.(Since I couldn't find any other way to do what I actually need)
So I used the coding above to do it and stuck in the middle.
Sir is there any another way to achieve what I need?

Ok see my other email for a pointer to the API docs on using the network analysis library in QGIS. You will need to do some research into approaches you could take if you want to find multiple candidate routes (not just the single shortest route). Dil I would be very interested to incorporate your work in InaSAFE itself as we have on the project roadmap the intention to add route finding tools between affected people and IDP camps. Please keep in touch via this list and we can collaborate to include your work directly into InaSAFE if possible.

Regards

Tim

 

--
Visit the InaSAFE project page at http://inasafe.org
Let us know of any issues you encounter at: https://github.com/AIFDR/inasafe/issues
---
You received this message because you are subscribed to the Google Groups "inasafe-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to inasafe-user...@googlegroups.com.
To post to this group, send email to inasaf...@googlegroups.com.
Visit this group at http://groups.google.com/group/inasafe-users.

To view this discussion on the web visit https://groups.google.com/d/msgid/inasafe-users/fe3e92c8-eede-47b9-9c6b-6237f3a3752d%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.