What is the best way to search the corridor for a set of latitude / longitude coordinates

Question

What would be the best approach to finding a set of coordinates, say, about 5.00, which lie within the path of the points with a given width. for example, an airplane following several waypoints.

Is there a good way to sort them in the same order as the route.

Computing speed will be more important than accuracy, as I look at making a list of sentences.

From what I looked, I believe that this is not easy, and the question is a bit broad, but any suggestions / pointers would be welcome, for example, for:

• Best way to store lat / long or use spherical coordinates
• Additional clustering information in the coordinate set
• Can some kind of conversion be used to simplify range checking?
• What is the best way to order points.

Here's a better approach than doing a circular / square check on several equally spaced points along the path.

Answer 1

There are many optimizations you can do:

• Divide your points into tiles of a fixed size, so you don’t need to check each point (first determine which plate you are in so you can skip all the points in other tiles).

• When calculating the distance to each point, you usually use Pythagoras to get the distance. But if you only want to know which point is the closest, you can omit the square root, which is an expensive operation (see Code Example below).

• Use a flat projection instead of working with lat / lon or approximate estimated distances, just assuming the earth is flat. For small distances (up to several kilometers), which are usually quite accurate and faster and easier than for working with WGS84 coordinates. You may need to convert all your coordinates, but this preliminary calculation will save a lot of processor cycles at runtime.

-

// delphi code that would iterate through a set of points to find the index // of the point that is the closest to the provided x/y function TMatcher.GetIndexOfClosest(X,Y:Double):Integer; var i : Integer; Closest:Double; Distance:Double; begin Closest:= MaxInt; Result := -1; for i:=0 to high(Points) do begin // taking the square root is not needed here! Distance :=Sqr(X-Points[I].X)+Sqr(Y-Points[I].Y); if Distance < Closest then begin Closest := Distance; Result := i; end; end; end; 

Answer 2

I assume that you know how to calculate the distance between points and a track. Latitude / longitude is simple (x, y) data, albeit with fractional data, not just integers.

5,000 data points is really not so bad as calculating the distance to the path for each point, but if you want to scale, some kind of relational data structure such as a quadrit will be your best choice for storing glasses. This way, you can immediately drop points that are nowhere near your path.

Answer 3

When you encounter this type of problem, I would use PostGIS . Import the data into the database, then use the spatial features of SQL to create a buffer on the track and select the points that lie inside the buffer. Lot is faster than coding it.

PostGIS (and PostgreSQL ) are easy to install on Windows / OSX / Linux. They have good documentation and a quick session at Google finds the answer to most of the questions.

Answer 4

  Best way to store lat / long, or use spherical coordinates 

What are you trying to save? The path or point you are looking for? If this is the way, then this is basically a list of some kind, since the points are ordered. Depending on how / if you manipulate the path, this will determine your data structure.

Additional clustering information in the coordinate set

What information are you trying to save? If, for example, you select a linked list as your data structure, you may have a linked list of class objects containing the information you need.

Can some conversion be used to simplify range checking

You can convert Lat / Long to UTM or any other coordinate system. The range between the two points will still be the same.

What is the best way to arrange points

If you save the path, then the order matters - as in paragraph N-1 → N → N + 1, etc ...