Microsoft Interview Question Software Engineer / Developers
I would use the centers of the rectangles. Let h1, w1 denote height and width of the first rectangle and so on. Then if the difference between y coordinates of the centers is smaller than (h1+h2)/2 they intersect. Similarly if the difference between the x coordinates of the centers is smaller than (w1+w2)/2 they intersect
Almost. You can't assume they intersect if one condition is fulfilled or the other. Your example would pass if two rectangles had centers at the same y value but were very far apart from each other and never intersected. You would need to verify that |y2-y1| <= (h1+h2)/2 AND |x2-x1| <= (w1+w2)/2.
#include <math.h>
#define _X 1
#define _Y 0
typedef struct rectangle {
int x1; /* bottom side of rectangle */
int y2; /* left side of rectangle */
int width;
int height;
} rectangle;
int get_center(rectangle *r, int is_x) {
if (r == NULL)
return 0;
if (is_x)
return ((r->x1+r->width)/2);
else
return ((r->y1+r->height)/2);
}
int intersecting(rectangle *r1, rectangle *r2) {
int r1cx, r1cy, r2cx, r2cy;
if (r1 == NULL || r2 == NULL)
return;
r1cx = get_center(r1, IS_X);
r2cx = get_center(r1, IS_X);
r1cy = get_center(r2, IS_Y);
r1cy = get_center(r2, IS_Y);
if ((abs(r1cx-r2cx) <= (r1->width+r2->width)/2) && \
(abs(r1cy-r2cy) <= (r1->height+r2->height)/2))
return true;
return false;
}
pardon small typos if there are any; didn't compile this.
public boolean intersects(Rectangle r, Rectangle r1) {
- zhan February 22, 2011int tw = r1.width;
int th = r1.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = r1.x;
int ty = r1.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}