Выпуклая оболочка (долгота, широта) -точек на поверхности сферы

Question

Стандартные алгоритмы выпуклого корпуса не будут работать с точками (долгота, широта), потому что стандартные алгоритмы предполагают, что вам нужен корпус множества декартовых точек.Точки широты и долготы , а не декартовы, потому что долгота «оборачивается» на анти-меридиане (+/- 180 градусов).То есть два градуса к востоку от долготы 179 равны -179.

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

Какие-либо предложения для уловок, которые я мог бы применить со стандартным алгоритмом выпуклой оболочки, чтобы исправить это, или указатели на правильные "геосферические" алгоритмы оболочки?

Теперь, когда я думаю об этом, есть более интересные случаи длярассмотреть, чем оседлать анти-мердиан.Рассмотрим «группу» точек, которые окружают землю - ее выпуклая оболочка не будет иметь границ восток / запад.Или даже далее, что такое выпуклая оболочка {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)}?- Казалось бы, он содержит всю поверхность Земли, так какие же точки находятся по ее периметру?

Answer 1

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

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

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

Другим подходом, принятым навигаторами и картографами на протяжении веков, было бы проецирование части поверхности сферы (части, содержащей все ваши точки) в евклидово пространство (которое является предметом картографических проекций, и я выиграл » я не буду ссылаться на обширную литературу по этому вопросу) и выяснить выпуклую оболочку спроецированных точек. Спроецируйте интересующую вас область на плоскость и отрегулируйте координаты так, чтобы они не переворачивались; Например, если вы заинтересованы во Франции, вы можете отрегулировать все долготы, добавив 30 градусов, чтобы вся страна была скоординирована по + ve числам.

Пока я пишу, идея, предложенная в ответе @ Li-aung Yip об использовании алгоритма 3D с выпуклой оболочкой, кажется мне ошибочной. Трехмерная выпуклая оболочка множества точек поверхности будет содержать точки, ребра и грани, которые лежат внутри сферы. Их буквально не существует на 2D-поверхности сферы, и они лишь изменяют ваши трудности с борьбой с не совсем правильной концепцией в 2D на совершенно неправильной в 3D. Кроме того, я узнал из статьи в Википедии, на которую я ссылался, что замкнутое полушарие (то есть то, которое включает его «экватор») не является выпуклым в геометрии поверхности сферы.

Answer 2

Вместо того, чтобы рассматривать ваши данные как данные широты и долготы, вы могли бы вместо этого рассмотреть их в трехмерном пространстве и применить алгоритм 3D выпуклой оболочки ?Затем вы сможете найти желаемую двумерную выпуклую оболочку, проанализировав выпуклую трехмерную оболочку.

Это возвращает вас к хорошо пройденным алгоритмам для декартовых выпуклых оболочек (хотя и в трех измерениях) и не имеет проблем с переносомвокруг координат.

Кроме того, есть статья: Вычисление выпуклой оболочки простого многоугольника на сфере (1996) , которая, кажется, решает некоторые из тех же проблем, что и выимеем дело с (координировать обтекание и т. д.)

Answer 3

FutureNerd:

Вы абсолютно правы. Мне пришлось решить ту же проблему, что и Maxy-B для моего приложения. В качестве первой итерации я просто обработал (lng, lat) как (x, y) и запустил стандартный 2D-алгоритм. Это работало нормально, пока никто не смотрел слишком близко, потому что все мои данные находились в смежных США. Однако в качестве второй итерации я использовал ваш подход и подтвердил эту концепцию.

Точки ДОЛЖНЫ быть в одном полушарии. Как оказалось, выбор этого полушария нетривиален (это не просто центр точек, как я изначально догадывался). Для иллюстрации рассмотрим следующие четыре пункта: (0,0), (-60,0), (+60,0) вдоль экватора и (0,90) северного полюса. Однако вы выбираете определение «центр», их центр лежит на северном полюсе по симметрии, и все четыре точки находятся в северном полушарии. Однако рассмотрите возможность замены четвертой точки, скажем, (-19, 64) Исландией. Теперь их центр НЕ на северном полюсе, а асимметрично обращен к Исландии. Однако все четыре точки все еще находятся в Северном полушарии. Кроме того, Северное полушарие, как однозначно определено Северным полюсом, является ЕДИНСТВЕННЫМ полушарием, которое они разделяют. Таким образом, вычисление этого «полюса» становится алгоритмическим, а не алгебраическим.

Смотрите мой репозиторий для кода Python: https://github.com/VictorDavis/GeoConvexHull

Answer 4

Если все ваши точки находятся в полушарии (то есть, если вы можете найти плоскость разреза через центр Земли, которая помещает их все в одну сторону), то вы можете сделать центральную, также известную как гномическую проекцию, изцентр Земли в плоскости, параллельной плоскости разреза.Тогда все большие круги становятся прямыми линиями в проекции , и поэтому выпуклая оболочка в проекции вернется к правильной выпуклой оболочке на Земле.Вы можете увидеть, насколько неправильны точки широты и долготы, посмотрев на линии широты в разделе «Гномоническая проекция» здесь (обратите внимание, что линии долготы остаются прямыми).

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