0

I have serious performance issues with a distance calculation script.

I have approximately 3000 locations (and this will eventually be doubled) in a database. The database structure is quite complex (categories, subcategories) but with time(); I saw that these query's didn't took much time.

I have a $_GET of latitude and longitude of the user and I use this calculation to determine if the location is within a certain radius:

   function distance($lat1, $lon1, $lat2, $lon2, $unit) {

      $theta = $lon1 - $lon2;
      $dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) +  cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta));
      $dist = acos($dist);
      $dist = rad2deg($dist);
      $miles = $dist * 60 * 1.1515;
      $unit = strtoupper($unit);

      if ($unit == "K") {
        return ($miles * 1.609344);
      } else if ($unit == "N") {
          return ($miles * 0.8684);
        } else {
            return $miles;
          }
    }

// some sql queries to get the lat/lon from the locations

if ((distance($_GET["lat"], $_GET["long"], $row3["content"], $row4["content"], "K") . "") < 10) {

            //push to multidimensional array



        }

$row3["content"] and $row4["content"] are the latitude and longitude values. For 3000 locations, this calculation takes up to 13 seconds!

I read this: Fastest Way to Find Distance Between Two Lat/Long Points

I think the option to draw a box, based on the $_GET of latitude and longitude could perhaps already remove the current calculation. In the sql queries I can already filter out the locations outside the 10 km range.

But I have 2 questions:

  1. If I change the SQL to something like this: ... WHERE LAT >= x1 AND <= x2, does this affect the time of the query?
  2. In the explanation the writer talks about "units". I've been playing around with the lat/lon values, but how do I actually calculate x1, x2, y1, y2 where the $_GET value is a point in the center with a distance of 10 km?

Thank you.

Community
  • 1
  • 1
Prastow
  • 178
  • 1
  • 19
  • If you are serious about performance, you should really look into some GIS/spatial solution. – Jonathan Kuhn Apr 02 '14 at 18:18
  • 1
    I'm certain that the problem has to do with your database code, and not the calculation of your distance between two coordinates. I don't know how to help you with your queries, since you didn't show them to us. – Brad Apr 02 '14 at 18:19
  • It's a lot of code to show, but basically it's this: select * from table A - while mysqli_fetch_assoc select reference id's from table B (match with id's from table A) - while mysqli_fetch_assoc select LAT from table C (match with reference id from table B) - while mysqli_fetch_assoc select LON from table C (match with reference id from table B) - while mysqli_fetch_assoc { //distance calculation } – Prastow Apr 02 '14 at 18:36
  • 1
    This is why most people generate a bounding box for their SQL query, to reduce the number of records that they need to calculate distances for: it doesn't eliminate the need for calculating distances because you're reducing the number still further with the calculation, but it reduces the number of times you need to execute the calculation – Mark Baker Apr 02 '14 at 19:03
  • Thanks, I've updated my answer. I indeed found this a very effective approach, I was able to reduce the loading time from 13 seconds to only 1, only because of using a bounding box in the SQl query. – Prastow Apr 02 '14 at 19:06

1 Answers1

0

I was able to reduce the calculation time from 13 seconds to 1 second!

I did this by filtering out with mysql the locations that were not within a 10 km bounding box of my lat/long coordinates.

I used this code:

  $rad = 10;  // radius of bounding circle in kilometers

  $R = 6371;  // earth's mean radius, km

  // first-cut bounding box (in degrees)
  $maxLat = $_GET['lat'] + rad2deg($rad/$R);
  $minLat = $_GET['lat'] - rad2deg($rad/$R);
  // compensate for degrees longitude getting smaller with increasing latitude
  $maxLon = $_GET['long'] + rad2deg($rad/$R/cos(deg2rad($_GET['lat'])));
  $minLon = $_GET['long'] - rad2deg($rad/$R/cos(deg2rad($_GET['lat'])));

and I changed my mysql to this:

$sql2 = "SELECT ....WHERE LAT BETWEEN '".$minLat."' AND '".$maxLat."'";
$sql3 = "SELECT ....WHERE LON BETWEEN '".$minLon."' AND '".$maxLon."'";

The rest of my code and calculation is exact the same, but instead of doing 3000 calculations, mysql sweeps out the majority.

I don't know if this approach is 100% mathematically correct, but as far as I see it works very fast with minor changes to my initial coding so for my project it's great.

And of course, the source: http://www.movable-type.co.uk/scripts/latlong-db.html

Prastow
  • 178
  • 1
  • 19