57

座標系の軸に平行な辺を持つ2つの長方形aとbがあります。私はそれらの座標をx1、y1、x2、y2として持っています。

私はそれらが重なっているだけでなく、どれだけ重なっているのかを判断しようとしていますか？私は、それらが本当に同じ長方形であるかどうかを把握しようとしています。それで、彼らの面積は95％同じですか？

オーバーラップの％を計算するのに役立ちますか？

4

9 に答える 9

82

交差点の面積を計算します。これも長方形です。

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

そこから、組合の面積を計算します。

SU = SA + SB - SI

そして、あなたは比率を考慮することができます

SI / SU

（完全なオーバーラップの場合は100％、0％まで）。

于 2012-02-17T08:31:58.593 に答える
33

与えられた受け入れられた答えは正しいですが、答えの論理的根拠を完全に明らかにする方法でこの答えを調査することは価値があると思います。これはあまりにも一般的なアルゴリズムであり、不完全な（またはさらに悪いことに、物議を醸す）答えを得ることができません。さらに、与えられた式を一目見ただけでは、アルゴリズムの美しさと拡張性、および行われている暗黙の決定を見逃す可能性があります。

まず、2次元ボックスを定義する1つの方法を考えてみましょう。

  • （x、y）左上のポイント
  • （x、y）右下のポイント

これは次のようになります。

長方形の例

左上を三角形で、右下を円で示しています。x1, x2これは、この例のような不透明な構文を避けるためです。

2つの重なり合う長方形は次のようになります。

2つの長方形

オレンジとブルーが衝突する場所を探しているオーバーラップを見つけることに注意してください。

長方形のオーバーラップ

これを認識すると、オーバーラップはこれら2つの暗い線を見つけて乗算した結果であることが明らかになります。

オーバーラップの定義

各線の長さは、2つの円の点の最小値から、2つの三角形の点の最大値を引いたものです。

ここでは、ツートンカラーの三角形（および円）を使用して、オレンジとブルーのポイントが互いに比較されていることを示しています。ツートンカラーの三角形の後の小さな文字「y」は、三角形がy軸に沿って比較されることを示し、小さな「x」は、三角形がx軸に沿って比較されることを意味します。

重複を見つける

たとえば、濃い青色の線の長さを見つけるために、三角形が2つの間の最大値を探すために比較されていることがわかります。比較される属性はx属性です。三角形間の最大x値は210です。

同じことを言う別の言い方をすると、オレンジとブルーの両方の線に合う新しい線の長さは、線の最も遠い側の最も近い点から線の最も近い側の最も遠い点を引くことによって求められます。

オーバーラップを表示

それらの線を見つけると、重複する領域に関する完全な情報が得られます。

計算のデモンストレーション

これができたら、重複の割合を見つけるのは簡単です。

重複の割合を見つける

しかし、待ってください。オレンジ色の長方形が青い長方形と重ならない場合は、問題が発生します。

最後の注意：壊れた例

この例では、重複する領域に対して-850が得られますが、これは正しくありません。さらに悪いことに、検出がどちらの次元とも（x軸でもy軸でも）重ならない場合でも、両方の次元が負であるため、正の数が得られます。Max(0, ...) * Max(0, ...)これが、をソリューションの一部と見なす理由です。オーバーラップのいずれかが負の場合、関数から0が返されることが保証されます。

私たちの象徴に沿った最終的な公式：

式

max(0, ...)この関数を使用する必要がない場合があることに注意してください。何かがすべてではなく、その次元の1つに沿って重なっているかどうかを知りたい場合があります。maxを使用すると、その情報が消去されます。そのため、重複しないバウンディングボックスをどのように処理するかを検討してください。通常、max関数は使用しても問題ありませんが、何をしているのかを知っておく価値があります。

最後に、この比較は線形測定にのみ関係するため、任意の寸法または任意の重なり合う四辺形にスケーリングできることに注意してください。

要約する：

intersecting_area = 
max(0, min(orange.circle.x, blue.circle.x) 
  - max(orange.triangle.x, blue.triangle.x)) 
  * max(0, min(orange.circle.y, blue.circle.y) 
  - max(orange.triangle.y, blue.triangle.y)
)

percent_coverage = intersecting_area 
   / (orange_area + blue_area - intersecting_area)
于 2018-09-05T23:58:25.043 に答える
9

私も最近この問題に遭遇し、イヴの答えを適用しましたが、どういうわけかそれが間違った領域サイズにつながったので、私はそれを書き直しました。

2つの長方形AとBを想定して、それらがどれだけ重なっているのかを調べ、重なっている場合は、領域サイズを返します。

IF A.right < B.left OR A.left > B.right
    OR A.bottom < B.top OR A.top > B.bottom THEN RETURN 0

width := IF A.right > B.right THEN B.right - A.left ELSE A.right - B.left
height := IF A.bottom > B.bottom THEN B.bottom - A.top ELSE A.bottom - B.top

RETURN width * height
于 2013-04-16T09:02:51.783 に答える
6

比率が0と1の間になるように以前の回答を修正するだけです（Pythonを使用）：

    # (x1,y1) top-left coord, (x2,y2) bottom-right coord, (w,h) size
    A = {'x1': 0, 'y1': 0, 'x2': 99, 'y2': 99, 'w': 100, 'h': 100}
    B = {'x1': 0, 'y1': 0, 'x2': 49, 'y2': 49, 'w':  50, 'h':  50}

    # overlap between A and B
    SA = A['w']*A['h']
    SB = B['w']*B['h']
    SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
    SU = SA + SB - SI
    overlap_AB = float(SI) / float(SU)
    print 'overlap between A and B: %f' % overlap_AB

    # overlap between A and A
    B = A
    SB = B['w']*B['h']
    SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
    SU = SA + SB - SI
    overlap_AA = float(SI) / float(SU)
    print 'overlap between A and A: %f' % overlap_AA

出力は次のようになります。

    overlap between A and B: 0.250000
    overlap between A and A: 1.000000
于 2014-03-24T15:19:28.120 に答える
4

前のコメントと回答からの状況のように見えるように、長方形が平行xで軸でなければならないと仮定します。y

まだコメントを投稿することはできませんが、前の両方の回答は、一方の長方形がもう一方の長方形の側面内に完全にある場合を無視しているように見えることを指摘したいと思います。私が間違っている場合は訂正してください。

ケースを考えてみましょう

a: (1,1), (4,4)
b: (2,2), (5,3)

この場合、交差点の高さはbTop - bBottom、の垂直部分bが完全にに含まれているためでなければならないことがわかりますa。

次のようにさらにケースを追加する必要があります:(上下を左右と同じものとして扱う場合はコードを短縮できるため、条件付きチャンクを2回複製する必要はありませんが、これで十分です）。

if aRight <= bLeft or bRight <= aLeft or aTop <= bBottom or bTop <= aBottom:
    # There is no intersection in these cases
    return 0
else:
    # There is some intersection

    if aRight >= bRight and aLeft <= bLeft:
        # From x axis point of view, b is wholly contained in a
        width = bRight - bLeft
    elif bRight >= aRight and bLeft <= aLeft:
        # From x axis point of view, a is wholly contained in b
        width = aRight - aLeft
    elif aRight >= bRight:
        width = bRight - aLeft
    else:
        width = aRight - bLeft

    if aTop >= bTop and aBottom <= bBottom:
        # From y axis point of view, b is wholly contained in a
        height = bTop - bBottom
    elif bTop >= aTop and bBottom <= aBottom:
        # From y axis point of view, a is wholly contained in b
        height = aTop - aBottom
    elif aTop >= bTop:
        height = bTop - aBottom
    else:
        height = aTop - bBottom

return width * height
于 2013-08-01T17:46:55.157 に答える
2

@ User3025064は正しく、最も簡単な解決策ですが、交差しない長方形、たとえば長方形AとB（Visual Basicの場合）については、最初に排他性をチェックする必要があります。

If A.Top =< B.Bottom or A.Bottom => B.Top or A.Right =< B.Left or A.Left => B.Right then
    Exit sub   'No intersection
else
    width = ABS(Min(XA2, XB2) - Max(XA1, XB1))
    height = ABS(Min(YA2, YB2) - Max(YA1, YB1))
    Area = width * height      'Total intersection area.
End if
于 2014-03-29T20:04:19.533 に答える
2 
[ymin_a, xmin_a, ymax_a, xmax_a] = list(bbox_a)
[ymin_b, xmin_b, ymax_b, xmax_b] = list(bbox_b)

x_intersection = min(xmax_a, xmax_b) - max(xmin_a, xmin_b) + 1
y_intersection = min(ymax_a, ymax_b) - max(ymin_a, ymin_b) + 1

if x_intersection <= 0 or y_intersection <= 0:
    return 0
else:
    return x_intersection * y_intersection
于 2014-07-29T15:13:34.853 に答える
2

これがC＃で機能する関数です。

    public double calculateOverlapPercentage(Rectangle A, Rectangle B)
    {
        double result = 0.0;
        //trivial cases
        if (!A.IntersectsWith(B)) return 0.0; 
        if (A.X == B.X && A.Y == B.Y && A.Width == B.Width && A.Height == B.Height) return 100.0;


        //# overlap between A and B
        double SA = A.Width * A.Height;
        double SB = B.Width * B.Height;
        double SI = Math.Max(0,  Math.Min(A.Right, B.Right) - Math.Max(A.Left, B.Left)) *
                    Math.Max(0, Math.Min(A.Bottom, B.Bottom) - Math.Max(A.Top, B.Top));
        double SU = SA + SB - SI;
        result = SI / SU; //ratio
        result *= 100.0; //percentage
        return result;
    }
于 2020-06-11T07:41:56.050 に答える
1

@user3025064の答えは正しい答えです。受け入れられた回答は、誤って内部のMAX呼び出しとMIN呼び出しを反転させます。また、ABS（x）ではなくMAX（0、x）の式を使用する場合は、それらが交差するかどうかを最初に確認する必要はありません。それらが交差しない場合、MAX（0、x）はゼロを返し、交差領域を0にします（つまり、互いに素です）。

@Yves Daoustが彼の答えを修正することをお勧めします。それは、その問題を検索する人にポップアップする受け入れられた答えだからです。繰り返しになりますが、交差点の正しい式は次のとおりです。

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

残りはいつものように。連合：

SU = SA + SB - SI

と比率：

SI/SU

于 2015-06-12T10:03:39.430 に答える