枚举两个矩形的非公共部分的整数点

Question

我有两个与坐标轴平行且坐标为整数的矩形。

我有四个坐标：第一个矩形的左上角和右下角，第二个矩形的左上角和右下角。坐标 left-top 总是在 right-bottom 的顶部和左侧。

矩形可以部分相交、完全相交或完全不相交。我需要枚举不在第二个矩形内的第一个矩形的点，以及不在第一个矩形内的第二个矩形的点。

Example

另外，我需要比O(h1*w1+h2*w2)做得更好，最好是O(结果点数)。

Answer 1

Rectangles can intersect partially, fully, or not intersect at all.

让我们调查一下每个场景中的问题：

1.当它们不相交时： 您需要枚举两个矩形的所有点。

2。当它们完全相交时： 在这种情况下，您可以简单地遍历较大矩形的所有点并检查它们是否在交点内。但要改进它并迭代结果，您可以将其划分为 8 个不同的分区：

现在可以枚举每个分区的所有点了

3。当它们部分相交时： 这可以被认为是前一个的特例，其中 8 个分区中的一些无效：

结论： 在下面的伪代码中，每个矩形都由一个 4 元素数组表示，例如：[left top right bottom].

procedure isValid(R)
    return R(1)<=R(3) & R(2)<=(R4)
end

procedure enumerateRectangle(R)
    if isValid(R)
        for i = R(1) to R(3)
            for j = R(2) to R(4)
                visit(i, j)
end

procedure enumerateNonIntersection(R, I)
    enumerateRectangle([R(1),       R(2),       I(1)-1,     I(2)-1])    // top-left
    enumerateRectangle([R(1),       I(2),       I(1)-1,     I(4)])      // left
    enumerateRectangle([R(1),       I(4)+1,     I(1)-1,     R(4)])      // bottom-left

    enumerateRectangle([RI(1),      R(2),       I(3),       I(2)-1])    // top
    enumerateRectangle([RI(1),      I(4)+1,     I(3),       R(4)])      // bottom

    enumerateRectangle([I(3)+1,     R(2),       R(3),       I(2)-1])    // top-right
    enumerateRectangle([I(3)+1,     I(2),       R(3),       I(4)])      // right
    enumerateRectangle([I(3)+1,     I(4)+1,     R(3),       R(4)])      // bottom-right
end

procedure enumerateExclusiveOr(R1, R2)
    I = intersectionOf(R1, R2)
    if isValid(I)
        enumerateNonIntersection(R1, I)
        enumerateNonIntersection(R2, I)
    else
        enumerateRectangle(R1)
        enumerateRectangle(R2)
    end
end

枚举两个矩形的非公共部分的整数点

Enumerate integer points of non-common parts of two rectangles

geometry

intersection

rectangles