Учитывая набор координат, как я могу вычислить минимальные границы?

У меня есть набор координат в lon / lat. Всегда есть как минимум 3 упорядоченные координаты, которые образуют поли (если они были спроецированы на плоскость). Как я могу рассчитать минимальные границы для этих координат в виде набора допустимых диапазонов долготы и широты? (под «действительным» я подразумеваю диапазоны, которые явно учитывают антимеридиан). Трудно объяснить, что я ищу, поэтому у меня есть картинка.

Случай на картинке тривиален; Вы просто находите абсолютный минимум и максимум для всех точек. Это не работает для всех случаев, хотя. Есть ли общее решение?

Изменить: Чтобы уточнить, что я имею в виду под «действительным», скажем, что в моем наборе данных было три значения долготы: -76, -135 и 164. Значения пересекают антимеридиан, и я хотел бы, чтобы результирующие диапазоны были разделены: -76 до -180 и от 164 до 180.

Еще несколько уточнений. Точки образуют многоугольник, поэтому в некоторых случаях требуемый диапазон может быть от -180 до +180 (т. Е. Все 360 градусов):

Изображение слева показывает долготу четырех координат, которые встречаются на одной «половине» Земли. Представьте, что вы смотрите на северный полюс (черная точка). Розовый цвет показывает минимальный продольный диапазон, который охватывает многоугольник (многоугольник показан между четырьмя точками фиолетового цвета). Случай слева будет иметь два продольных диапазона: [-180 до -120] и [135 до 180] (просто визуально оценивая его)

На изображении справа показан другой случай, когда точки движутся вокруг Земли. Этот диапазон будет [-180 до 180].

Надеюсь, я правильно понял вопрос ...

Мы можем решить проблему для долготы и широты отдельно, поэтому я возьму ваш пример с долготой: -76, -135 и 164.

Сначала я бы заказал их:

-135, -76, 164

Тогда я бы добавил левую координату справа снова: -135 + 360 = 225

-135, -76, 164, 225

Теперь мы можем рассчитать промежутки между координатами:

-135 (59) -76 (240) 164 (61) 225
             .......

Самый большой зазор (240) должен быть границей минимального ограничивающего прямоугольника, той части, которая не принадлежит этому прямоугольнику. Пунктирная линия - самая большая часть круга, которую мы можем выделить. В нашем примере это означает, что граничная рамка начинается с 164, включает -135 и заканчивается -76.

Это действительно легко сделать в Javascript с помощью API Карт Google. Вот как вы могли бы сделать это на стороне клиента с этим API:

var bounds = new google.maps.LatLngBounds();

//Recursively loop through your coordinate list
    latLng = new google.maps.LatLng(<YourLat>, <YourLon>);
    bounds.extend(latLng);
//

extentBox = new google.maps.Rectangle({
    bounds: bounds,
    strokeColor: "#FF0000",
    strokeOpacity: 0.8,
    strokeWeight: 2,
    fillColor: "#FF0000",
    fillOpacity: 0.35
});
extentBox.setMap(map);

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

Учитывая то, что я занимаюсь получением диапазонов lon / lat для многоугольника, а не только для точек, которые его составляют, один из способов решения проблемы - фактически «пройти» вдоль набора упорядоченных координат от начала до конца. Вы отслеживаете, насколько далеко по часовой стрелке и против часовой стрелки вы прошли относительно центра Земли с учетом начальной точки, и продолжаете движение, пока не пройдете полигон:

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

Этот метод также работает, когда многоугольник «обнимает» поверхность Земли, а не пересекает ее. Таким образом, если у вас есть многоугольник, показывающий кого-то, путешествующего по поверхности Земли от Торонто (отр .: -79) до Лондона (отн .: -5) до Токио (отн .: 139) и обратно (в том же порядке), вы будете получить диапазон [от -79 до 139].

Если многоугольник пересекает центр (представьте две соседние точки в +90 и -90), я считаю, что это полный цикл (360 градусов), хотя вы можете пойти в любом случае.