Ask a Question
or
Create a Poll
  1. Home /
  2. Questions /
  3. Travel
  4. / Travel (General)

by Thinking on April 21st, 2005

Thinking

Question

Help answer this question below.

How do maps (like on Google or Mapquest) know exactly where a house is and are able to give driving directions to/from it?

  • Like
  • Report
Share:
Other

Answers. Showing one answer.

  • by BoundSyco on May 2nd, 2005

    BoundSyco

    I will answer for mapquest, however I would assume that google would use a similar process.

    How does mapquest know where a house is?

    Simple answer, they guess. Thats right, they guess. Mapquest has an algorithm called Geocoding which uses the US post office data (for US maps) to guess (quire accurately typically) the latitude and longitude of the address you specify. Geocoding takes the address and compares it to the number of addresses the US post office says is on the current block, and guesses based upon how many addresses there are and the address supplied. For example, suppose you ask for 135 Main St. Now mapquest looks up the info it has for Main St as it is supplied by the US post office, which consists of the address on the end of the block (have you ever seen the signs that say "400" on a street sign?). Now suppose that 135 Main lies on the block that starts at 100 Main and ends at 400 Main. This means there are 300 addresses on this block. Each address is assumed to take 1/300th of the street space. Thus 135 Main will lie 35/300th's of the distance from the 100 end of the block to the other side of the block. Mapquest knows the latitude and longitude of the intersections and computes the lat/long of the address using these numbers. Further explanation here: http://www.mapquest.com/features/main.adp?page=geocode

    How is mapquest able to give driving directions?

    Again, they guess. They have very good ways of guessing, but without a massive amount of computation it is not possible to give a perfect answer. Typically the method used for such driving directions is an example of something called a "greedy algorithm". I would hazard a guess that they actually use a form of an A* ("A Star") algorithm, but the technicalities are not important. Basically the algorithm takes a location and looks at all possible directions a person can go if they are at a specified location and chooses the direction which gets the person closer to their goal. They call this a "greedy" algorithm because it continually tries to get closer to the goal. Typically this type of search arrives at the best solution. Other considerations such as travel time are taken into consideration in the real calculations.
    For more information on greedy algorithms:
    http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm
    http://en.wikipedia.org/wiki/Greedy_algorithm

    I hope this answers your question without being to technical.

    Comments

    • Jeez...it is more complicated than I thought. I was told 'They' drove around with GPS. Thanks.

      Thinking

      by Thinking on May 17th, 2005

    • Like
    • Report

    1 comment | Post one | Permalink

Want to attach an image to your answer? Click here.

Did this answer your question? If not, then ask a new question or create a poll.

More Questions. Additional questions in this category.

You're reading How do maps (like on Google or Mapquest) know exactly where a house is and are able to give driving directions to/from it?

Follow us on Facebook!

Related Ads

Related Questions

Professionally Researched

Answerbag

a Demand Media company