CODEWITHSUNDEEP
algorithmdata-structuresgeolocationgeospatial
Dark Matter
Dark Matter

Reputation: 3698

How can I do efficient multi search points by lat long

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

Upvotes: 3

Views: 346

Answers (3)

xpda
xpda

Reputation: 15813

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.

Upvotes: 2

Анатолий
Анатолий

Reputation: 2857

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.

Upvotes: 1

Srikant Krishna
Srikant Krishna

Reputation: 881

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.

Upvotes: -1

Related Questions