CODEWITHSUNDEEP
algorithmsearchgraphpath-finding
Keyur Mahajan
Keyur Mahajan

Reputation: 134

Considering Start point and end point on edge, not Node of graph in Path finding algorithm for Road Network Graph

I am working on Path finding algorithm for Road Network. I have details of my road network as undirected graph in db with Node(id,cordinate) and Edge(id,start-node-id, end-node-id,line-points) table. I am using A* path finding algorithm to compute path between given two nodes.

User will select any location on map, which can not be exact node location, so I am finding nearest node from user selected location on map to calculate start node and end node on graph and running algorithm between these two points of graph.

Now my problem is when user select location on map which is at the middle of any edge, it is selecting nearest node and then starting path finding algorithm. Instead i want algorithm to start from edge itself, instead of nearest node. So when user select location on map, it will see if any edge(road) is near, then it will select that nearest point on edge(which is not node) and calculate the path. How should i approach this problem?

Upvotes: 2

Views: 1810

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86126

Insert an artificial node in the graph representing the user's start point, and connect it to the two endpoints of that edge.

Upvotes: 0

Related Questions