Как наилучшим образом выполнить поиск диапазона коридора по набору координат широты / долготы

Question

Каков наилучший подход к поиску набора координат, скажем, около 5,00, которые лежат в пределах пути точек, учитывая указанную ширину. например, самолет, следующий за несколькими путевыми точками.

Есть ли хороший способ сортировать их в том же порядке, что и маршрут.

Скорость расчета будет важнее точности, так как я смотрю на составление списка предложений.

Из того, что я посмотрел, я предполагаю, что это не так просто, и вопрос немного широк, но любые предложения / указатели будут приветствоваться, например, для:

1. Лучший способ сохранить широту / длину или использовать сферические координаты
2. Наличие дополнительной информации о кластеризации в наборе координат
3. Можно ли использовать какое-то преобразование для упрощения проверки диапазона
4. Как лучше всего заказать очки

Здесь лучший подход, чем круговая / квадратная проверка на нескольких равноудаленных указывает вдоль пути.

Answer 1

Есть много оптимизаций, которые вы можете сделать:

• Разделите свои точки на плитки фиксированного размера, чтобы вам не приходилось проверять каждую точку (сначала определите, в какой плитке вы находитесь, чтобы пропустить все точки в других плитках).

• При расчете расстояния до каждой точки вы обычно использовали бы Пифагор для получения расстояния. Но если вы хотите узнать только, какая точка ближе всего, вы можете опустить квадратный корень, что является дорогостоящей операцией (см. Пример кода ниже).

• Используйте некоторую плоскую проекцию вместо работы с широтой / долготой или приблизительные расчетные расстояния, просто предполагая, что Земля плоская. Для небольших расстояний (до нескольких километров) это обычно достаточно точно и намного быстрее и проще, чем работа с координатами WGS84. Возможно, вам придется преобразовать все ваши координаты, но этот предварительный расчет сэкономит много циклов ЦП во время выполнения.

-

 // 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

При возникновении такой проблемы я бы использовал PostGIS . Импортируйте данные в базу данных, затем используйте пространственные функции SQL, чтобы создать буфер на дорожке и выбрать точки, которые лежат внутри буфера. Гораздо быстрее, чем кодировать его самостоятельно.

PostGIS (и PostgreSQL ) легко установить в Windows / OSX / Linux. У них хорошая документация, и быстрый сеанс в Google находит ответы на большинство вопросов.

Answer 3

Полагаю, вы знаете, как рассчитать расстояние между точками и траекторией. Широта / Долгота - это простые (x, y) данные, хотя с дробными данными, а не просто целыми числами.

5000 точек данных на самом деле не так уж и плохо вычислять расстояние до траектории для каждой точки, но если вы хотите масштабировать, то для хранения точек лучше всего подойдет какая-то структура реляционных данных, такая как дерево квадрантов. Таким образом, вы можете сразу отказаться от точек, которые не находятся рядом с вашим путем.

Answer 4

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

Что вы пытаетесь хранить? Путь или точка, которую вы ищете? Если это путь, то это принципиально какой-то список, в котором упорядочены точки. В зависимости от того, как / если вы будете манипулировать путем, это будет определять вашу структуру данных.

Наличие дополнительной информации о кластеризации в наборе координат

какую информацию вы пытаетесь сохранить? Если, например, вы выбрали связанный список в качестве структуры данных, у вас может быть связанный список объектов класса, содержащий любую необходимую вам информацию.

Можно ли использовать какое-то преобразование для упрощения проверки диапазона

Вы можете преобразовать широту / долготу в UTM или любую другую систему координат. Диапазон между двумя точками останется прежним.

Как лучше всего заказать очки

Если вы храните путь, то порядок имеет значение - как в точке N-1 -> N -> N + 1 и т. Д. ...