Нахождение ближайшей пары точек на сфере

Question

Я знаю, как реализовать n log n алгоритм ближайшей пары точек (Shamos и Hoey) для 2D случаев (x и y).Однако для задачи, где даны широта и долгота, этот подход не может быть использован.Расстояние между двумя точками рассчитывается по формуле haversine.

Я хотел бы знать, есть ли какой-нибудь способ преобразовать эти широты и долготы в их соответствующие координаты x и y и найти ближайшую пару точек, илиесли есть другая техника, которая может быть использована для этого.

Answer 1

Я бы перевел их в трехмерные координаты, а затем использовал бы разделяй и властвуй , используя плоскость, а не линию. Это определенно будет работать правильно. Мы можем быть уверены в этом, потому что при рассмотрении только точек на сфере две ближайшие точки по дуговому расстоянию (расстояние, пройденное по поверхности) также будут двумя ближайшими по 3-му декартовому расстоянию. Это будет иметь время работы O (nlogn).

Для перевода в трехмерные координаты проще всего сделать (0,0,0) центр Земли, и тогда ваши координаты будут (cos (широта) * cos (долгота), cos (широта) * грех (LAN), грех (лат)). Для этих целей я использую шкалу, для которой радиус Земли равен 1, чтобы упростить вычисления. Если вам нужно расстояние в какой-то другой единице, просто умножьте все величины на радиус Земли, если измерять в этой единице.

Должен отметить, что все это предполагает, что земля является сферой. Это не совсем одна точка, и точки могут иметь высоту, поэтому эти ответы не будут действительно точными, но они будут очень близки к корректировке почти в каждом случае.