How can I do efficient multi search points by lat long

Question

I'm an app on iOS, which has Trip Planner. For example I'm using google direction API to get route from New York to Boston. I have 50 different latitude longitude to make polylines on the map. After that I need to get places on this route which I can visit on the way to Boston.

Google directions API gives me:

latitude = "30.308399"; longitude = "-89.748299";
latitude = "30.310930"; longitude = "-89.818604";
latitude = "30.350050"; longitude = "-89.916054";
latitude = "30.432850"; longitude = "-90.098549";
....

Right now for each point I do search in mysql database to get closest places:

select id,title,type_id,service_id,latitude,longitude,state,city,zip,address, ( 3959 * acos( cos( radians(31.72723) ) * cos( radians(latitude ) ) * cos( radians( longitude ) - radians(-106.3047)) + sin( radians(31.72723) ) * sin( radians(latitude ) ) ) ) AS distance from places distance <= 10 order by distance ASC limit 10

But if this trip from New York to San Francisco, I will have 800 points, I would to make 800 query to database which takes more than 2 seconds in total. And I have 7 different tables, it would be 14 seconds.

What is the best to do if?

Example

You need to make places in DB more organized..may be by running k-means clustering and dividing them into different clusters..then instead of searching each place you can search by each cluster..size of the cluster..should depend on level of zoom.. — Shivam, Feb 20 '13 at 06:52
possible duplicate of [Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location](http://stackoverflow.com/questions/5031268/algorithm-to-find-all-latitude-longitude-locations-within-a-certain-distance-fro) — raisercostin, Dec 18 '14 at 09:56

score 2 · Answer 1 · answered Feb 20 '13 at 06:45

Here's one way to make it faster:

(1) Put indexes in the table for latitude and longitude.

(2) In the query, select first only those places within a horizontal and vertical distance of the point on the route, close enough to be interesting. Select by latitude range and longitude range.

(3) Then sort those points by distance, either inside or outside the query.

score 1 · Answer 2 · answered Feb 20 '13 at 06:43

1

Best I can suggest this is Voronoi diagram. But it hard to implement.

Notes: As you have only 80k points, you may cache all this points inside application and return from application required points.

answered Feb 20 '13 at 06:43

Толя

2,839
15
23

Srikant Krishna · Answer 3 · 2013-02-20T06:40:44.817

-1

Try putting in a minimum distance clause, Where Diatance > 100 etc.

This is known as a conical scan. You start with a low resolution and then keep increasing as you get closer.

edited Feb 20 '13 at 06:40

answered Feb 20 '13 at 06:28

Srikant Krishna

881
6
11

It nothing changed, he still need calculate distance. – Толя Feb 20 '13 at 06:29
Still need to make 5 600 queries to database in total. – Dark Matter Feb 20 '13 at 06:31
He won't be receiving hundreds of datapoints, perhaps dozens. And that would speed up his query. This is the intuitive solution - for very large distances, do a "broader" scan first and then reuce the distance. – Srikant Krishna Feb 20 '13 at 06:34
He select only top 10. To apply you query SQL still must calculate distance to each point. – Толя Feb 20 '13 at 06:35

How can I do efficient multi search points by lat long

3 Answers3