###### 10.24

2013-11-03 12:52 阅读 566

# 得到两个矩形的交点

Let say that we have two rectangles, defined with their bottom-left and top-right corners. For example: rect1 (x1, y1)(x2, y2) and rect2 (x3, y3)(x4, y4). I'm trying to find the coordinates(bottom-left and top-right) of the intersected rectangle.

Any ideas, algorithm, pseudo code, would be greatly appreciated.

p.s. I found similar questions but they check only if 2 rectangle intersect.

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享

#### 3条回答默认 最新

• 已采纳
北城已荒凉 2013-11-03 16:03

If the input rectangles are normalized, i.e. you already know that `x1 < x2`, `y1 < y2` (and the same for the second rectangle), then all you need to do is calculate

``````int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);
``````

and it will give you your intersection as rectangle `(x5, y5)-(x6, y6)`. If the original rectangles do not intersect, the result will be a "degenerate" rectangle (with `x5 >= x6` and/or `y5 >= y6`), which you can easily check for.

P.S. As usual, small details will depend on whether you have to consider touching rectangles as intersecting.

点赞 6 评论 复制链接分享
• 笑故挽风 2013-11-03 13:15

You can deal with the `x` and `y` direction separately.

Assume that `x1 <= x3` (the first box is at least as far to the left as the second). Then, there is overlap if and only if `x1 <= x3 <= x2`.

Similarly, assume `y1 <= y3` (the first box is at least as far to the bottom as the second). Then, there is overlap if and only if `y1 <= y3 <= y2`.

If there is overlap in both directions, there is a rectangle overlapping. You can find the coordinates by sorting the `x` and `y` coordinates and selecting the middle two.

In pseudocode:

``````if (((x1 <= x3 && x3 <= x2) || (x3 <= x1 && x1 <= x4)) // x-overlap
&&
((y1 <= y3 && y3 <= y2) || (y3 <= y1 && y1 <= y4)) // y-overlap
) {
int[] xs = {x1, x2, x3, x4};
int[] ys = {y1, y2, y3, y4};
sort(xs);
sort(ys);

// bottom-left: xs[1], ys[1]
// top-right:   xs[2], ys[2]
}
``````
点赞 9 评论 复制链接分享
• 七度＆光 2013-11-03 13:02

Let's say that a box has a radius X and radius Y (I know it has not but this term is useful here).

You will have:

``````rect1_x_radius = (x2-x1)/2
``````

and

``````rect2_x_radius = (x4-x3)/2
``````

Now if rect middle points are further away than sum of their radiuses in appropriate direction - they do not collide. Otherwise they do - this hint should suffice.

You should be now able to finish your assignment.

UPDATE:

OK - let's solve it for 1D - later you'll solve it for 2D. Look at this piece of ... art ;-)

You see 2 segments - now some calculations:

``````rA = (maxA-minA) / 2
rB = (maxB-minB) / 2

midA = minA + rA
midB = minB + rB

mid_dist = |midA - midB|
``````

Now how to check if collision occurs? As I said if sum of 'radiuses' is less than segments' distance - there is no collision:

``````if ( mid_dist > fabs(rA+rB) )
{
// no intersection
}
else
{
// segments intersect
}
``````

Now it is your work to calculate intersection / common part in 1D and 2D. It is up to you now (o ryou can read Andrey's answer).

Here is the same situation but in 2D - two 1D situations:

点赞 6 评论 复制链接分享