How best to perform corridor range search over a set of latitude / longitude coordinates

Question

Hi,

What would be the best approach to finding the set of coordinates, from say about 5,00, which lie within a path of points, given a specified width. eg an aircraft following several waypoints.

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

Calculation speed would be more important than accuracy, since I'm looking at producing a list of suggestions.

From what I've looked at, I presume it's not straightforward, and the question is a bit broad, but any suggestions/pointers would be welcome, eg for:

1. Best way to store lat / long, or use spherical coordinates
2. Having additional clustering info in the coordinate set
3. Can a transform of some kind be use to simplify the range check
4. What is the best way to order the points

Is here a better approach than doing a circular/square check on several equi-distant points along the path.

Answer 1

I assume you know how to calculate the distance between the points and the path. Latitude/Longitude is simple (x,y) data, although with fractional data rather than just integers.

5,000 data points really isn't that bad to compute the distance to the path for each point, but if you wish to scale, some kind of relational data structure such as a quadtree would be your best bet to store the points. That way, you can immediately discard the points that are nowhere near your path.

Answer 2

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

What are you trying to store? The path, or the point you're searching for? If its the path, then it is fundamentally a list of some kind, as points are ordered. Depending on how/if you will manipulate the path, that will determine your data structure.

Having additional clustering info in the coordinate set

what information are you trying to store? If, for example, you chose a linked list as your data structure, you could have a linked list of class objects containing whatever information you needed.

Can a transform of some kind be use to simplify the range check

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

What is the best way to order the points

If you're storing a path, then the order matters - as in point N-1 -> N -> N+1, and so on...

Answer 3

There are many optimisations that you can do:

• Split your points into fixed sized tiles so you don't have to check every point (first determine which tile you're in, so you can skip all points in other tiles).

• When calculating the distance to each point, you'd normally 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 example code below).

• Use some flat projection instead of working with lat/lon, or approximate calculated distances by just assuming that the earth is flat. For small distances (up until several kilometres) that's usually accurate enough, and way faster and easier than working with WGS84 coordinates. You might have to convert all your coordinates though, but that precalculation is going to save a lot of cpu-cycles in 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 4

When faced with this type of problem, I'd use PostGIS. Import the data into the database, then use the spatial SQL functions to create a buffer on the track and select the points that lie inside the buffer. Lot quicker than coding it yourself.

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