LinuxQuestions.org
Visit the LQ Articles and Editorials section
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
LinkBack Search this Thread
Old 01-05-2013, 07:51 AM   #1
resetreset
Senior Member
 
Registered: Mar 2008
Location: India
Distribution: Dynebolic, Ubuntu 10.10
Posts: 1,320

Rep: Reputation: 51
How to find the shortest path between 2 points on a map?


If a user picks out their own position on a Google map (say), I'd like to figure the shortest path to another, particular point on the map.

I've been trying to figure this out, the idea that occurred to me was to break curves into small straight lines, but really not much more than that. (no idea even on how to measure the LENGTH of the lines after that! - er that'd be Pythagoras' theorem, right?)

Any heads on LQ wanna weigh in?

Last edited by resetreset; 01-05-2013 at 07:54 AM.
 
Old 01-05-2013, 09:05 AM   #2
business_kid
Guru
 
Registered: Jan 2006
Location: Ireland
Distribution: Slackware & Android
Posts: 5,953

Rep: Reputation: 496Reputation: 496Reputation: 496Reputation: 496Reputation: 496
It's messy and complicated. There's one way streets. The shortest way in Ireland is often not the quickest way. In Ireland some of the big roads have the traffic but have QBCs (Quality Bus Corridors), which are lanes where only buses, bikes, and taxis are allowed. These operate near rush hour. Traffic lights abound, and are set randomly. Some short cuts (known as 'rat runs') have regular ramps of various sizes to prevent old people and kids from being mowed down by teenagers with 2 feet on the throttle. We drive on the left, so right turns are often limited. So the fastest routes are the routes where you can keep going.

Take all that stuff into account, and you'll do all right.
 
Old 01-05-2013, 10:02 AM   #3
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Ubuntu
Posts: 1,032

Rep: Reputation: 275Reputation: 275Reputation: 275
Quote:
Originally Posted by resetreset View Post
If a user picks out their own position on a Google map (say), I'd like to figure the shortest path to another, particular point on the map.
Everything said by business_kid is correct, for travel by road. Google Maps offers travel directions (for my part of the world) in four flavors: car, public transportation, bicycling, walking. Click on "walking" and you are likely to get the shortest path, other than a straight-line overland route.

Daniel B. Martin
 
Old 01-05-2013, 10:07 AM   #4
smallpond
Senior Member
 
Registered: Feb 2011
Location: Massachusetts, USA
Distribution: Fedora
Posts: 1,163

Rep: Reputation: 258Reputation: 258Reputation: 258
Pittsburgh is so hilly that you have to consider 3 dimensions. Some streets right next to each other on the map are 200' apart vertically, so it can be very difficult even for a native to give directions.
 
Old 01-06-2013, 12:58 AM   #5
resetreset
Senior Member
 
Registered: Mar 2008
Location: India
Distribution: Dynebolic, Ubuntu 10.10
Posts: 1,320

Original Poster
Rep: Reputation: 51
None of you are talking about the ALGORITHM!

Is there any way for a program to access the Google Map "walking" data?
 
Old 01-06-2013, 04:29 AM   #6
whizje
Member
 
Registered: Sep 2008
Location: The Netherlands
Distribution: Slackware64 current
Posts: 582

Rep: Reputation: 129Reputation: 129
Maybe the google maps api helps https://developers.google.com/maps/?hl=nl
 
Old 01-06-2013, 08:57 AM   #7
business_kid
Guru
 
Registered: Jan 2006
Location: Ireland
Distribution: Slackware & Android
Posts: 5,953

Rep: Reputation: 496Reputation: 496Reputation: 496Reputation: 496Reputation: 496
@smallpond: 200 feet? Wow. We have a place or two, Enniscorthy in Wexford is one that comes to mind, where they were built on the side of a hill. I stayed overnight with a motorbike and couldn't park outside the B&B. It just wouldn't hold on the stand.

The fact is, any algorithm or system fails to satisfy all. Listen to the stories about GPS devices.
Min has 'shortest distance,' or fastest route. I gather it thinks you do 500kmh on a motorway, because 'fastest route' it sends you by the main road to the motorway, and by the main road from the motorway. Shortest distance is suicidal outside the city limits. I got sent up farm entrances because it thought there was a way through the farmyard!

Google Maps sens me the most direct and SLOWEST way on a journey I do several times a week. I chug through villages with loads of traffic lights stacked against you, onto the longest queue in the area. Mind you Irish traffic is a disaster anyhow.
 
Old 01-06-2013, 09:52 AM   #8
johnsfine
Senior Member
 
Registered: Dec 2007
Distribution: Centos
Posts: 4,966

Rep: Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073
Quote:
Originally Posted by smallpond View Post
Pittsburgh is so hilly that you have to consider 3 dimensions. Some streets right next to each other on the map are 200' apart vertically, so it can be very difficult even for a native to give directions.
On my last visit to Pittsburgh, I tried to walk from downtown to the S 10th st bridge using just my general sense of direction (no map nor instructions). I had no idea you need to go through a tunnel and there was no useful sign at the point I though maybe I should turn right off of Forbes, but mistakenly decided turning right later would be better.

So I reached the Duquesne Athletic Field (which on a map is very near the bridge) and there finally found someone I could ask for directions. Those directions sent me down the scariest, decaying outdoor staircase I have ever been on (from Bluff St down to S 10th St).

Google maps shows that staircase. But if you ask for a walking route from the top of the staircase to the bottom, it sends you all the way back to the tunnel entrance. I don't really know whether the tunnel is correct either. I don't know if it has pedestrian access. Google maps is often wrong about that. There may be no safe way to walk to that bridge.

Quote:
Originally Posted by resetreset View Post
None of you are talking about the ALGORITHM!
Quote:
Originally Posted by resetreset View Post
the idea that occurred to me was to break curves into small straight lines, but really not much more than that. (no idea even on how to measure the LENGTH of the lines after that! - er that'd be Pythagoras' theorem, right?)
I don't know how to give advise on advanced algorithms to someone who is confused over the easy parts.

Last edited by johnsfine; 01-06-2013 at 09:59 AM.
 
Old 01-07-2013, 12:07 AM   #9
resetreset
Senior Member
 
Registered: Mar 2008
Location: India
Distribution: Dynebolic, Ubuntu 10.10
Posts: 1,320

Original Poster
Rep: Reputation: 51
Quote:
Originally Posted by johnsfine View Post
I don't know how to give advise on advanced algorithms to someone who is confused over the easy parts.
Try me. Yes, I *may* require some handholding, but only some. Whatever happens, I'm willing to go through the whole damn post of anybody who posts here, and SEE what I can make of it - I enjoy that adventure.
 
Old 01-07-2013, 07:29 AM   #10
johnsfine
Senior Member
 
Registered: Dec 2007
Distribution: Centos
Posts: 4,966

Rep: Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073
Quote:
Originally Posted by resetreset View Post
Try me. Yes, I *may* require some handholding, but only some. Whatever happens, I'm willing to go through the whole damn post of anybody who posts here, and SEE what I can make of it - I enjoy that adventure.
Map data is effectively a "directed graph" with a cost (expected time) for each link.

One basic approach to shortest path is:
1) Make a priority queue of all the nodes that can be reached in one step from the starting point, prioritized by low cost.

2) Repeatedly, take the lowest cost node from the queue and insert into the queue all nodes that can be reached in one step from that lowest cost node, that have not already been processed with a lower total cost.

When the destination node is pulled from the queue, you have found a short route to it. Depending on the rules of the map, it might be true that the first time you pull the destination node you have found the shortest route, or you might need to continue processing for a while (determined by characteristics of the map).

For real world maps, it is more efficient to either work in both directions at once (compute nodes with low cost to the destination at the same time you compute low costs from the source) or include a straight line minimum cost to the destination as part of the prioritization score.

Shortest path is a very well studied problem, so you can find rigorously defined algorithms very easily with a google search. I tried above just to give a beginner friendly description of the ideas.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is it possible to click on a Google map? Also, how to find the distance bet. 2 points resetreset Programming 3 05-20-2012 01:28 PM
[SOLVED] Algorithm for finding the shortest path between Geocoordinates TheIndependentAquarius Programming 1 06-27-2011 03:37 AM
LimeWire (from SlackBuild) won't start, path points to rm-ed java directory in /usr. Dennola4 Slackware 8 07-28-2009 02:14 AM
Find a file path and directory path ak.lokesh Linux - Newbie 3 02-19-2009 12:37 PM
Good program for plotting points on a map? Electrode Linux - Software 0 05-30-2004 02:03 AM


All times are GMT -5. The time now is 10:41 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration