交叉矩形的总面积

Question

我需要一个算法来解决这个问题:给定2个在任何角落交叉或重叠的矩形,如何确定没有重叠(交叉)区域的两个矩形的总面积？意味着必须使用第一个矩形或第二个矩形计算一次交叉区域.

Answer 1

这很简单.首先计算交点的坐标,也是一个矩形.

left = max(r1.left, r2.left)
right = min(r1.right, r2.right)
bottom = max(r1.bottom, r2.bottom)
top = min(r1.top, r2.top)

然后,如果交集不为空(left < right && bottom < top),则从两个矩形的公共区域中减去它:r1.area + r2.area - intersection.area.

PS:

1. 假设1:矩形通过坐标轴对齐,通常就是这种情况.
2. 假设2: y轴在这里向上增加,例如,在图形应用程序中,y轴向下增加,您可能需要使用:

bottom = min(r1.bottom, r2.bottom) top = max(r1.top, r2.top)

Answer 2

以下是使用Java的此算法的完整解决方案:

public static int solution(int K, int L, int M, int N, int P, int Q, int R,
        int S) {
    int left = Math.max(K, P);
    int right = Math.min(M, R);
    int bottom = Math.max(L, Q);
    int top = Math.min(N, S);

    if (left < right && bottom < top) {
        int interSection = (right - left) * (top - bottom);
        int unionArea = ((M - K) * (N - L)) + ((R - P) * (S - Q))
                - interSection;
        return unionArea;
    }
    return 0;
} 

Answer 3

我看到这个问题没有得到解答所以我写了一个小的java程序来试试@VicJordan和@NikitaRybak在之前的答案中谈过的等式.希望这可以帮助.

/**
 * This function tries to see how much of the smallest rectangle intersects 
 * the with the larger one. In this case we call the rectangles a and b and we 
 * give them both two points x1,y1 and x2, y2.
 * 
 * First we check for the rightmost left coordinate. Then the leftmost right 
 * coordinate and so on. When we have iLeft,iRight,iTop,iBottom we try to get the 
 * intersection points lenght's right - left and bottom - top.
 * These lenght's we multiply to get the intersection area.
 *
 * Lastly we return the result of what we get when we add the two areas 
 * and remove the intersection area.
 * 
 * @param xa1       left x coordinate   A
 * @param ya1       top y coordinate    A
 * @param xa2       right x coordinate  A
 * @param ya2       bottom y coordinate A
 * @param xb1       left x coordinate   B
 * @param yb1       top y coordinate    B
 * @param xb2       right x coordinate  B
 * @param yb2       bottom y coordinate B
 * @return          Total area without the extra intersection area.
 */

public static float mostlyIntersects(float xa1, float ya1, float xa2, float ya2, float xb1, float yb1, float xb2, float yb2) {
    float iLeft = Math.max(xa1, xb1);
    float iRight = Math.min(xa2, xb2);
    float iTop = Math.max(ya1, yb1);
    float iBottom = Math.min(ya2, yb2);

    float si = Math.max(0, iRight - iLeft) * Math.max(0, iBottom - iTop);
    float sa = (xa2 - xa1) * (ya2 - ya1);
    float sb = (xb2 - xb1) * (yb2 - yb1);

    return sa + sb - si;
}