Радиус нескольких точек широты / долготы

Question

У меня есть программа, которая принимает в качестве входных данных массив широт / длинных точек.Мне нужно выполнить проверку этого массива, чтобы убедиться, что все точки находятся в пределах определенного радиуса.Так, например, максимальный радиус, который я позволю, составляет 100 миль.Учитывая массив широты / долготы (исходя из базы данных MySQL, может быть 10 точек, может быть 10000), мне нужно выяснить, все ли они будут вписываться в круг с радиусом 100 миль.как подойти к этому.Любая помощь будет принята с благодарностью.

Answer 1

Найдите наименьший круг, содержащий все точки , и сравните его радиус с 100.

Answer 2

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

Чтобы выяснить радиус набора точек широты / долготы, вы должны сначала убедиться, что ваш набор точек является "полусферическим", т.е. все точки могут вписаться в произвольную половину вашей идеальной сферы.

Ознакомьтесь с разделом 3 в статье «Оптимальные алгоритмы для некоторых задач близости на гауссовой сфере с приложениями» Гупты и Салуджи. У меня нет конкретной ссылки, но я считаю, что вы можете найти копию онлайн бесплатно. Этого документа недостаточно для реализации решения. Вам также понадобится Приложение 1 в «Приближении центроидов для максимального пересечения сферических многоугольников» Ха и Ю.

Я бы не использовал алгоритм Мегиддо для выполнения линейного программирования при тестировании полусферичности. Вместо этого используйте алгоритм Зейделя для решения задач линейного программирования, описанный Раймундом Зайделем в «Мелкомасштабном линейном программировании и выпуклых оболочках, сделанных легким». Также см. «Рандомизированный алгоритм линейного программирования Зейделя» Курта Мелхорна и раздел 9.4 из «Обнаружения столкновений в реальном времени» Кристера Эриксона.

Как только вы определили, что ваши очки полусферические, перейдите к разделу 4 статьи Гупты и Салуджи. В этой части показано, как получить наименьший окружающий круг для точек.

Чтобы выполнить необходимое квадратичное программирование, см. Статью Н. Д. Боткина «Рандомизированный алгоритм для решения квадратичных программ». Этот урок полезен, но в статье используется (1/2) x ^ T G x - g ^ T x, а в веб-учебнике используется (1/2) x ^ T H x + c ^ T x. Один добавляет термины, а другой вычитает, что приводит к проблемам со знаком. Также см. Этот пример проблемы 2D QP . Подсказка: если вы используете C ++, библиотека Eigen очень хороша.

Этот метод немного сложнее, чем некоторые из двухмерных методов, описанных выше, но он должен дать вам более точные результаты, чем полное игнорирование искривления Земли. Этот метод также имеет O (n) временную сложность, которая, вероятно, асимптотически оптимальна.

Примечание: Описанный выше метод может плохо обрабатывать дублирующиеся данные, поэтому вы можете проверить наличие дублирующих точек широты / долготы, прежде чем найдете наименьший вмещающий круг.

Answer 3

Самый простой способ решить эту проблему - преобразовать координаты в (X, Y, Z), а затем найти расстояние вдоль сферы.

Предполагая, что Земля - ​​это сфера (полностью не соответствует действительности) с радиусом R ...

X = R * cos (long) * cos (lat)

Y = R * sin (long) * cos (lat)

Z = R * sin (лат)

В этот момент вы можете приблизить расстояние между точками, используя расширение теоремы Пифагора для трёх пространств:

dist = sqrt ((x1-x2) ^ 2 + (y1-y2) ^ 2 + (z1-z2) ^ 2)

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

Представляя ваши местоположения в виде векторов V1 = (X1, Y1, Z1) и V2 = (X2, Y2, Z2), угол равен:

angle = arcsin ((V1 x V2) / (| V1 || V2 |)), где x - это перекрестное произведение.

Расстояние тогда:

dist = (окружность Земли) * угол / (2 * пи)

Конечно, это не учитывает изменения высоты или тот факт, что Земля шире на экваторе.

Извините за то, что не написал мою математику в LaTeX.

Answer 4

Ознакомьтесь с ответами на на этот вопрос . Это дает возможность измерить расстояние между любыми двумя (широтой, длинной) точками. Затем используйте алгоритм наименьшего окружающего круга .

Я подозреваю, что нахождение наименьшего окружающего круга может быть достаточно сложным на плоскости, поэтому, чтобы устранить тонкости работы с широтой и долготой и сферической геометрией, вам, вероятно, следует рассмотреть возможность сопоставления ваших точек с плоскостью XY. Это внесет некоторое искажение, но если ваш предполагаемый масштаб составляет 100 миль, вы, вероятно, можете жить с этим. Если у вас есть круг и его центр на плоскости XY, вы всегда можете вернуться обратно к земной сфере и перепроверить свои расстояния.