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条回答 默认 最新

  • 已采纳
    weixin_41568208 北城已荒凉 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 评论 复制链接分享
  • csdnceshi70 笑故挽风 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};
        // bottom-left: xs[1], ys[1]
        // top-right:   xs[2], ys[2]
    点赞 9 评论 复制链接分享
  • weixin_41568110 七度&光 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
    rect1_y_radius = (y2-y1)/2


    rect2_x_radius = (x4-x3)/2
    rect2_y_radius = (y4-y3)/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.


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

    enter image description here

    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
        // 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:

    enter image description here

    点赞 6 评论 复制链接分享