7

2 つの長方形の差を計算する簡単な方法を探しています。長方形の 1 つに属しているが、両方に属していないすべてのポイントを意味します (つまり、XOR のようなものです)。

この場合、長方形は軸に沿って配置されるため、直角のみになります。差分領域は 0 ～ 4 の四角形 (両方の四角形が同じ場合は 0、1 つのエッジだけが異なる場合は 1、一般的な場合は 4) で表現できると信じており、差分領域をリストとして取得したいと考えています。長方形の。

また、塗りつぶされた長方形が移動/サイズ変更されたときに更新する必要がある画面の領域と考えることができます。

例: 長方形 "a" の幅を 2 ​​倍にする - 追加された領域 (R) が必要です。

+----+----+
| a  | R  |
|    |    |
+----+----+

交差する長方形 (a と b) - T、L、R、B で指定された領域を長方形 (他の分割も可能) で指定しますが、X は除外します。

+------------+  a
|      T     |
|·····+------+-----+  b
|  L  | X    |  R  |
|     |      |     |
+-----+------+·····|
      |    B       |
      +------------+

私はPythonソリューション/ライブラリを好みますが、堅牢なアルゴリズムは役に立ちます。

4

3 に答える 3

10

問題を軸ごとに分割します。長方形は、各軸のスパンで定義できます。長方形が開始または終了する各軸上の興味深い点を見つけて、それらの用語で結果を定義します。これにより、異なる領域の 6 つの四角形が得られます。必要に応じて、図に示した 4 つの四角形に簡単に結合したり、縮退したゼロ領域の四角形を削除したりできます。

Java の実装は次のとおりです。

public class Rect
{
    private float minX, maxX, minY, maxY;

    public Rect( float minX, float maxX, float minY, float maxY )
    {
        this.minX = minX;
        this.maxX = maxX;
        this.minY = minY;
        this.maxY = maxY;
    }

    /**
     * Finds the difference between two intersecting rectangles
     * 
     * @param r
     * @param s
     * @return An array of rectangle areas that are covered by either r or s, but
     *         not both
     */
    public static Rect[] diff( Rect r, Rect s )
    {
        float a = Math.min( r.minX, s.minX );
        float b = Math.max( r.minX, s.minX );
        float c = Math.min( r.maxX, s.maxX );
        float d = Math.max( r.maxX, s.maxX );

        float e = Math.min( r.minY, s.minY );
        float f = Math.max( r.minY, s.minY );
        float g = Math.min( r.maxY, s.maxY );
        float h = Math.max( r.maxY, s.maxY );

        // X = intersection, 0-7 = possible difference areas
        // h +-+-+-+
        // . |5|6|7|
        // g +-+-+-+
        // . |3|X|4|
        // f +-+-+-+
        // . |0|1|2|
        // e +-+-+-+
        // . a b c d

        Rect[] result = new Rect[ 6 ];

        // we'll always have rectangles 1, 3, 4 and 6
        result[ 0 ] = new Rect( b, c, e, f );
        result[ 1 ] = new Rect( a, b, f, g );
        result[ 2 ] = new Rect( c, d, f, g );
        result[ 3 ] = new Rect( b, c, g, h );

        // decide which corners
        if( r.minX == a && r.minY == e || s.minX == a && s.minY == e )
        { // corners 0 and 7
            result[ 4 ] = new Rect( a, b, e, f );
            result[ 5 ] = new Rect( c, d, g, h );
        }
        else
        { // corners 2 and 5
            result[ 4 ] = new Rect( c, d, e, f );
            result[ 5 ] = new Rect( a, b, g, h );
        }

        return result;
    }
}
于 2011-03-01T14:29:31.050 に答える
1

交差する長方形（つまりX）の面積を見つけ、それを長方形a +長方形bの結合面積から差し引くと、解決策が得られると思います。

簡単な答えを探しているときにこれを見つけました：

http://tekpool.wordpress.com/2006/10/12/rectangle-intersection-find-the-intersecting-rectangle/

于 2011-02-28T16:31:02.637 に答える