3

We are writing a flight search engine. We want to pre-fill the departure airport for mobile users with the closest one to their location. To do that, our plan is to

  1. Find a list of airports with their latitude/longitude.
  2. Find the user geolocation using something like HTML5 Geolocation (which asks the user for permission).
  3. Calculate the distance between the user's location and every airport to find the closest one.
  4. Fill the departure form.

Is this a standard way of proceeding? I am a junior programmer and I am not used to this kind of problem. Is there any obstacle I should bear in mind while developing my solution? I have the feeling the algorithm to calculate the distance between one point and 300 locations might get a bit heavy.

Improve this question
4
  • 5
    The calculation is trivial (look for "Great Circle Distance" algorithm). The problem, in my opinion, lies in the assumption that the closest airport is the most convenient. There are a lot of factors influencing airport choice that are more important than raw geographical distance, IMO. Commented Aug 8, 2014 at 19:43
  • 1
    @heltonbiker GCD may be overkill. Just collect the user's lat/lon then search for all airports where airport.lat is within some delta of user.lat. Subfilter for airport.lon. If the delta is 30 miles or so, you won't find THAT many airports. (Of course, in Wyoming you'll need a bigger delta) Commented Aug 8, 2014 at 20:45
  • 2
    Maybe you'd want to move the question to gis.stackexchange.com that site covers implementation questions of GIS technologies, including code. Commented Aug 8, 2014 at 21:22
  • @DanPichelman good point. That would be actually looking for points inside a bounding box centered at the user location. But unlike latitude deltas, which have the same distance-to-degree ratio, longitude deltas correspond to smaller distances at larger latitudes. That might or not be a problem, depending on the level of desired precision (rough vs precise). Commented Aug 10, 2014 at 1:39

3 Answers 3

Reset to default
3

We are writing a flight search engine.

Use a search engine!

You can use Apache Solr for example, and your #3 step is done. No need to know the details of the calculation. The basic steps needed is to store the geocodes to be searched on (the airports') then do a search using user's geocode maybe a maximum distance for results to be included.

Don't worry about being a junior, this is how seniors do it, i.e. look for existing solutions so they don't have to solve it themselves. It might take some time to configure it, but the end result is production quality.

Improve this answer
0

I'll assume that 'closest' means that you will present a list of nearby airports and allow the user to pick one. You might need up to (say) 10 airports in the list.

No, the calculation is not terribly complicated. It involves a bit of floating path maths, but not so it should cause any great stress. You can very easily reduce the number of actual calculations by pre-sorting the list and/or filtering on raw lat/lon.

One degree of latitude is obviously around 111 km. [Why? Because the original standard for the meter was 10 million meters = 90 degrees of latitude, through Paris.] One degree of longitude is anywhere from 0 to about the same. [Why? Obviously zero at the poles.]

So a first pass calculating values for locations plus/minus 10 degrees could be a useful heuristic for improved performance, and find anything within 1000 km or so. [In Australia, that wouldn't fill your list of 10.]

The great circle distance can be found here: http://en.wikipedia.org/wiki/Great-circle_distance, but I'm sure you knew that.

Improve this answer
2
  • Great circle distance is probably overkill for this, as most users are probably very close to their nearest airport, and absolutely precise accuracy is unlikely to be a requirement. Honestly, I'd just use cartesian distance with an assumption of an average ratio between the lengths of a degree of latitude and longitude. Commented Aug 10, 2014 at 0:20
  • 3
    @jules: Bad call. Great circle is just the haversine formula, which is about 3 lines of code and 10 floating point operations, and highly accurate. Cartesian requires lookup tables or other calculations to work out the length of a degree of longitude, and is still error-prone in high latitudes. Cartesian is OK for games, but not for the real GPS world. Commented Aug 10, 2014 at 2:15
0

This sort of spatial query is routinely handled by spatially enabled databases like mysql, postgres, oracle and sql server. I'm sure there are others I'm leaving out.

The search then becomes a sql query using whatever geometry type is defined for your database. The particular topic you're interested in is called a nearest neighbor query.

Check out this link for more details on how to write a query like that for sql server: http://msdn.microsoft.com/en-us/library/ff929109.aspx. Due to OGC standardization, you'll find very similar options across many databases and geospatial libraries.

The basic idea behind this scenario is to create a table that holds the locations of all the airports you're interested in as point geometry types. You then define a spatial index on that column which partitions the space. This spatial index is really a special tree structure (like a quadtree http://en.wikipedia.org/wiki/Quadtree or http://en.wikipedia.org/wiki/R-tree) which can allow large amounts of data to be excluded from the manual distance searching.

This also allows you to do some more interesting queries easily, like show me all airports within 5 miles.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.