Return union of all rectangles

Question

I'm kinda new to Java and have a problem I just can't wrap my head around.

union (Rectangle ... rectangles) should return the rectangle given by the Union of all rectangles. If rectangles is empty, return null.

I've created a helper-Method to compute the union of 2 Rectangles and then somehow tried to integrate it into the union-Method with no success. I kinda have to do the same for the intersection of 2 Rectangles but also can't get it done.

Could you guys give me some help? Below is my code.

public class Rectangle {
    int x, y, width, height;

    public Rectangle(int xInput, int yInput, int widthInput, int heightInput) {
        if (xInput <= 0 || yInput <= 0 || widthInput <= 0 || heightInput <= 0) {
            return;
        }
        this.x = xInput;
        this.y = yInput;
        this.width = widthInput;
        this.height = heightInput;

    }

    public static Rectangle union(Rectangle... rectangles) {
        Rectangle s = new Rectangle(0, 0, 0, 0);
        if (rectangles.length != 0) {
            for (Rectangle r : rectangles) {
                s = unionOfTwo(s, r);
            }
            return s;
        } else {
            return null;
        }

    }

     public static Rectangle unionOfTwo(Rectangle rec1, Rectangle rec2) {

        int x1 = Utils.min(rec1.x, rec2.x);
        int x2 = Utils.max(rec1.x + rec1.width, rec2.x + rec2.width) - x1;
        int y1 = Utils.min(rec1.y, rec2.y);
        int y2 = Utils.max(rec1.y + rec1.height, rec2.y + rec2.height) - y1;
        return new Rectangle(x1, y1, x2, y2);
    }
}

You should define s as the first rectangle before the for loop, then update it in each iteration with unionOfTwo(s,r) and return it after the loop has completed. — n314159
Hmm, I just did that. It still says: "Union of two overlapping rectangles is not computed correctly". Could it be that my algorithm to compute the union of 2 Rectangles is wrong? — user1233156
Your computation of y2 is wrong, the second argument to max should be rec2.y + rec2.height. — n314159
What does "the rectangle given by the Union of all rectangles" mean, more specifically? A union of rectangles is generally not a rectangle itself. Do you mean the minimum bounding rectangle? — kaya3

maraca maraca · Accepted Answer · 2019-11-24T22:50:55

The problem is here:

public static Rectangle union(Rectangle... rectangles) {
    Rectangle s = new Rectangle(0, 0, 0, 0); // <-- wrong
    if (rectangles.length != 0) {
        for (Rectangle r : rectangles) {
            s = unionOfTwo(s, r);
        }
        return s;
    } else {
        return null;
    }
}

It is because if your rectangles don't overlap (0, 0), you will get a wrong result. There are several ways to fix it, here is one of them:

public static Rectangle union(Rectangle... rectangles) {
    Rectangle s = null;
    for (Rectangle r : rectangles) {
        if (s == null)
            s = r;
        else
            s = unionOfTwo(s, r);
    }
    return s;
}

Return union of all rectangles

2 Answers