I'm researching into the idea of doing a "course locator" for an educational website. The visitors enter their (UK) postcode and the distance they are prepared to travel, and they are presented with a list of all courses in their area.

I have a list of UK postcodes with their respective lat/long co-ordinates.

I think I can just about get my head around this Haversine formula for "Great Circle" mapping. However, as far as I can tell, this can only tell you the distance between two points on the globe.

What I want to do is find out the lat/long extremities for a search radius around a certain point. So, if someone entered "30 miles" and their postcode, I want to know the minimum/maximum lat/longs needed to search within that area.

Does anyone know of any such formulae? 😃

    What are you using as the database engine. I MIGHT have a solution for you if you're using MySQL.

      I am indeed using MySQL. Most likely it will be version 4.0.x on the hosting package that will be used. PHP 4.3.5.

      Cheers 🙂

        i would use a query like this to grab post codes that are within a certain distance

        the cords would need to be in seperate fileds in database

        $query1="select * from test where SQRT(POWER((cord1-".$cord1."),2) + POWER((cord2-".$cord1."),2))<'".$distance."'";

          If you're on a hosting package, I don't know if you'll have access to do this.

          Basically, a friend of mine put together (he copied some code and pasted it with some other code) to make a MySQL SQL function. The code is in C++ and requires it to be compiled in a way MySQL prefers. He's had problems compiling it for Red Hat, but I think I've worked around them (I've got it up on my web host and they're running Red Hat). Let me describe what it does and then you can determine if this is something that might be helpful:

          The function is called geodist([latitude1], [longitude1], [latitude2], [longitude2]). It returns a numeric distance value to two decimal places in miles (I'm sure with some minor tweaking, the miles can be converted to kilometers from within the C++ code). You can then do things like this:

          	$query = 'SELECT Zip, geodist(' . $lat . ', ' . $long . ', Latitude, Longitude) AS distance FROM tbl_zip WHERE geodist(' . $lat . ', ' . $long . ', Latitude, Longitude) < ' . $radius . ' ORDER BY geodist(' . $lat . ', ' . $long . ', Latitude, Longitude)';
          

          Where $lat and $long are the coordinates of the center location. Then $radius is the number of miles you want to keep the search under. On top of that, the query then sorts the results by distance, showing the closest location first. You can see it in action here:

          http://www.axtime.com/zip/geodist.php (USA zips only). I was fiddling with this and it brings the results back surprisingly fast (you end up waiting for the data to download versus the server to process the request).

          I don't know if this will fit your application or not. I'm not an expert so if this doesn't work or you have problems installing, you will be on your own along with any docs at MySQL (they have sample code on how to create and install C++ user functions). Note the commented install instructions.

          geodist.cpp:

          /*
          Created by Geoff Parris
          [email]geoff@eclectic.com[/email]
          November 2003
          Follows GPL licensing
          
          INSTALL:
          gcc -shared -o geodist.so -I /usr/local/mysql/include geodist.cpp
          
          Place in a mysql accessible library such as usr/lib
          
          Run from MySQL:
          create function geodist returns real soname "geodist.so";
          */
          
          #ifdef STANDARD
          #include <stdio.h>
          #include <string.h>
          #ifdef __WIN__
          typedef unsigned __int64 ulonglong;	/* Microsofts 64 bit types */
          typedef __int64 longlong;
          #else
          typedef unsigned long long ulonglong;
          typedef long long longlong;
          #endif /*__WIN__*/
          #else
          #include <my_global.h>
          #include <my_sys.h>
          #endif
          #include <mysql.h>
          #include <m_ctype.h>
          #include <m_string.h>		// To get strmov()
          
          #ifdef HAVE_DLOPEN
          
          /* These must be right or mysqld will not find the symbol! */
          
          extern "C" {
          my_bool geodist_init(UDF_INIT *initid, UDF_ARGS *args, char *message);
          void geodist_deinit(UDF_INIT *initid);
          double geodist(UDF_INIT *initid, UDF_ARGS *args, char *is_null,
          		   char *error);
          }
          double pi = 3.141592653589792907377;
          double rad(double gr) {return pi * gr / 180.0;}
          
          
          /*
            Simple example of how to get a sequences starting from the first argument
            or 1 if no arguments have been given
          */
          
          my_bool geodist_init(UDF_INIT *initid, UDF_ARGS *args, char *message)
          {
            if (args->arg_count != 4)
            {
              strmov(message,"geodis takes 4 args");
              return 1;
            }
            if( args->arg_type[0] != REAL_RESULT || args->arg_type[1] != REAL_RESULT ||
          	args->arg_type[2] != REAL_RESULT || args->arg_type[3] != REAL_RESULT )
            {
              strcpy(message, "geodist() requires all 4 parameters to be type REAL");
              return 1;
            }
            // set max decimals to 2 because we are returning miles
            initid->decimals = 2;
            return 0;
          }
          
          void geodist_deinit(UDF_INIT *initid)
          {
          }
          
          double geodist(UDF_INIT *initid, UDF_ARGS *args, char *is_null,
          		   char *error)
          {
            double lat1 = 0.0;
            double lon1 = 0.0;
            double lat2 = 0.0;
            double lon2 = 0.0;
          
            lat1 = *((double*) args->args[0]);
            lon1 = *((double*)args->args[1]);
            lat2 = *((double*)args->args[2]);
            lon2 = *((double*)args->args[3]);
          
            return 0.621 * 6371.2 * 2 *
          	atan2( sqrt(fabs(0 + pow(sin(rad(lat2)/2 - rad(lat1)/2),2) +
          	cos(rad(lat1)) * cos(rad(lat2)) * pow(sin(rad(lon2)/2 -
          	rad(lon1)/2),2))),sqrt(fabs(1 - pow(sin(rad(lat2)/2 -
          	rad(lat1)/2),2) + cos(rad(lat1)) * cos(rad(lat2)) *
          	pow(sin(rad(lon2)/2 - rad(lon1)/2),2))));
          
          }
          
          #endif /* HAVE_DLOPEN */
          
          
          

            Originally posted by sidney

            $query1="select * from test where SQRT(POWER((cord1-".$cord1."),2) + POWER((cord2-".$cord1."),2))<'".$distance."'";

            I've seen equations like this in math class for finding the location between 2 points such as an (x,y) point. I'm not sure I was able to interpret your eqution correctly so here's a rewrite with the idea of findingthe distance between (X1, Y1) and (X2, Y2):

            SQRT(POWER((X1 - X2),2) + POWER((Y2 - Y1),2))

            Did I interpret this correctly? Using a lat/long coordinate and your equation matched up with geodist(), I wasn't able to even get numbers that were close. Maybe you could provide some more insite. Also, how do you take into account the curvature of the earth?

              there would be no need to take in to account the curve of earth
              as your pin pointing postcode areas not a metre square area

              over england on say 40 miles the error would be negligable

              over 400miles a bit more but still acceptable i think

              you would need to find the average mile per degree latitude and long for the uk and settle on a figure this would give you a distance with some error but i feel would be ok for pin pointing postcode areas

                Could you rewrite your equation for lat/long use? Looking at it, I haven't been able to get results even closely matching what geodist() produces.

                  give me a example of the cordinates are you using minutes to
                  because it might be simpler to conver all your lat and lons and mins into a decimal system give us an example and ill take a look
                  im not a sailor and never done work with cords before but i think i would have no prob

                  also it would be possible to calculate the discrpency with curve of earth using trig but or just adding a small value per mile etc

                    The data would look like this:

                    Location A:
                    latitude: 41.412653
                    longitude: -81.560671

                    Location B:
                    latitude: 41.123588
                    longitude: -81.571295

                    I'd be curious to what distance you come up with for these two locations.

                      Thanks for all your replies. I don't think I'll be able to compile a user function into MySQL on the hosting package, but I'll see if I can convert that C code into a PHP function that I can then call in a similar way 🙂

                        guess at 70 miles per degree latitude and long

                        i would say alittle over 20 mile

                          Originally posted by gazchap
                          Thanks for all your replies. I don't think I'll be able to compile a user function into MySQL on the hosting package, but I'll see if I can convert that C code into a PHP function that I can then call in a similar way 🙂

                          may i ask why you wouldnt be able to query myslq with the example code i first posted

                            Really close (I'd be curious to see the math you're using behind the scenes so I can run some numbers against the equation). It works out to be about 19.97 miles.

                            gazchap: First see if you can compile it. You may have to ask your hosting provider to issue the MySQL query to install it. But maybe let them know what it does and they may appreciate it (because they'll be able to use it too). Worth a shot. The beauty about this function is its uber-fast and you can do your distance comparisons directly in the SQL. Example: You have 20,000 records to test. This function will only return those records within your specified range (say 10). But with PHP, you'd have to process all 20,000 to get the 10 you want. Of course, if that's the only way you can do it, then that is the best way to do it.

                              Oh, sorry sidney. I didn't notice that reply! I'll give it a shot, but it looks similar to a formula that I've seen on the web and one that states its common pitfall as a loss of accuracy as the distance increases.

                              Not too much of a problem for stuff based in the UK (we are a small nation after all) but our client has requested that it be as accurate as is possible. I'll give it a shot anyway and see what happens 🙂

                                if any one can tell me what the miles per degree lat and long on average over the uk i could get closer

                                  Originally posted by gazchap
                                  Oh, sorry sidney. I didn't notice that reply! I'll give it a shot, but it looks similar to a formula that I've seen on the web and one that states its common pitfall as a loss of accuracy as the distance increases.

                                  Not too much of a problem for stuff based in the UK (we are a small nation after all) but our client has requested that it be as accurate as is possible. I'll give it a shot anyway and see what happens 🙂

                                  the accuracy can be improve over distance using the arc of a cycle
                                  and a bit of trig

                                    2 months later

                                    the earth is technically not a sphere but an oblate spheroid from about.com:
                                    The circumference of the earth at the equator is 24,901.55 miles (40,075.16 kilometers).
                                    But, if you measure the earth through the poles the circumference is a bit shorter - 24,859.82 miles (40,008 km). This the earth is a tad wider than it is tall, giving it a slight bulge at the equator. This shape is known as an ellipsoid or more properly, geoid (earth-like).

                                    more about latitude and longitude here:
                                    http://geography.about.com/library/faq/blqzdistancedegree.htm

                                      Hi GazChap - where did you get your postcode data, is it the stuff from jibble? If it is then that also has the location in metres. I found another database of postcodes with the county and area they're in and linked that in with the jibble data to produce a "find all the postcodes X miles from my postcodes" which equates to the same thing you're trying to do. I found you can speed up the queries vastly by only doing the square root part of the query later, and first finding if the x distance and y distance are within the bounding box, then do the square root maths on the results, or do it at the end of the query here's a snippet.

                                      $q="SELECT @x:=x, @y:=y FROM jibble, postnames WHERE postnames.area LIKE '$area' AND jibble.postcode=postnames.postcode"; 
                                      
                                      $db->safe_query($q); 
                                      $db->show_table(); 
                                      
                                      $q="SELECT postnames.* FROM jibble, postnames WHERE jibble.postcode=postnames.postcode AND 
                                      x BETWEEN @x - $distance AND @x + $distance AND y BETWEEN @y - $distance AND @y + $distance 
                                      ORDER BY county, postcode";

                                      The jibble data only has 2800 postcodes, basically the first 4 letters, if you've got a better resolution one is there any chance of getting a copy of the data?

                                      I'll put up a zip of all the code and the sql for the database if you need it.