0

Here's my problem:

I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long coordinates. I also have a function to calculate the distance between two points based on their coordinates.

Now I'm looking for a way to find one of these things:

  • The n nearest products to the user's location.
  • All the products within a radius of x kilometers from the user's location.

Both solutions would be fine for my application.

Currently I just iterate over all the database entries, find their distance, and sort them. This obviously gets way too slow with a lot of entries.

Are there any algorithms/data structures I can apply here to make it faster?

Thanks in advance!

Wouter Florijn
  • 2,711
  • 2
  • 23
  • 38
  • That's why many people using a bounding box in their WHERE clause, to limit the number of database entries that they run the calculation against – Mark Baker Apr 15 '15 at 16:58
  • Have a look here: http://dexxtr.com/post/83498801191/how-to-determine-point-inside-circle-using-mysql – axel.michel Apr 15 '15 at 17:01
  • @MarkBaker That sounds like a very good idea! However, I wouldn't know how to implement this based on lat/long coordinates. It seems like it would work alright in some cases, but would be really difficult near the Prime median and North/South pole. Reference: http://www.learner.org/jnorth/images/graphics/mclass/Lat_Long.gif – Wouter Florijn Apr 15 '15 at 17:02
  • @axel.michel I'll take a look at implementing that. Looks promising. If you think it solves my problem, please add it as an answer with some explanation. – Wouter Florijn Apr 15 '15 at 17:05
  • How much of your data is close to the poles or to the dateline? Bounding boxes are a simple but efficient approach, and can be split into two or even four boxes with a little bit of code logic if you are close to the poles or to the 180 degree meridian – Mark Baker Apr 15 '15 at 17:08
  • Alternatives include more specialist datastructures such as quadtrees – Mark Baker Apr 15 '15 at 17:08
  • Google wrote up a doc on how query for calculating distances, https://developers.google.com/maps/articles/phpsqlsearch_v3 Go to the `Finding Locations with MySQL` section – chris85 Apr 15 '15 at 17:08

0 Answers0