Get the shortest distance from a point

Question

I have this table in sqlite

Locations ID Lat ( latitude) Lon ( longitude) Type Name City 

I have, for example, 100 records I need to get (using my own coordinates) the nearest point in my table.

What I did was get the shortest distance between my current point and each in the table and return the shortest, but I'm looking for the best solution

thanks

Answer 1

A possible solution is to use the grid for the entire map you are interested in and pre-assign points to a specific row / column. Then:

• Calculate the grid location of your new point - add a column to it for this.
• Calculate the distance of all coordinates in the current grid - if exists
• You still need to calculate all the distances in the next grid (you are unlikely to be perfectly concentrated in your current square, you always need to check one grid distance from the one in which there was a better match.)

Should greatly reduce the amount of computation you need to do.

If you expect that you will always find a place at a distance of X, you can request the x / y coordinates that fall into this range, your coordinates +/- x KM (square), calculate whether they fall into the xKM circle from your point, and then choose the shortest one.

UPDATE - grid option

I assume that you are already making the distance between the two point calculations and will not describe it.

If you have an atlas, you can see an example by looking at the place in the index. This will give you the page and grid location, for example M5. If you go to this page, it will have rows and columns with numbers and letters, and if you look at the square where lines M and column 5 intersect, you will find a city there. For this you need:

• determine how big your grid is (how dense your points are), it would be nice to have a big grid, and all your points will land one square).
• For each point, calculate which grid it is in. If your polygons are complex, there are many points to copy in the polygon code. If (in my example) you just use squares, you just need to determine which row / column of each point is between them.
• See map for location of user and nearest points:

So, if the user is a green marker, he will be in C4. You would look for all the other points on C4 and determine that the nearest one is No. 2. Then you will also need to check one grid all the way to make sure that the object was not closer than the one you found, so this includes squares: B3, B4, B5, C3, C5, D3, D4, D5. When you do this, you will choose No. 3 with C3 and you will be done.

If the user was in the square D2, where there are no other points, you would find your first match in the word C2. When checking C1, C2, C3, D1, D3, E1, E2, E3. After detection, you will again need to check another radius, which would be the following: B0-4, C0, C4, D0, D4, E0, E4, F0-4. etc. You can see that mesh selection will be important to make it as efficient as possible.

Also note that this assumes your grids are equal in contrast to my drawn example.

Option 2:

If you expect a result in X km and you want your database to calculate quickly, you can do this:

 LatMin = currentLatCoord-radiusValInDegrees LatMax = currentLatCoord+radiusValInDegrees LonMin = currentLonCoord-radiusValInDegrees LonMax = currentLonCoord+radiusValInDegrees SELECT * From Locations WHERE Lat BETWEEN LatMin AND LatMax AND Lon BETWEEN LonMin AND LonMax 

Now this gives you all the results squared. It is important that you then check that they are actually in the circle - you need to drop any of the corners, since there may actually be closer coordinates than at the edge of the circle. Therefore, for each point, first check to see if it is inside the circle ( Equation for testing if the point is inside the circle ), then calculate the distance and save the nearest one. If you do not get the result, increase the circle.

Again, choosing a good radius will depend on your data.

Answer 2

You are checking this site. How to calculate the distance between two points on Earth ?

But just keep in mind that it gives a distance based on the surface of the Earth, not based on the actual path to reach this position. Therefore, if you want to calculate the distance based on the actual path to reach this position, you can get it using the Google MAP API.

The Google Maps API gives the distance between two points based on the actual path.

Hope this information helps you.

Enjoy the coding ... :)

Answer 3

The distance between two points: ((x1 - x2) ^ 2 + (y1 - y2) ^ 2) ^ 0.5 . However, the distance between these points is straight. Most likely, there are variables such as local or highway, not to mention one-way streets and waterways, where you need to find the nearest bridge. Therefore, I suggest using Google maps and Bing api. They are free for a limited number of requests.

Answer 4

Is there a pretty clever solution in Query to retrieve Radius-based records in SQLite? based on the preliminary calculation of some trigonometric values ​​for each position when inserting rows, which then allow you to calculate the distance in your query using only arithmetic functions.

I used it very successfully in my own code

Answer 5

Let me make sure that this is correct: you have a point a and a table of points a[] . You are currently doing something like:

• loop over b[]
  • get distance from b[i] to a
  • if distance less than minimumDistance
    • set minimumDistance = distance
    • set closestPoint = i
• return closestPoint

If so, you find it in O(n) time, which in fact cannot be significantly improved. You must check all the points to see which ones are closest.

However, as Matthew points out, you can trim n by assigning points to the grid. This can significantly reduce the number of points needed for comparison. Consumption is a bit of preprocessing time and a bit more complex logic. If you have a long list of points (or the distance() function takes a lot of time), you will definitely want to do something like this.

Answer 6

Depends on how much you care about correctness when near the poles

if closest to the Pythagorean distance is enough you can use this in sql order

eg. SELECT * FROM locations ORDERBY (Lat-myLat)*(Lat-myLat) + (Lon-myLon)*(Lon-myLon) LIMIT 1

Not technically the most correct, but save all the locations from the database and iterate over them, let sqlite do it for you

Answer 7

You can use my php class hilbert curve @ phpclasses.org. He uses a monster curve and a quad key to find the shortest distance. You can use any depth to search for the quad key.

Answer 8

Although this is not the best option.
Let me try to figure out the shortest distance within N miles / km radius for a fixed number of places / the data in the location table does not change regularly.
Add another Distance_Index (DI) self multi reference key ArrayType column. After starting the procedure and updating the DI with the identifier in ascending order, depending on the distance from this DI. Now from the next distance the distance between you and you. just query the database and use it.

Now, in your problem there is no less space within N, then the DI will not be too long. Just as an opinion.