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

Question

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

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

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

1. Пересекаются ли две фигуры?
2. Содержит ли круг полностью внутри прямоугольника?

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

Answer 1

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

Answer 2

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

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

круг: центр = широта = + 85 градусов, длинный = + 160 градусов, радиус = 20 градусов (например, если точка A находится на окружности, а точка C - центр окружности, а точка O - центр сферы, то угол AOC = 40 градусов ).

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

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

---

Пусть 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 в Sente, отлично на этом форуме в других местах были заданы круговые расстояния)

• Определить PANG(x) = основной угол x = MOD (x + 180 градусов, 360 градусов) -180 градусов. PANG(x) всегда между -180 градусов и + 180 градусов включительно (+ 180 градусов должно соответствовать -180 градусов).

• Чтобы определить ограничивающий прямоугольник, вам нужно знать 4 числа, но есть небольшая проблема с долготой. LAT1 и LAT2 представляют ограничивающие широты (предполагая, что LAT1

  • LAT1 <= LATP и LATP <= LAT2 (эта часть очевидна) </li>
  • abs (PANG (LONGP-LONGM))

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

• PCORNER = 4 угла ограничительной рамки
• точки PLAT на сторонах ограничительной рамки (их нет или 2), которые имеют ту же широту, что и центр круга, , если LATC находится между LAT1 и LAT2, и в этом случае эти точки имеют широта LATC и долгота LONG1 и LONG2.
• точки PLONG на сторонах ограничительной рамки (их нет или 2, или 4!), Которые имеют ту же долготу, что и центр круга. Эти точки имеют ЛИБО долгота = LONGC ИЛИ долгота PANG (LONGC-180). Если abs (PANG (LONGC-LONGM))

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

Это должно работать для любых точек на земле. Если вы хотите изменить его на сферу другого размера, просто измените 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!";
}

Answer 6

Еще одна попытка на этом ...

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

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

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

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

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

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

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

Answer 7

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