Определение перекрытия прямоугольника по широте и круга на сфере.

https://stackoverflow.com/questions/394201

23-08-2019
|

Вопрос

Предположим, у меня есть следующее:

Регион, определяемый минимальной и максимальной широтой и долготой (обычно это «прямоугольник», хотя на самом деле он не прямоугольный, за исключением некоторых проекций).
Круг, определяемый центральной широтой/долготой и радиусом.

Как я могу определить:

Перекрываются ли эти две формы?
Находится ли круг целиком внутри прямоугольника?

Я ищу полную формулу/алгоритм, а не урок математики как таковой.

Решение

Да, если углы коробки содержат центр круга.
Да, если какой-либо из углов прямоугольника находится в пределах радиуса центра круга.
Да, если поле содержит долготу центра круга, а пересечение долготы поля-широта, ближайшего к широте центра круга, находится в пределах радиуса центра круга.
Да, если поле содержит широту центра круга, а точка на расстоянии радиуса от центра круга на пеленге кратчайшего пересечения находится «за пределами» долготы ближайшего поля;где пеленг кратчайшего пересечения определяется путем нахождения начального пеленга от центра круга до точки с нулевой широтой и долготой, которая на пи/2 «за пределами» ближайшей долготы прямоугольника.
Нет, иначе.

Предположения:

Вы можете найти начальный пеленг минимального курса от точки А до точки Б.
Вы можете найти расстояние между двумя точками.

Первая проверка тривиальна.Вторая проверка просто требует нахождения четырех расстояний.Третья проверка просто требует найти расстояние от центра круга до (широты ближайшего ящика, долготы центра круга).

Четвертая проверка требует найти линию долготы ограничивающей рамки, ближайшую к центру круга.Затем найдите центр большого круга, на котором лежит линия долготы, наиболее удаленная от центра круга.Найдите начальный пеленг от центра круга до центра большого круга.Найдите точку радиуса окружности от центра окружности на этом подшипнике.Если эта точка находится по другую сторону линии долготы, ближайшей к центру круга, то круг и ограничивающая рамка пересекаются на этой стороне.

Мне кажется, что в этом должен быть изъян, но мне его найти не удалось.

Настоящая проблема, которую я не могу решить, - это найти ограничивающую рамку, которая идеально содержит круг (для кругов, которые не содержат полюса).Направление на минимальную/максимальную широту, по-видимому, является функцией широты центра круга и радиуса круга/(окружность сферы/4).Вблизи экватора оно падает до значения пи/2 (восток) или 3*пи/2 (запад).Когда центр приближается к полюсу, а радиус приближается к окружности сферы/4, направление приближается к нулю (север) или пи (юг).

Другие советы

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

"прямоугольник":минимальная длина = -90 градусов, максимальная длина = +90 градусов, минимальная широта = +70 градусов, максимальная широта = +80 градусов

круг:центр = широта = +85 градусов, долгота = +160 градусов, радиус = 20 градусов (например.если точка А находится на окружности, точка С — центр окружности, а точка О — центр сферы, то угол АОС = 40 градусов).

Они пересекаются, но математика, вероятно, будет иметь несколько случаев для проверки пересечения/включения.На описанном выше круге лежат следующие точки:P1=(+65 градусов широты, +160 градусов долготы), P2=(+75 градусов широты, -20 градусов долготы).P1 находится за пределами «прямоугольника», а P2 находится внутри «прямоугольника», поэтому круг/прямоугольник пересекаются как минимум в двух точках.

Хорошо, вот мой вариант решения:

Пусть C = центр круга с радиусом R (выраженный как сферический угол, как указано выше).C имеет широту LATC и долготу LONGC.Поскольку слово «прямоугольник» здесь вводит в заблуждение (линии постоянной широты не являются сегментами больших кругов), я буду использовать термин «ограничивающая рамка».

функция InsideCircle(P) возвращает +1,0 или -1: +1, если точка P находится внутри круга, 0, если точка P находится на круге, и -1, если точка P находится вне круга:расчет расстояния D по большому кругу (выраженного как сферический угол) между C и любой точкой P покажет вам, находится ли P внутри круга: InsideCircle(P) = sign(R-D) (Как упомянул пользователь @Die in Sente, на этом форуме в другом месте задавались вопросы о больших расстояниях по кругу)
Определять PANG(x) = главный угол x = MOD(x+180 градусов, 360 градусов)-180 градусов. PANG(x) всегда находится в диапазоне от -180 до +180 градусов включительно (+180 градусов должно соответствовать -180 градусам).
Чтобы определить ограничивающую рамку, вам нужно знать 4 числа, но есть небольшая проблема с долготой.LAT1 и LAT2 представляют собой ограничивающие широты (при условии, что LAT1 < LAT2);там нет никакой двусмысленности.LONG1 и LONG2 представляют собой ограничивающие долготы интервала долготы, но это становится сложнее, и проще переписать этот интервал как центр и ширину, где LONGM = центр этого интервала и LONGW = ширина.ОБРАТИТЕ ВНИМАНИЕ, что всегда есть два варианта интервалов долготы.Вы должны указать, какой из этих случаев это, включаете ли вы меридиан 180 градусов или исключаете его, напримерсамый короткий интервал от -179 градусов до +177 градусов имеет LONGM = +179 градусов и LONGW = 4 градуса, но другой интервал от -179 градусов до +177 градусов имеет LONGM = -1 градус и LONGW = 356 градусов.Если вы наивно попытаетесь выполнить «обычные» сравнения с интервалом [-179,177], вы в конечном итоге будете использовать больший интервал, а это, вероятно, не то, что вам нужно.Кроме того, точка P с широтой LATP и долготой LONGP находится внутри ограничивающего прямоугольника, если выполняются оба следующих условия:
- LAT1 <= LATP и LATP <= LAT2 (эта часть очевидна)
- abs(PANG(LONGP-LONGM)) < LONGW/2

Окружность пересекает ограничивающую рамку, если ЛЮБАЯ из следующих точек P в PTEST = Union(PCORNER,PLAT,PLONG), как описано ниже, не все возвращают одинаковый результат для InsideCircle():

PCORNER = 4 угла ограничивающей рамки.
точки PLAT на сторонах ограничивающей рамки (их либо нет, либо 2), которые имеют ту же широту, что и центр круга, если LATC находится между LAT1 и LAT2, и в этом случае эти точки имеют широту LATC и долготу LONG1 и LONG2.
точки PLONG на сторонах ограничивающей рамки (их либо нет, либо 2 или 4!), которые имеют ту же долготу, что и центр круга.Эти точки имеют ИЛИ долгота = LONGC ИЛИ долгота ПАНГ(LONGC-180).Если abs(PANG(LONGC-LONGM)) < LONGW/2, то LONGC является допустимой долготой.Если abs(PANG(LONGC-180-LONGM)) < LONGW/2, то PANG(LONGC-180) является допустимой долготой.Одна из этих долгот, обе или ни одна из этих долгот не могут находиться в пределах интервала долготы ограничивающей рамки.Выберите точки PLONG с допустимыми долготами и широтами LAT1 и LAT2.

Эти точки PLAT и PLONG, перечисленные выше, являются точками ограничивающей рамки, которые «ближайшими» к кругу (если углы не таковы;Я использую слово «ближайший» в кавычках в смысле широты/длинного расстояния, а не расстояния по большому кругу) и охватываю случаи, когда центр круга находится на одной стороне границы ограничивающей рамки, но точки на круге «прокрадываются через» граница ограничивающей рамки.

Если все точки P в PTEST возвращаются InsideCircle(P) == +1 (все внутри круга), то круг полностью содержит ограничивающую рамку.

Если все точки P в PTEST возвращаются InsideCircle(P) == -1 (все вне круга), то круг полностью находится внутри ограничивающей рамки.

В противном случае существует хотя бы одна точка пересечения круга и ограничивающей рамки.Обратите внимание, что при этом не вычисляется расположение этих точек, хотя если вы возьмете любые две точки P1 и P2 в PTEST, где InsideCircle(P1) = -InsideCircle(P2), то вы можете найти точку пересечения (неэффективно) путем деления пополам.(Если InsideCircle(P) возвращает 0, то у вас есть точка пересечения, хотя равенству в математике с плавающей запятой обычно не следует доверять.)

Вероятно, есть более эффективный способ сделать это, но описанное выше должно работать.

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

Как насчет этого?

Найти вектор v которая соединяет центр прямоугольника, точку Cr, в центр круга.Найти точку i где v пересекает прямоугольник.Если ||i-Cr|| + r > ||v|| тогда они пересекаются.

Другими словами, длина отрезка внутри прямоугольника плюс длина отрезка внутри круга должна быть больше общей длины ( v, отрезок, соединяющий центр).

Поиск точки i это должно быть сложнее, особенно если оно приходится на край долготы, но вы сможете придумать что-нибудь быстрее, чем я.

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

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

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

Этот метод используется для расчета расстояния между точками широты и долготы.

Я взял эту формулу расстояния отсюда:http://www.codeproject.com/csharp/distancebetweenlocations.asp

public static double Calc(double Lat1, double Long1, double Lat2, double Long2)
{
    double dDistance = Double.MinValue;
    double dLat1InRad = Lat1 * (Math.PI / 180.0);
    double dLong1InRad = Long1 * (Math.PI / 180.0);
    double dLat2InRad = Lat2 * (Math.PI / 180.0);
    double dLong2InRad = Long2 * (Math.PI / 180.0);

    double dLongitude = dLong2InRad - dLong1InRad;
    double dLatitude = dLat2InRad - dLat1InRad;

    // Intermediate result a.
    double a = Math.Pow(Math.Sin(dLatitude / 2.0), 2.0) +
               Math.Cos(dLat1InRad) * Math.Cos(dLat2InRad) *
               Math.Pow(Math.Sin(dLongitude / 2.0), 2.0);

    // Intermediate result c (great circle distance in Radians).
    double c = 2.0 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1.0 - a));

    // Distance.
    // const Double kEarthRadiusMiles = 3956.0;
    const Double kEarthRadiusKms = 6376.5;
    dDistance = kEarthRadiusKms * c;

    return dDistance;
}

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

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

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

public string Test(double cLat,
    double cLon,
    double cRadius,
    double rlat1,
    double rlon1,
    double rlat2,
    double rlon2,
    double rlat3,
    double rlon3,
    double rlat4,
    double rlon4)
{
    double d1 = Calc(cLat, cLon, rlat1, rlon1);
    double d2 = Calc(cLat, cLon, rlat2, rlon2);
    double d3 = Calc(cLat, cLon, rlat3, rlon3);
    double d4 = Calc(cLat, cLon, rlat4, rlon4);

    if (d1 <= cRadius ||
        d2 <= cRadius ||
        d3 <= cRadius ||
        d4 <= cRadius)
    {

        return "Circle and Rectangle intersect...";
    }

    double width = Calc(rlat1, rlon1, rlat2, rlon2);
    double height = Calc(rlat1, rlon1, rlat4, rlon4);

    if (d1 >= cRadius &&
        d2 >= cRadius &&
        d3 >= cRadius &&
        d4 >= cRadius &&
        width >= d1 &&
        width >= d2 &&
        width >= d3 &&
        width >= d4 &&
        height >= d1 &&
        height >= d2 &&
        height >= d3 &&
        height >= d4)
    {
        return "Circle is Inside of Rectangle!";
    }



    return "NO!";
}

Еще одна попытка в этом направлении...

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

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

Т.е. пусть долгота является измерением x и широты-размер y, пусть каждая сторона блока будет параметрической кривой p (t) = p0 + t (p1-p0) для o <= t <= 1,0, где p0 и P1 - два смежных угла.

Пусть f(P) = f(P.x, P.y) — расстояние от центра круга.

Тогда f (P0 + t (P1-P0)) является функцией расстояния от t:г(т).Найдите все точки, в которых производная функции расстояния равна нулю:г'(т) == 0.(Конечно, отбрасывание решений выходит за пределы области 0 <= t <= 1,0)

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

Хорошо, я понимаю, что вам нужен код, а не математика.Но математика – это все, что у меня есть.

Ответ на вопрос евклидовой геометрии см.: Обнаружение столкновения круга и прямоугольника (пересечение)

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow