Find intersecting rectangle

Question

Given two rectangles, return the intersecting rectangles. This class is thread-safe. It takes rectangles in two different representations, and returns the intersecting rectangle in the respective representations.

Looking for code review, optimization and best practices.

final class RectangleWithPoints {
    private final int leftTopX;
    private final int leftTopY;

    private final int rightBottomX;
    private final int rightBottomY;

    RectangleWithPoints (int leftTopX, int leftTopY, int rightBottomX, int rightBottomY) {
        this.leftTopX = leftTopX;
        this.leftTopY = leftTopY;
        this.rightBottomX = rightBottomX;
        this.rightBottomY = rightBottomY;
    }

    public int getTopLeftX() {
        return leftTopX;
    } 

    public int getTopLeftY() {
        return leftTopY;
    }

    public int getBottomRightX() {
        return rightBottomX;
    }

    public int getBottomRightY() {
        return rightBottomY; 
    }

    @Override
    public String toString() {
        /*
         * http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java
         */
        return "TopLeftPoint: ("  + leftTopX + "," + leftTopY + ")"   + "  BottomRightPoint: (" + rightBottomX + "," + rightBottomY + ")" ; 
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + leftTopX;
        result = prime * result + leftTopY;
        result = prime * result + rightBottomX;
        result = prime * result + rightBottomY;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        RectangleWithPoints other = (RectangleWithPoints) obj;
        if (leftTopX != other.leftTopX)
            return false;
        if (leftTopY != other.leftTopY)
            return false;
        if (rightBottomX != other.rightBottomX)
            return false;
        if (rightBottomY != other.rightBottomY)
            return false;
        return true;
    }
} 

final class RectangleWithHeightAndWidth {
    private final int leftBottomX;
    private final int leftBottomY;
    private final int height;
    private final int width; 

    RectangleWithHeightAndWidth (int leftBottomX, int leftBottomY, int height, int width) {
        this.leftBottomX = leftBottomX;
        this.leftBottomY = leftBottomY;
        this.height = height;
        this.width = width;
    }

    public int getLeftBottomX() {
        return leftBottomX;
    }

    public int getLeftBottomY() {
        return leftBottomY;
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }    


    @Override
    public String toString() {
        /*
         * http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java
         */
        return "BottomLeftPoint: (" +  leftBottomX + "," + leftBottomY + "), Height: " + height + " Width: " + width;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + height;
        result = prime * result + leftBottomX;
        result = prime * result + leftBottomY;
        result = prime * result + width;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        RectangleWithHeightAndWidth other = (RectangleWithHeightAndWidth) obj;
        if (height != other.height)
            return false;
        if (leftBottomX != other.leftBottomX)
            return false;
        if (leftBottomY != other.leftBottomY)
            return false;
        if (width != other.width)
            return false;
        return true;
    }
}

public final class OverlappingRectangles {

    private OverlappingRectangles() { }

    private static boolean intersects(RectangleWithPoints rect1, RectangleWithPoints rect2) {
        // is one rectangle on left side of other
        if (rect1.getBottomRightX() < rect2.getTopLeftX() || rect2.getBottomRightX() < rect1.getTopLeftX()) {
            return false;
        }

        // is one of the rectangle is below the other.
        if (rect1.getTopLeftY() < rect2.getBottomRightY() || rect2.getTopLeftY() < rect1.getBottomRightY()) {
            return false;
        }

        return true;
    }


    /**
     * Given two overlapping rectangles, returns the intersecting rectangle.
     * If rectangles are not overlapping then exception is thrown.
     * It is clients responsibility to pass in the valid Rectangle object, else results are unpredictable.
     * 
     * 
     * @param rect1         The rectangle
     * @param rect2         The second rectangle
     * @return              The intersecting rectangle.
     * @throws              IllegalArgumentException if it occurs.
     */
    public static RectangleWithPoints fecthIntersectingRectangle (RectangleWithPoints rect1, RectangleWithPoints rect2) {
        if (!intersects(rect1, rect2))  throw new IllegalArgumentException("The rectangles cannot intersect.");

        RectangleWithPoints rectLeft = null;
        RectangleWithPoints rectRight = null;

        if (rect1.getTopLeftX() < rect2.getTopLeftX()) {
            rectLeft  = rect1;
            rectRight = rect2;
        } else {
            rectLeft  = rect2;
            rectRight = rect1;
        }

        // check if the 'top y' axis of 'right' rectangle falls in range of 'height' of 'left' rectangle
        if (rectRight.getTopLeftY() < rectLeft.getTopLeftY() && rectRight.getTopLeftY() > rectLeft.getBottomRightY()) {
           return new RectangleWithPoints(rectRight.getTopLeftX(),  rectRight.getTopLeftY(), rectLeft.getBottomRightX(), rectRight.getBottomRightY());
        } 
        // means the 'bottom y' axis of the 'right' rectangle falls in the range of 'hieght' of 'left rantangle'
        return new RectangleWithPoints(rectRight.getTopLeftX(), rectLeft.getTopLeftY(), rectLeft.getBottomRightX(), rectRight.getBottomRightY());
    }

    private static boolean intersects(RectangleWithHeightAndWidth rect1, RectangleWithHeightAndWidth rect2) {
        // is one rectangle on left side of other
        if ((rect1.getLeftBottomX() + rect1.getWidth() < rect2.getLeftBottomX())
                || (rect2.getLeftBottomX() + rect2.getWidth() <  rect1.getLeftBottomX()))  {
            return false;
        }

        // is one rectangle is below the other
        if ((rect1.getLeftBottomY() + rect1.getHeight() < rect2.getLeftBottomY()) ||
                (rect2.getLeftBottomY() + rect2.getHeight() < rect1.getLeftBottomY())) {
            return false;
        }

        return true;
    }


    /**
     * Given two overlapping rectangles, returns the intersecting rectangle.
     * If rectangles are not overlapping then exception is thrown.
     * It is clients responsibility to pass in the valid Rectangle object, else results are unpredictable.
     * 
     * 
     * @param rect1         The rectangle
     * @param rect2         The second rectangle
     * @return              The intersecting rectangle.
     * @throws              IllegalArgumentException if it occurs.
     */
    public static RectangleWithHeightAndWidth fetchIntersectingRectangle (RectangleWithHeightAndWidth rect1, RectangleWithHeightAndWidth rect2) {
        if (!intersects(rect1, rect2)) throw new IllegalArgumentException("The rectangles cannot intersect.");

        RectangleWithHeightAndWidth rectLeft = null;
        RectangleWithHeightAndWidth rectRight = null;

        if (rect1.getLeftBottomX() < rect2.getLeftBottomX()) {
            rectLeft  = rect1;
            rectRight = rect2;
        } else {
            rectLeft  = rect2;
            rectRight = rect1;
        }


        int rectRightSmallX = rectRight.getLeftBottomX();
        int rectRightTopY = rectRight.getLeftBottomY() + rectRight.getHeight(); 
        int rectRightBottomY = rectRight.getLeftBottomY();

        int rectLeftBigX = rectLeft.getLeftBottomX() + rectLeft.getWidth();
        int rectLeftTopY = rectLeft.getLeftBottomY() + rectLeft.getHeight();
        int rectLeftBottomY = rectLeft.getLeftBottomY();

        // check if the 'top y' axis of 'right' rectangle falls in range of 'height' of 'left' rectangle
        if ((rectRightTopY < rectLeftTopY) && (rectRightTopY > rectLeftBottomY)) {
            return new RectangleWithHeightAndWidth(rectRightSmallX, 
                                                        rectLeftBottomY,
                                                            rectRightTopY - rectLeftBottomY,
                                                            rectLeftBigX - rectRightSmallX);
        } else {
            return new RectangleWithHeightAndWidth(rectRightSmallX,
                                                        rectRightBottomY,
                                                            rectLeftTopY - rectRightBottomY,
                                                            rectLeftBigX- rectRightSmallX);
        }
    }

    public static void main(String[] args) {

        //  top-left corner, of right rectangle intersects
        assertEquals(new RectangleWithPoints(15, 25, 25, 5), 
                fecthIntersectingRectangle(new RectangleWithPoints(10,  35,  25, 15), 
                        new RectangleWithPoints(15,  25,  35, 5)));

        // bottom-left corner of right rectangle intersects
        assertEquals(new RectangleWithPoints(20, 40, 30, 30), 
                fecthIntersectingRectangle(new RectangleWithPoints(10,  40,  30, 20), 
                        new RectangleWithPoints(20,  50,  40, 30)));

       //  top-left corner, of right rectangle intersects
        assertEquals(new RectangleWithHeightAndWidth(20, 20, 10, 10), 
                fetchIntersectingRectangle(new RectangleWithHeightAndWidth(10,  20,  20, 20), 
                        new RectangleWithHeightAndWidth(20,  10,  20, 20)));

        // bottom-left corner of right rectangle intersects
        assertEquals(new RectangleWithHeightAndWidth(20, 30, 10, 10), 
                fetchIntersectingRectangle(new RectangleWithHeightAndWidth(10,  20,  20, 20), 
                        new RectangleWithHeightAndWidth(20,  30,  20, 20)));

    }
}

Answer 1

Instead of putting unit tests in the main method, create proper JUnit tests.

---

At least one of your unit tests is incorrect:

assertEquals(new RectangleWithPoints(15, 25, 25, 5), 
        fecthIntersectingRectangle(new RectangleWithPoints(10,  35,  25, 15), 
                new RectangleWithPoints(15,  25,  35, 5)));

This test corresponds to something like this:

AAA
AAA
AXXBB
AXXBB
 XXBB
 XXBB

The intersection of the A and B rectangles (right side of your case) should be (15, 25, 25, 15) instead of (15, 25, 25, 5). So something's wrong with your intersection implementation.

---

Try to cover all corner cases with unit tests. For example test non-intersecting rectangles:

@Test(expected = IllegalArgumentException.class)
public void testNonIntersectingRectangles() {
    OverlappingRectangles.fetchIntersectingRectangle(new RectangleWithHeightAndWidth(10, 20, 20, 20),
            new RectangleWithHeightAndWidth(120, 130, 20, 20));
}

Similarly, adding unit tests for the intersects method would be good too.

---

The classes RectangleWithPoints and RectangleWithHeightAndWidth are not general enough. One could be transformed to the other, so it would be better to have a single Rectangle class, with factory methods like createWithPoints and createWithHeightAndWidth. That would eliminate a lot of your duplicated code, as only one equals, toString, hashCode and intersects would be enough.

---

Name your variables and methods consistently: either use leftTopX and getLeftTopX everywhere or topLeftX and getTopLeftX everywhere but don't mix both here and there.

---

About toString, the SO discussion you linked is concerning StringBuilder versus concatenation efficiency. In case of your toString methods, performance doesn't matter. You only need to optimize string concatenation in specific situations where performance really matters and the method is called millions of times. In toString methods like yours I use this less efficient but more readable format:

return String.format("TopLeftPoint: (%s,%s) BottomRightPoint: (%s,%s)",
        topLeftX, topLeftY, bottomRightX, bottomRightY);

---

A more common and compact form of your equals method would be:

@Override
public boolean equals(Object obj) {
    if (obj instanceof RectangleWithPoints) {
        RectangleWithPoints other = (RectangleWithPoints) obj;
        return leftTopX == other.leftTopX
                && leftTopY == other.leftTopY
                && rightBottomX == other.rightBottomX
                && rightBottomY == other.rightBottomY;
    }
    return false;
}

---

I would rename fecthIntersectingRectangle to getIntersectingRectangle. The word "fetch" usually evokes downloading something from a remote service or database.

---

It might make sense to move the methods of the OverlappingRectangles utility class inside your new refactored Rectangle. It depends on your use case.

See my refactored version on GitHub (taking hints from @david-harkness as well).

Answer 2

You can simplify your model by using left, right/width, bottom, and top/height values. The name leftTopX is superfluous because the left edge's x coordinate will be the same at the top and bottom in any rectangle.

Even though you store the four sides in one implementation and the height and width in the other, you could still provide the full set of accessors for both. For example,

public int getWidth() {
    return width;
}

public int getRight() {
    return left + width;
}

You can simplify your intersection methods by employing min and max. It would be nice to make these instance methods of the rectangle classes at the same time and introduce some static factory methods.

public Rectangle intersection(Rectangle other) {
    return Rectangle.fromFourSides(
            Math.max(left, other.left), Math.min(top, other.top), 
            Math.min(right, other.right), Math.max(bottom, other.bottom));
}

Move the validity check into the Rectangle constructors so you don't have to check everywhere you want to create one.

public Rectangle(left, top, right, bottom) {
    if (left >= right) {
        throw new IllegalArgumentException("Width must be positive");
    }
    if (bottom >= top) {
        throw new IllegalArgumentException("Height must be positive");
    }
}