1

ポイントが長方形の内側にあるかどうかをチェックする次のアルゴリズムが有効かどうか疑問に思いました。私は自分の直感を使ってそれを開発しました（それをサポートするための強力な三角法/数学の基礎はありません）ので、この問題についてより多くの経験を持つ誰かから聞いてみたいです。

コンテクスト：

  • 長方形は4点で定義されます。回転させることができます。
  • 座標は常に正です。
  • 定義上、点は長方形と交差する場合、長方形の内側と見なされます。

仮説：

  • ポイントと長方形の頂点の間の距離を使用します（下の最初の図）。
  • 可能な最大合計距離は、ポイントが1つの頂点にある場合です（2番目の図）。
  • ポイントが長方形のすぐ外側にある場合、距離は大きくなります（3番目の図）。

図のリンク： http： //i45.tinypic.com/id6o35.png

アルゴリズム（Java）：

static boolean pointInsideRectangle(Point[] rect, Point point) {
    double maxDistance = distance(rect[0], rect[1]);
    maxDistance += distance(rect[0], rect[2]);
    maxDistance += distance(rect[0], rect[3]);

    double distance = 0;
    for (Point rectPoint : rect) {          
        distance += distance(rectPoint, point);
        if (distance > maxDistance) return false;
    }
    return true;
}

質問：これは正しいですか？

4

2 に答える 2

3

簡単な答え：いいえ：P（それについて悪くならないでください）

長い答え：あなたが言及する4つの円からの領域（反対側の頂点間の最大距離）を交差させると、長方形は生成されません。長方形の対角線に等しい半径の4つの円の共通領域で、各コーナーに中心があります 私は幾何学で少し錆びているので、完全な数学的説明を与えることはできません（私の部分の時間制約）が、あなたが求める制約（派手な式はありません）を備えた手順の擬似コードをあなたに与えます、wikipeidaのどの長方形にも有効ですまたは、幾何学の本でギャップを埋めることができます。

  • N、E、S、W頂点（最上部、右端、最下部、左端の頂点）を見つけます。これはどの長方形でも簡単ですが、軸が整列しているため、頂点の割り当てが奇妙になります（例のある画像を参照）。ここに画像の説明を入力してください
  • NE、SE、SW、およびNWの境界線を見つけます。これは、ウィキペディアまたは別のリンクの線の方程式です。これも簡単なはずですが、軸に沿った境界線は、別の種類の計算/制限を生成するため、慎重に分析する必要があります。

  • ポイントが境界線の「右側」にあるかどうかを確認します。不等式を数学用語として参照してください。添付の画像に示されているように、長方形の内側のポイントのみ が4つの制限を満たしています。それぞれのために

  • このタスクを実行できるjava.geomのコマンドを見落とした場合はお詫びします

これがあなたの努力に役立つことを願っています

于 2012-06-07T13:34:39.597 に答える
0

これを試すことができます。私たちが持っている点にAという名前を付けましょう。Aと長方形のすべての点の間に線を引きます。その後、4つの異なる三角形を取得します。三角形が取っている面積を計算し（ヘロンの公式を使用して）、それを比較します。長方形の面積。面積が同じ場合、ポイントは長方形の内側にあります。乾杯

于 2013-02-19T21:20:45.643 に答える