-1

1 つのアルゴリズムに問題があります。2 つの長方形 (どちらも OX と OY に平行) の交点の面積を計算するとします。長方形 (A と呼びましょう) は (x1,y1,x2,y2) 左上隅 (x1,y1) と右下隅 (x2,y2) で表され、秒は B (x3,y3,x4, y4)。1つのアルゴリズムについて考えましたが、不十分なようです。

if(all of the points of rectangle A are inside of rectangle B)
     calculate(A);
else if(all of points the points of rectangle B are in A)
     calculate(B);
else if(x1 y1 is inside rectangle B)
        if(x1 is on the left from x3){
            if(y1 is under the y3)
         else
        }

などなど、とても長くてばかげています。

4

1 に答える 1

1

はい、私が考えるように、問題は分離可能であり、3 つ以上の次元に拡張できるため、少し非効率的です。

次元 x で重なり合う幅を計算し、次元 y で重なり合う高さを計算して、それらを乗算するだけで十分です。

(長方形が一部の次元で重ならない場合、その値は 0 です)

オーバーラップの検出は、各四角形の min_x と max_x の値を比較することによって行われます。

 <------>  <------->   vs.  <-----> <----->
 a      b  c       d        c     d a     b
 Thus if b<=c OR a>=d, then no overlapping length = 0

 <------------->   or   <------------->
 a    <---->   b        a       <------------->
      c    d                    c     b       d
 + the 2 symmetric cases (swap ab & cd)

最後の行から、共通領域の端点はd & b の最小値です。共有エリアの始点はa&cの最大値です。

次に、共通領域は min(d,b) - max (a,c) です。これが負の場合はどうでしょうか。さて、最初の行の条件を確認したところです...

于 2012-10-23T18:44:23.970 に答える