Разница (XOR) между двумя прямоугольниками, как прямоугольники?

Я ищу простой способ рассчитать разницу между двумя прямоугольниками. Я имею в виду все точки, которые принадлежат одному из прямоугольников, но не обоим (так что это похоже на XOR).

Прямоугольники в этом случае выровнены по оси, поэтому будут только прямые углы. Я считаю, что область различия может быть выражена в 0-4 прямоугольниках (0, если оба прямоугольника одинаковы, 1, если отличается только одно ребро, 4 в общем случае), и я хотел бы получить область различия в виде списка. прямоугольников.

Вы также можете думать об этом как об областях экрана, которые должны обновляться при перемещении / изменении размера сплошного прямоугольника.

Примеры: Удвоение ширины прямоугольника "а" - я хочу добавить область (R).

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

Пересекающиеся прямоугольники (a и b) - я хочу область, заданную T, L, R и B в прямоугольниках (возможно другое разбиение), но исключая X:

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

Я бы предпочел решение / библиотеку Python, но любой надежный алгоритм был бы полезен.

3 ответа

Решение

Разделите проблему на каждую ось. Ваши прямоугольники могут быть определены с точки зрения их промежутков на каждой оси - найдите интересные точки на каждой оси, где начинается или заканчивается прямоугольник, а затем определите свои результаты в этих терминах. Это даст вам 6 прямоугольников разностных областей, вы можете легко объединить их до четырех, как вы проиллюстрировали, или устранить вырожденные прямоугольники нулевой области, если вам нужно.

Вот реализация 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;
    }
}

В этой ссылке есть алгоритм: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Rectangle_difference

Это называется "4-зонная разница прямоугольников".

Он в основном вычисляет четыре возможных прямоугольника, которые могут остаться после вычитания одного прямоугольника из другого.

В этом случае алгоритм должен быть запущен дважды.

Я хотел бы представить, что найти площадь пересекающегося прямоугольника (то есть X) и вычесть ее из объединенной области прямоугольника a + прямоугольник b даст ваше решение.

Я нашел это на своей охоте для быстрого ответа:

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

Другие вопросы по тегам