How to subtract two rectangles?

user_14319953 0
Viewed 219

I am wondering how to get the Set Subtraction between two rectangles with "parallel edges" in an efficient way. Thank you in advance for you help!

Problem: We know that each rectangle can be encoded by four parameters. Now, assume that we have 2 rectangles region1 and region2 and we want to get the set subtraction (a.k.a set complement, set difference see wiki) region1 - region2, which is a union of some smaller rectangles. How can we encoded these resulting rectangles efficiently?

My efforts:

  1. At the beginning, I did it by considering all the possible positions of the two rectangles (there are at least 10 main cases by fixing region1 and moving region2 and many sub-cases). But of course, this is not a good strategy.

  2. I found a similar post here but it is not exactly the problem I consider here and the code provided is in C# (which I don't know) and the answer there has no explanation.

  3. I then post my question in Math Stack Exchange and got a promising answer as follows:

There are four x-coordinates and four y-coordinates involved, which together determine a total of 9 sub-rectangles; and you can just check their centers one by one to see whether they are in region1 and not in region2.

I then try to program it using python (I just know Python). Here is my code. But I think it is unclean, unclear and unreadable. In addition, it is not very efficient since the rectangles with common edges have not been merged.

def substraction(region1, region2):
    # return region1 \ region2
    # region = [(x1,x2), (y1,y2)]
    assert(len(region1) == 2 and  len(region2) == 2)
    (r1x1, r1x2), (r1y1, r1y2) = region1
    (r2x1, r2x2), (r2y1, r2y2) = region2
    x1, x2, x3, x4 = sorted([r1x1, r1x2, r2x1, r2x2])
    y1, y2, y3, y4 = sorted([r1y1, r1y2, r2y1, r2y2])
    out=[]
    for x in [(x1, x2), (x2, x3), (x3, x4)]:
        for y in [(y1, y2), (y2, y3), (y3, y4)]:
            xm, ym = (x[0]+x[1])/2, (y[0]+y[1])/2
            bool1_x = xm>r1x1 and xm<r1x2
            bool1_y = ym>r1y1 and ym<r1y2
            bool2_x = xm<=r2x1 or xm>=r2x2
            bool2_y = ym<=r2y1 or ym>=r2y2
            if (bool1_x and bool1_y) and (bool2_x or bool2_y):
                out += [ [x, y] ]    
    return out

def test():
    region1=[(0., 1.), (0., 1.)]
    region2=[(0.4, 1.5), (0.4, 0.6)]
    list_rects=substraction(region1, region2)
    print(list_rects)

test()

Could anyone give an idea how to improve my code. A new efficient solution is also welcome! Thank you!

rectangles math python
1 Answers

A simple solution in C#

Еdit: Fix the case of (subtrahend.IsEmpty) so the code do not return zero area rectangles. See comments for scenarios where touching rectangles are returned

    //-------------------------
    //|          A            |
    //|-----------------------|
    //|  B  |   hole    |  C  |
    //|-----------------------|
    //|          D            |
    //-------------------------
    public static IEnumerable<Rectangle> Subtract(this 
        Rectangle minuend,
        Rectangle subtrahend)
    {
        subtrahend.Intersect(minuend);
        //if (subtrahend.IsEmpty)
        //if (subtrahend.Size.IsEmpty)
        if (subtrahend.Width*subtrahend.Height == 0)
        {
            yield return minuend;
            yield break;
        }

        //A
        var heightA = subtrahend.Top - minuend.Top;
        if (heightA > 0)
            yield return new Rectangle(
                minuend.Left,
                minuend.Top,
                minuend.Width,
                heightA);

        //B
        var widthB = subtrahend.Left - minuend.Left;
        if (widthB > 0)
            yield return new Rectangle(
                minuend.Left,
                subtrahend.Top,
                widthB,
                subtrahend.Height);

        //C
        var widthC = minuend.Right - subtrahend.Right;
        if (widthC > 0)
            yield return new Rectangle(
                subtrahend.Right,
                subtrahend.Top,
                widthC,
                subtrahend.Height);

        //D
        var heightD = minuend.Bottom - subtrahend.Bottom;
        if (heightD > 0)
            yield return new Rectangle(
                minuend.Left,
                subtrahend.Bottom,
                minuend.Width,
                heightD);
    }
user_93424640
Related