Algorithm to find the nearest point to a path using Latitude and Longitude

Question

Hello guys,
I need a way to sort out the following problem.

---

Input:

• Lot of points expressed as (Latitude,Longitude) in a database
• A given path as an array of (Latitude,Longitude), the path is composed by the sum of all the segment formed using two subsequent points.

Output:

• The point that is closer to a path. To make it clear: the distance between this point and one of the segment composing the path must be less or equal to all the other distance between all the points and all the segments.

---

This is what I've been able to thought so far:

• Decompose the path in smaller paths
• For each new path compute the bounds of the concerned area.
• Make database query for all the points in the area of each path.
• Compute the distance between all the resulting points and the segments in the relative area
• Pick the smaller one

n.b. Obviously i will make each new paths calculation on a separated thread.

n.b.b. This is just the "basic idea", there are a lot of problem in this solution that i'm not showing hoping to make it simple, for example, the bounds needs to be of a proper size to be sure to include all the candidated point.

---

Since there are a lot of points and i would like to perform this search in the most efficent way, i'd like to hear some of your suggestion to improve my solution or to change it radically with something better.

Thanks for your time, comment if you want some clarification.

Answer 1

Since no one seems to solve (or maybe understand XD) my problem i'll write down what i've just accomplished on my own.

Basically i used the same solution i posted on the question, but in this answer i'll explain some problem i've found while implementing in the hope that someone one day will find this usefull.

So, the algorithm is this:

• Decompose the path array in smaller arrays. Each of this array has a total distance that i try to keep less than 4 kilometers. If two subsequent points are distant more than 4 kilometers they will be in an array alone. To compute the distance between 2 LatLng point i've used Location.distanceBetween Library.

• For each new path compute the bounds of the concerned area. To compute bounds, expressed as SouthOvest bound and NorthEast bound, i just need to check all the points in the array and save the lowest and the bigest for Latitude and Longitude. To include the points near to the path but out of the bounds i just subtract 500m to SouthOvest Latitude and Longitude and add 500m to NorthEast Latitude and Longitude, more info on how to do this here.

• Make database query for all the points in the area of each path. Since i choose to run all the "little path" on different thread i had some trouble using SQLite, nothing too difficult, you just need to understand how getReadableDatabase work, more info here.

• Compute the distance between all the resulting points and the segments in the relative area. Nothing difficult, need to compute distance point-segment for each point and for each segment of the small path. More info onw how to do this with LatLng point here

• Pick the smaller one. When the threads stops the main thread get all the results deleting any copy (Just to solve the possibility of intersected areas as mentioned in the question).