Rectangle Overlap

There is some severe weather in the Texas area which should affect the Twin Cities of Minneapolis and St. Paul later today and tomorrow morning. Hopefully it will not be too bad.

On the local news members of the Black Lives Matter movement vandalized and looted several blocks of tall buildings in the down town of the Minneapolis business area. Not sure what was the point of the protests which just create problems for regular people that work and live in that area of the Twin Cities. This time around, the mayor of Minneapolis and the governor of Minnesota immediately called for the Minneapolis police, Minnesota State troopers, and National Guard to stop the vandals and looters. Will see how this sage develops in the next few days.

I decided to go for the LeetCode problem 836. Rectangle Overlap. If interested read the requirements at the LeetCode site. Once you understand the requirements take the time to thinks about an approach. Perhaps go for a pass before taking a look at this post.

A rectangle is represented as a list [x1, y1, x2, y2], 
where (x1, y1) are the coordinates of its bottom-left corner, 
and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive.
To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

It is important to understand how the rectangles are defined. In this case by the coordinates of the bottom left corner followed by the coordinates of the top right corner. It is important to make sure (end conditions) that you understand how overlap is defined.

    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {  
    }

The requirements call for one to write the code inside the specified function.

0,0,2,2
1,1,3,3

main <<< rec1: [0, 0, 2, 2]
main <<< rec2: [1, 1, 3, 3]
main <<< overlap: true


0,0,1,1
1,0,2,1

main <<< rec1: [0, 0, 1, 1]
main <<< rec2: [1, 0, 2, 1]
main <<< overlap: false


1,12,13,13
17,1,17,19

main <<< rec1: [11, 12, 13, 13]
main <<< rec2: [17, 1, 17, 19]
main <<< overlap: false


7,8,13,15
10,8,12,20

main <<< rec1: [7, 8, 13, 15]
main <<< rec2: [10, 8, 12, 20]
main <<< overlap: true


7,8,13,15
7,8,13,15

main <<< rec1: [7, 8, 13, 15]
main <<< rec2: [7, 8, 13, 15]
main <<< overlap: true

It shows how the scaffolding that I implemented reads in the data. The first line holds the coordinates for the lower left and upper right corners of the first rectangle. The second line repeats for the corners of the second rectangle. For convenience I separated the values by ‘,’s.

The test scaffolding appears to read the lines and populate two arrays. This appears to be needed as arguments to the function we need to implement as a solution.

The first set implements test 1 and the second test 2. The returned values seem to match the expected results.

There are three other tests cases, some of which came from the LeetCode web site.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {

        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read values for rec1 ****
        String[] vals = sc.nextLine().split(",");

        // **** populate rec1 ****
        int[] rec1 = new int[4];
        for (int i = 0; i < rec1.length; i++) {
            rec1[i] = Integer.parseInt(vals[i]);
        }

        // ???? ????
        System.out.println("main <<< rec1: " + Arrays.toString(rec1));

        // **** read rec 2 ****
        vals = sc.nextLine().split(",");

        // **** populate rec1 ****
        int[] rec2 = new int[4];
        for (int i = 0; i < rec1.length; i++) {
            rec2[i] = Integer.parseInt(vals[i]);
        }

        // ???? ????
        System.out.println("main <<< rec2: " + Arrays.toString(rec2));

        // **** close scanner ****
        sc.close();
        
        // **** determine if the rectangles overlap ****
        boolean overlap = isRectangleOverlap(rec1, rec2);

        // ???? ????
        System.out.println("main <<< overlap: " + overlap);
    }

As I mentioned, the test scaffolding is provided by LeetCode. I prefer to use my computers and tools. For this problem I used the Java programming language and used the VSCode IDE running on a Windows 10 machine.

The first thing we do is open a scanner. We then read the first line and populate the first rectangle with the provided coordinates. The operation repeats for the second rectangle. I could have implemented a function but it was easier to copy, paste and edit a small set of lines. Please keep in mind that in production is it very important to use functions and methods when possible. Imagine we copy and paste the same code on different files and thanks to Murphy, the code will have a bug or needs to be updated. You will have to update the same set of lines all over the code and test it for possible new issues.

We are ready to close the scanner and make a call to the function we need to write. The returned value is then displayed.

Remember that all this code is not needed to solve the problem. LeetCode provides the test scaffolding as long as you are willing to use their development environment.

    /**
     * Given two (axis-aligned) rectangles, return whether they overlap.
     * 
     * Two rectangles overlap if the area of their intersection is positive.
     * To be clear, two rectangles that only touch at the corner or edges do not overlap.
     * 
     * Two rectangles do NOT overlap if one of the following conditions is true:
     * 
     * 1) One rectangle is above top edge of other rectangle.
     * 2) One rectangle is on left side of left edge of other rectangle.
     */
    static boolean isRectangleOverlap(int[] rec1, int[] rec2) {

        // **** one rectangle is on the left side of the left edge of the other ****
        if ((rec2[2] <= rec1[0]) ||             // rec2 LEFT of rec1
            (rec1[2] <= rec2[0]))               // rec1 LEFT of rec2
            return false;
                
        // **** one rectangle is is above the top edge of the other ****
        if ((rec2[1] >= rec1[3]) ||             // rec2 ABOVE rec1
            (rec1[1] >= rec2[3]))               // rec1 ABOVE rec2
            return false;

        // **** rectangles overlap ****
        return true;

        // // **** somewhat hard to folow ****
        // return  rec1[0] < rec2[2] &&         // rec1 LEFT of rec2
        //         rec1[1] < rec2[3] &&         // rec2 ABOVE rec1
        //         rec2[0] < rec1[2] &&         // rec2 LEFT of rec1
        //         rec2[1] < rec1[3];           // rec1 ABOVE rec2
    }

The key idea is how to solve the problem. I used to do a lot of work with graphics at different levels. To be honest with you, I did not remember exactly what needed to be done. After several minutes tinkering I recalled what had to be done.

The idea is to look at the two rectangles and decide if they meet the two conditions listed in the comment section of the function at hand. We need to first check if one rectangle is above the other in the coordinate space. If that passes then we need to check if one rectangle is on the side of the other. Note that we can check on top or on the bottom because the idea is the same. The same holds true for checking left or right as long as we use the rightmost or leftmost side on the other rectangle.

Please make sure you fully understand what is happening. One or more drawings should clear up the concept.

The code that is enabled implements the ideas here presented. Please take a look at the code and make sure you agree with it. We are just figuring out if one rectangle is left of the other and repeat it with the rectangles swapped.

On the second set of statements we check if one rectangle is above the other. We perform the checks for both rectangles by swapping them in the OR statement.

If all is well so far and we have not exited the function, then the rectangles do not overlap.

Once I had that done and my solution was accepted, I checked other solutions. Just Google the title of the problem and check other approaches. The return statement commented out works. The logic is hard to follow. I added the comments to each line. In production I would rather have the top code which would help me understand the logic of the code. It could also be that the author has moved to a different project or company and someone else has to follow and perhaps enhance the code.

I went back to LeetCode and tested the second approach. The executions times displayed were identical.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,715 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.