25

x、y、幅、高さ（ピクセル）、回転値（度）の2つの長方形がある場合、それらの輪郭の相互の最も近い距離を計算するにはどうすればよいですか？

背景：Luaで書かれたゲームでは、ランダムにマップを生成していますが、特定の長方形が互いに近すぎないようにしたいのですが、長方形が特定の近距離位置に入るとマップが解決できなくなるため、これが必要です。ボールはそれらの間を通過する必要があります。長方形があまりなく、マップはレベルごとに1回だけ生成されるため、速度は大きな問題ではありません。StackOverflowで見つけた以前のリンクはこれとこれです

よろしくお願いします！

4

9 に答える 9

11

編集：OKが指摘するように、このソリューションはすべての長方形が直立していることを前提としています。OPが要求するように回転した長方形で機能させるには、各長方形の角から他の長方形の最も近い辺までの距離も計算する必要があります。ただし、点が線分の両方の端点の上または下にあり、両方の線分の左または右にある場合は、ほとんどの場合、その計算を避けることができます (電話の位置 1、3、7、または 9 に対して線分）。

Agnius の答えは DistanceBetweenLineSegments() 関数に依存しています。以下は、そうでない場合の分析です。

(1) Check if the rects intersect. If so, the distance between them is 0.
(2) If not, think of r2 as the center of a telephone key pad, #5.
(3) r1 may be fully in one of the extreme quadrants (#1, #3, #7, or #9). If so
    the distance is the distance from one rect corner to another (e.g., if r1 is
    in quadrant #1, the distance is the distance from the lower-right corner of
    r1 to the upper-left corner of r2).
(4) Otherwise r1 is to the left, right, above, or below r2 and the distance is
    the distance between the relevant sides (e.g., if r1 is above, the distance
    is the distance between r1's low y and r2's high y).
于 2014-03-20T07:22:13.263 に答える
4

実際、高速な数学的解法があります。

Length(Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent)))

どこCenter = ((Maximum - Minimum) / 2) + MinimumとExtent = (Maximum - Minimum) / 2。基本的に、オーバーラップしているゼロの軸より上のコードであるため、距離は常に正しいです。

多くの状況で望ましいので、長方形をこの形式のままにしておくことが望ましいです (回転ははるかに簡単です)。

于 2016-01-28T15:56:51.210 に答える
3

擬似コード:

distance_ between_rectangles = some_scary_big_number;
Rectangle1 の各 edge1 について: Rectangle2
    の各 edge2 について:         距離= edge1 と edge2 の間の
        最短距離を計算し             ます。

于 2011-02-23T10:40:11.487 に答える
0

この質問は、どのような距離に依存します。中心の距離、エッジの距離、または最も近いコーナーの距離が必要ですか？

私はあなたが最後のものを意味すると思います。X値とY値が長方形の中心を示している場合は、このトリックを適用することで各コーナーを見つけることができます

//Pseudo code
Vector2 BottomLeftCorner = new Vector2(width / 2, heigth / 2);
BottomLeftCorner = BottomLeftCorner * Matrix.CreateRotation(MathHelper.ToRadians(degrees));
//If LUA has no built in Vector/Matrix calculus search for "rotate Vector" on the web.
//this helps: http://www.kirupa.com/forum/archive/index.php/t-12181.html

BottomLeftCorner += new Vector2(X, Y); //add the origin so that we have to world position.

すべての長方形のすべての角に対してこれを実行してから、すべての角をループして距離を計算します（abs（v1-v2）のみ）。

これがお役に立てば幸いです

于 2011-02-12T14:27:36.747 に答える