8

次のものがあるとします。

  • 緯度と経度の最小値と最大値によって定義される地域 (特定の投影法を除いて、実際には長方形ではありませんが、通常は「緯度経度四角形」)。
  • 中心の緯度/経度と半径で定義される円

どのように判断できますか:

  1. 2 つの形状が重なるかどうか。
  2. 円が四角形に完全に含まれているかどうか。

数学そのもののレッスンではなく、完全な式/アルゴリズムを探しています。

4

7 に答える 7

3

警告:円/「長方形」が球の大部分にまたがる場合、これは注意が必要です。例:

"rectangle": 最小長 = -90 度、最大長 = +90 度、最小緯度 = +70 度、最大緯度 = +80 度

円: 中心 = 緯度 = +85 度、長さ = +160 度、半径 = 20 度 (たとえば、点 A が円上にあり、点 C が円の中心であり、点 O が球の中心である場合、角度 AOC = 40 度)。

これらは交差しますが、数学では、交差/包含をチェックするケースがいくつかある可能性があります。次のポイントは上記の円上にあります: P1=(+65 緯度、+160 度経度)、P2=(+75 度緯度、-20 度経度)。P1 は「長方形」の外側にあり、P2 は「長方形」の内側にあるため、円/「長方形」は少なくとも 2 点で交差します。

OK、これがソリューションの概要での私のショットです。

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)示します。

  • 定義PANG(x)= x の主角度 = MOD(x+180deg, 360deg)-180deg. PANG(x)常に -180 度から +180 度までの範囲です (+180 度は -180 度にマップする必要があります)。

  • バウンディング ボックスを定義するには、4 つの数値を知る必要がありますが、経度には若干の問題があります。LAT1 と LAT2 は境界緯度を表します (LAT1 < LAT2 と仮定)。そこに曖昧さはありません。LONG1 と LONG2 は経度間隔の境界経度を表しますが、これはややこしいので、この間隔を中心と幅として書き直す方が簡単です。LONGM = その間隔の中心、LONGW = 幅です。経度間隔には常に 2 つの可能性があることに注意してください。子午線 180 度を含めるか除外するかにかかわらず、これらのケースのいずれであるかを指定する必要があります。たとえば、-179 度から +177 度までの最短間隔は LONGM = +179 度と LONGW = 4 度ですが、-179 度から +179 度までの他の間隔は +179 度です。 177deg は、LONGM = -1deg および LONGW = 356deg です。素朴に「レギュラー」をやろうとすると 間隔 [-179,177] と比較すると、より大きな間隔を使用することになり、それはおそらくあなたが望むものではありません。余談ですが、緯度 LATP と経度 LONGP を持つポイント P は、次の両方が true の場合、境界ボックス内にあります。

    • 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 を持ちます。
  • 円の中心と同じ経度を共有する、バウンディング ボックスの側面にあるポイント (何もないか、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 (すべて円の外側) を返す場合、円は境界ボックス内に完全に含まれます。

それ以外の場合は、円と境界ボックスの間に少なくとも 1 つの交点があります。これは、これらのポイントがどこにあるかを計算しないことに注意してください。ただし、InsideCircle(P1) = -InsideCircle(P2) である PTEST で P1 と P2 の 2 つのポイントを取得すると、二分法によって (非効率的に) 交点を見つけることができます。(InsideCircle(P) が 0 を返す場合、交点がありますが、浮動小数点演算の等号は一般に信頼されません。)

おそらくこれを行うためのより効率的な方法がありますが、上記は機能するはずです。

于 2008-12-26T22:06:17.800 に答える
3

平射図法を使用します。すべての円 (具体的には緯度、経度、および円) は、平面内の円 (または線) にマップされます。これは、平面ジオメトリの円と線に関する単なる質問です (さらに良いことに、すべての経度は 0 を通る線であり、すべての緯度は 0 の周りの円です)。

于 2009-01-01T23:10:08.697 に答える
2

これはどう？

四角形の中心 pointを円の中心vに結ぶベクトルを見つけます。長方形と交わる点をCr見つけます。もしそうなら、それらは交差します。iv||i-Cr|| + r > ||v||

つまり、長方形の内側のセグメントの長さと円の内側のセグメントの長さの合計がv、(中心を結ぶ線セグメントの) 全長よりも大きくなければなりません。

特に経度の端にある場合は、ポイントを見つけるiのが難しい部分ですが、私よりも早く何かを思いつくことができるはずです。

編集: このメソッドは、円が完全に長方形内にあるかどうかを判断できません。そのためには、その中心から四角形の 4 つのエッジすべてまでの距離を見つける必要があります。

編集：上記は正しくありません。Federico Ramponi が示唆したように、ユークリッド幾何学でも機能しない場合があります。別の回答を投稿します。これを受け入れず、遠慮なく反対票を投じてください。すぐに削除します。

于 2008-12-26T22:55:46.263 に答える
2
  • はい、ボックスの角に円の中心が含まれている場合。
  • はい、ボックスの角のいずれかが円の中心の半径内にある場合。
  • ボックスに circle-center の経度が含まれていて、circle-center-latitude に最も近い box-latitude の経度交点が circle-center の半径内にある場合は、はい。
  • はい、ボックスに円の中心の緯度が含まれており、円の中心から最短交差点方位の半径距離にあるポイントが、最も近いボックスの経度を「超えている」場合。ここで、最短交差方位は、円の中心から緯度ゼロの地点までの初期方位と、最も近いボックス経度を「超える」pi/2 の経度を見つけることによって決定されます。
  • いいえ、そうでなければ。

仮定:

  • 点 A から点 B までの最小コースの初期方位を見つけることができます。
  • 2 点間の距離を求めることができます。

最初のチェックは簡単です。2 番目のチェックでは、4 つの距離を見つけるだけです。3 番目のチェックでは、円の中心から (最も近いボックスの緯度、円の中心の経度) までの距離を見つけるだけです。

4 番目のチェックでは、円の中心に最も近い境界ボックスの経線を見つける必要があります。次に、円の中心から最も遠い経度線が載っている大円の中心を見つけます。円の中心から大円の中心までの初期方位を見つけます。その方位の円の中心から点の円の半径を見つけます。その点が円の中心から最も近い経度線の反対側にある場合、円と境界ボックスはその側で交差します。

これには欠陥があるはずですが、見つけることができませんでした。

私が解決できないように見える本当の問題は、円を完全に含むバウンディングボックスを見つけることです（極を含まない円の場合）。緯度の最小/最大への方位は、円の中心と円の半径/(球の円周/4) の緯度の関数のように見えます。赤道付近では、pi/2 (東) または 3*pi/2 (西) になります。中心が極に近づき、半径が球の円周/4 に近づくと、方位はゼロ (北) または pi (南) に近づきます。

于 2009-05-08T21:17:42.517 に答える
1

これをもう一度試してみてください...

解決策は、Jason S が提案したように、点のセットをテストすることだと思いますが、彼の点の選択には同意しません。これは数学的に間違っていると思います。

円の中心までの距離が局所的な最小値または最大値である、緯度/経度ボックスの側面上の点を見つける必要があります。これらの点をコーナーのセットに追加すると、上記のアルゴリズムが正しくなるはずです。

つまり、経度を x 次元、緯度を y 次元とし、ボックスの各辺をパラメトリック曲線 P(t) = P0 + t (P1-P0) for o <= t <= 1.0 とします。ここで、P0 とP1 は隣接する 2 つのコーナーです。

f(P) = f(Px, Py) を円の中心からの距離とします。

この場合、f (P0 + t (P1-P0)) は t の距離関数: g(t) です。距離関数の導関数がゼロであるすべてのポイントを見つけます: g'(t) == 0. (もちろん、解を破棄するとドメイン 0 <= t <= 1.0 を超えます)

残念ながら、これは超越式のゼロを見つける必要があるため、閉じた形式の解はありません。このタイプの方程式は、Newton-Raphson 反復によってのみ解くことができます。

OK、数学ではなくコードが必要だったことがわかりました。しかし、数学は私が持っているすべてです。

于 2008-12-27T20:55:13.793 に答える
1

これは、地球上のどの地点でも機能するはずです。異なるサイズの球体に変更したい場合は、kEarchRadiusKms を球体に必要な半径に変更するだけです。

このメソッドは、緯度点と経度点の間の距離を計算するために使用されます。

ここからこの距離式を取得しました: http://www.codeproject.com/csharp/distance betweenlocations.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!";
}
于 2008-12-31T01:25:48.143 に答える
-1

ユークリッド幾何学の答えについては、以下を参照してください:円と長方形の衝突検出 (交差)

于 2008-12-31T00:26:59.730 に答える