Enumerate integer points of non-common parts of two rectangles

Question

I have two rectangles which is parallel with axis of coordinates and have integer coordinates.

I have four coordinates: left-top and right-bottom of first rectangle, left-top and right-bottom of second rectangle. Coordinate left-top is always to top and to left of right-bottom.

Rectangles can intersect partially, fully, or not intersect at all. I need to enumerate points of first rectangle which aren't inside the second one, and points of second rectangle which aren't inside the first one.

Example

Also, I need to do it much better than O(h1*w1+h2*w2), the best is O(count of result points).

saastn saastn · Accepted Answer · 2019-05-03T21:19:19

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

Let's investigate the problem in each scenario:

1. When they don't intersect: You need to enumerate all points of both rectangles.

2. When they fully intersect: In this scenario you can simply iterate over all points of the bigger rectangle and check if they are inside of the intersection. But to improve it and just iterate over the results you can divide it to 8 different partitions:

Now you can enumerate all points of each partition.

3. When they partially intersect: This can be considered as a special case for the previous one, where some of those 8 partitions are invalid:

Conclusion: In the following pseudocode each rectangle is represented by a 4 element array like: [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

1 Answers