language-agnostic - 确定经纬度矩形和球体上的圆是否重叠

Question

假设我有以下内容：

• 由最小和最大纬度和经度定义的区域（通常是“经纬度矩形”，尽管它实际上不是矩形，除非在某些投影中）。
• 由中心纬度/经度和半径定义的圆

我如何确定：

1. 两个形状是否重叠？
2. 圆是否完全包含在矩形内？

我正在寻找一个完整的公式/算法，而不是数学课，本身。

Answer 1

警告：如果圆圈/“矩形”跨越球体的大部分，这可能会很棘手，例如：

“矩形”：最小长度 = -90 度，最大长度 = +90 度，最小纬度 = +70 度，最大纬度 = +80 度

circle：center = lat = +85deg, long = +160deg, radius = 20deg（例如，如果 A 点在圆上，C 点是圆心，O 点是球心，那么角度 AOC = 40deg）。

这些相交但数学可能有几个案例来检查相交/包含。以下点位于上述圆上：P1=(+65deg lat,+160deg long), P2=(+75deg lat, -20deg long)。P1 在“矩形”之外，P2 在“矩形”内，因此圆/“矩形”至少相交 2 个点。

好的，这是我对解决方案的概述：

---

令 C = 半径为 R 的圆心（如上表示为球面角）。C 有纬度 LATC 和经度 LONGC。由于“矩形”这个词在这里有点误导（恒定纬度的线不是大圆的段），我将使用“边界框”这个词。

• 函数InsideCircle(P)返回 +1,0 或 -1：如果点 P 在圆内，则 +1，如果点 P 在圆上，则返回 0，如果点 P 在圆外，则返回 -1：计算大圆距离 D（表示C 和任何点 P 之间的球角）会告诉你 P 是否在圆内：（InsideCircle(P) = sign(R-D)正如 Sente 中的用户 @Die 所提到的，在其他地方的这个论坛上已经询问了大圆距离）

• 定义PANG(x)= x 的主角 = MOD(x+180deg, 360deg)-180deg。PANG(x)始终介于 -180 度和 +180 度之间（含）（+180 度应映射到 -180 度）。

• 要定义边界框，您需要知道 4 个数字，但经度存在一个小问题。LAT1 和 LAT2 表示边界纬度（假设 LAT1 < LAT2）；那里没有歧义。LONG1 和 LONG2 表示经度区间的边界经度，但这变得很棘手，并且更容易将此区间重写为中心和宽度，其中 LONGM = 该区间的中心，LONGW = 宽度。请注意，经度间隔总是有两种可能性。您必须指定是哪种情况，无论您是包括还是排除 180 度子午线，例如，从 -179 度到 +177 度的最短间隔为 LONGM = +179 度和 LONGW = 4 度，但从 -179 度到 + 的其他间隔177deg 有 LONGM = -1deg 和 LONGW = 356deg。如果你天真地尝试做“常规” 与区间 [-179,177] 进行比较，您最终将使用更大的区间，这可能不是您想要的。顺便说一句，如果以下两个都为真，则具有纬度 LATP 和经度 LONGP 的点 P 位于边界框内：

  • LAT1 <= LATP 和 LATP <= LAT2 （那部分很明显）
  • abs(PANG(LONGP-LONGM)) < LONGW/2

如果 PTEST = union(PCORNER,PLAT,PLONG) 中的任何以下点 P 如下所述，则圆与边界框相交，对于 不都返回相同的结果InsideCircle()：

• PCORNER = 边界框的 4 个角
• 如果LATC 在 LAT1 和 LAT2 之间，则边界框两侧的点 PLAT（没有或 2 个）与圆的中心共享相同的纬度，在这种情况下，这些点具有纬度 LATC 和经度 LONG1 和 LONG2。
• 边界框两侧的点 PLONG（没有或 2 或 4 个！）与圆心的经度相同。这些点的经度 = LONGC或经度PANG(LONGC-180)。如果 abs(PANG(LONGC-LONGM)) < LONGW/2 则 LONGC 是有效的经度。如果 abs(PANG(LONGC-180-LONGM)) < LONGW/2 则 PANG(LONGC-180) 是有效的经度。这些经度中的一个或两个或都不在边界框的经度区间内。选择具有有效经度和纬度 LAT1 和 LAT2 的点 PLONG。

上面列出的这些点 PLAT 和 PLONG 是边界框上离圆“最近”的点（如果角不是；我在引号中使用“最近”，在纬度/长距离的意义上，而不是大 -圆距离），并涵盖圆的中心位于边界框边界的一侧但圆上的点“潜入”边界框边界的情况。

如果 PTEST 中的所有点 P 返回InsideCircle(P)== +1（都在圆内），则圆包含整个边界框。

如果 PTEST 中的所有点 P 返回InsideCircle(P)== -1（都在圆外），则圆完全包含在边界框内。

否则，圆与边界框之间至少有一个交点。请注意，这不会计算这些点的位置，尽管如果您在 PTEST 中取任意 2 个点 P1 和 P2，其中 InsideCircle(P1) = -InsideCircle(P2)，那么您可以通过二等分找到一个交点（效率低下）。（如果 InsideCircle(P) 返回 0，那么你就有一个交点，尽管浮点数学中的相等性通常是不可信的。）

可能有一种更有效的方法可以做到这一点，但上述方法应该有效。

Answer 2

使用立体投影。所有圆圈（特别是纬度、经度和您的圆圈）都映射到平面中的圆圈（或线）。现在只是一个关于平面几何中的圆和线的问题（更好的是，所有经度都是通过0的线，所有纬度都是围绕0的圆）

Answer 3

这个怎么样？

v找到将矩形中心点 连接到圆心的向量Cr。找到与矩形相交的i点。v如果||i-Cr|| + r > ||v||那么它们相交。

换句话说，矩形内线段的长度加上圆内线段的长度应该大于总长度（的v，中心连接线段）。

寻找点i应该是棘手的部分，特别是如果它落在经度边缘，但你应该能够比我更快地想出一些东西。

编辑：此方法无法判断圆是否完全在矩形内。为此，您需要找到从其中心到矩形所有四个边缘的距离。

编辑：以上不正确。正如 Federico Ramponi 所建议的那样，在某些情况下，即使在欧几里得几何中它也不起作用。我会发布另一个答案。请不接受这一点，并随时投反对票。我会尽快删除它。

Answer 4

• 是的，如果框角包含圆心。
• 是的，如果任何框角在圆心半径内。
• 是的，如果该框包含圆心的经度，并且最接近圆心纬度的框纬度的经度交点在圆心的半径内。
• 是的，如果盒子包含圆心的纬度，并且最短交点轴承上距圆心半径距离的点“超出”最近的盒子经度；其中最短交点方位角是通过找到从圆心到零纬度点的初始方位角和 pi/2“超过”最近的箱形经度的经度来确定的。
• 不，否则。

假设：

• 您可以找到从 A 点到 B 点的最小航向的初始方位。
• 您可以找到两点之间的距离。

第一次检查是微不足道的。第二次检查只需要找到四个距离。第三个检查只需要找到从圆心到（最近框纬度，圆心经度）的距离。

第四次检查需要找到最接近圆心的边界框的经线。然后找到距离圆心最远的经线所在的大圆的中心。找到从圆心到大圆心的初始方位。从该轴承上的圆心找到点圆半径。如果该点位于距离圆心最近的经线的另一侧，则圆和边界框在该侧相交。

在我看来，这应该有一个缺陷，但我一直无法找到它。

The real problem that I can't seem to solve is to find the bounding-box that perfectly contains the circle (for circles that don't contain a pole). The bearing to the latitude min/max appears to be a function of the latitude of circle-center and circle-radius/(sphere circumference/4). Near the equator, it falls to pi/2 (east) or 3*pi/2 (west). As the center approaches the pole and the radius approaches sphere-circumference/4, the bearing approach zero (north) or pi (south).

Answer 5

再试一次...

我认为解决方案是测试一组点，正如 Jason S 所建议的那样，但我不同意他选择的点，我认为这在数学上是错误的。

您需要找到纬度/经度框两侧的点，其中到圆心的距离是局部最小值或最大值。将这些点添加到角集，然后上面的算法应该是正确的。

即，设经度为 x 维，纬度为 y 维，令框的每一侧为参数曲线 P(t) = P0 + t (P1-P0)，对于 o <= t <= 1.0，其中 P0 和P1 是两个相邻的角。

令 f(P) = f(Px, Py) 为距圆心的距离。

那么 f (P0 + t (P1-P0)) 是 t 的距离函数：g(t)。找到距离函数的导数为零的所有点：g'(t) == 0。（当然，丢弃的解决方案超出域 0 <= t <= 1.0）

不幸的是，这需要找到一个超越表达式的零，所以没有封闭形式的解决方案。这类方程只能通过 Newton-Raphson 迭代求解。

好的，我知道你想要的是代码，而不是数学。但数学就是我所拥有的。

Answer 6

这应该适用于地球上的任何点。如果您想将其更改为不同大小的球体，只需将 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 7

有关欧几里得几何的答案，请参阅：圆矩形碰撞检测（交集）