CODEWITHSUNDEEP
javalogicintersection
Doug B
Doug B

Reputation: 175

Java method to find the rectangle that is the intersection of two rectangles using only left bottom point, width and height?

I have found the solution but wanted to ensure my logic is the most efficient. I feel that there is a better way. I have the (x,y) coordinate of the bottom left corner, height and width of 2 rectangles, and i need to return a third rectangle that is their intersection. I do not want to post the code as i feel it is cheating.

  1. I figure out which is furthest left and highest on the graph.
  2. I check if one completely overlaps the other, and reverse to see if the other completely overlaps the first on the X axis.
  3. I check for partial intersection on the X axis.
  4. I basically repeat steps 2 and 3 for the Y axis.
  5. I do some math and get the points of the rectangle based on those conditions.

I may be over thinking this and writing inefficient code. I already turned in a working program but would like to find the best way for my own knowledge. If someone could either agree or point me in the right direction, that would be great!

Upvotes: 12

Views: 50369

Answers (3)

William Morrison
William Morrison

Reputation: 11006

My variation of determining intersection of two rectangles in a small utility function.

//returns true when intersection is found, false otherwise.
//when returning true, rectangle 'out' holds the intersection of r1 and r2.
private static boolean intersection2(Rectangle r1, Rectangle r2,
        Rectangle out) {
    float xmin = Math.max(r1.x, r2.x);
    float xmax1 = r1.x + r1.width;
    float xmax2 = r2.x + r2.width;
    float xmax = Math.min(xmax1, xmax2);
    if (xmax > xmin) {
        float ymin = Math.max(r1.y, r2.y);
        float ymax1 = r1.y + r1.height;
        float ymax2 = r2.y + r2.height;
        float ymax = Math.min(ymax1, ymax2);
        if (ymax > ymin) {
            out.x = xmin;
            out.y = ymin;
            out.width = xmax - xmin;
            out.height = ymax - ymin;
            return true;
        }
    }
    return false;
}

Upvotes: 13

Michaël Sanchez
Michaël Sanchez

Reputation: 61

You can also use the Rectangle source code to compare with your own algorithm:

/**
 * Computes the intersection of this <code>Rectangle</code> with the
 * specified <code>Rectangle</code>. Returns a new <code>Rectangle</code>
 * that represents the intersection of the two rectangles.
 * If the two rectangles do not intersect, the result will be
 * an empty rectangle.
 *
 * @param     r   the specified <code>Rectangle</code>
 * @return    the largest <code>Rectangle</code> contained in both the
 *            specified <code>Rectangle</code> and in
 *            this <code>Rectangle</code>; or if the rectangles
 *            do not intersect, an empty rectangle.
 */
public Rectangle intersection(Rectangle r) {
    int tx1 = this.x;
    int ty1 = this.y;
    int rx1 = r.x;
    int ry1 = r.y;
    long tx2 = tx1; tx2 += this.width;
    long ty2 = ty1; ty2 += this.height;
    long rx2 = rx1; rx2 += r.width;
    long ry2 = ry1; ry2 += r.height;
    if (tx1 < rx1) tx1 = rx1;
    if (ty1 < ry1) ty1 = ry1;
    if (tx2 > rx2) tx2 = rx2;
    if (ty2 > ry2) ty2 = ry2;
    tx2 -= tx1;
    ty2 -= ty1;
    // tx2,ty2 will never overflow (they will never be
    // larger than the smallest of the two source w,h)
    // they might underflow, though...
    if (tx2 < Integer.MIN_VALUE) tx2 = Integer.MIN_VALUE;
    if (ty2 < Integer.MIN_VALUE) ty2 = Integer.MIN_VALUE;
    return new Rectangle(tx1, ty1, (int) tx2, (int) ty2);
}

Upvotes: 5

shuangwhywhy
shuangwhywhy

Reputation: 5625

Why not use JDK API to do this for you?

Rectangle rect1 = new Rectangle(100, 100, 200, 240);
Rectangle rect2 = new Rectangle(120, 80, 80, 120);
Rectangle intersection = rect1.intersection(rect2);

To use java.awt.Rectangle class, the parameters of the constructor are: x, y, width, height, in which x, y are the top-left corner of the rectangle. You can easily convert the bottom-left point to top-left.

I recommend the above, but if you really want to do it yourself, you can follow the steps below:

say (x1, y1), (x2, y2) are bottom-left and bottom-right corners of Rect1 respectively, (x3, y3), (x4, y4) are those of Rect2.

  • find the larger one of x1, x3 and the smaller one of x2, x4, say xL, xR respectively
    • if xL >= xR, then return no intersection else
  • find the larger one of y1, y3 and the smaller one of y2, y4, say yT, yB respectively
    • if yT >= yB, then return no intersection else
    • return (xL, yB, xR-xL, yB-yT).

A more Java-like pseudo code:

// Two rectangles, assume the class name is `Rect`
Rect r1 = new Rect(x1, y2, w1, h1);
Rect r2 = new Rect(x3, y4, w2, h2);

// get the coordinates of other points needed later:
int x2 = x1 + w1;
int x4 = x3 + w2;
int y1 = y2 - h1;
int y3 = y4 - h2;

// find intersection:
int xL = Math.max(x1, x3);
int xR = Math.min(x2, x4);
if (xR <= xL)
    return null;
else {
    int yT = Math.max(y1, y3);
    int yB = Math.min(y2, y4);
    if (yB <= yT)
        return null;
    else
        return new Rect(xL, yB, xR-xL, yB-yT);
}

As you see, if your rectangle was originally defined by two diagonal corners, it will be easier, you only need to do the // find intersection part.

Upvotes: 21

Related Questions