How to find out whether the largest rectangle contains other smaller rectangles-CodePudding

I have to create a program that generates 3 random rectangles and finds the area of each using the coordinates of the upper left point and the bottom right point (coordinates are random and between (-50;50).

The problem is that it must determine the largest rectangle and indicate whether the other two/one are/is located in it, if not - display the corresponding message.

It's not a overlap, other rectangles/rectangle must be fully in the biggest one.

Here is what I've already done:

#include <stdio.h> 
#include <locale>

struct Point {
    int x;
    int y;
};

struct Rectangle {
    struct Point topLeft;
    struct Point botRight;
};

int Area(struct Rectangle r) {
    int length, breadth;
    length = r.botRight.x - r.topLeft.x;
    breadth = r.topLeft.y - r.botRight.y;

    return length * breadth;
}

int main() {
    srand(time(NULL));

    struct Rectangle r1, r2, r3;
    
    r1.topLeft.x  = -50   rand() % 50;
    r1.topLeft.y  = -50   rand() % 50;
    r1.botRight.x = -50   rand() % 50;
    r1.botRight.y = -50   rand() % 50;

    while (r1.botRight.x <= r1.topLeft.x) {
        r1.botRight.x = -50   rand() % 50;
    }
    while (r1.topLeft.y <= r1.botRight.y) {
        r1.topLeft.y = -50   rand() % 50;
    }
    printf("\t----------RECTANGLE 1----------\n");
    printf("\tTop left point is x = %d y = %d\n", r1.topLeft.x, r1.topLeft.y);
    printf("\tBottom right point is x = %d y = %d\n", r1.botRight.x, r1.botRight.y);
    printf("\tArea is %d\n", Area(r1));
    
    r2.topLeft.x  = -50   rand() % 50;
    r2.topLeft.y  = -50   rand() % 50;
    r2.botRight.x = -50   rand() % 50;
    r2.botRight.y = -50   rand() % 50;

    while (r2.botRight.x <= r2.topLeft.x) {
        r2.botRight.x = -50   rand() % 50;
    }
    while (r2.topLeft.y <= r2.botRight.y) {
        r2.topLeft.y = -50   rand() % 50;
    }
    printf("\t----------RECTANGLE 2----------\n");
    printf("\tTop left point is x = %d y = %d\n", r2.topLeft.x, r2.topLeft.y);
    printf("\tBottom right point is x = %d y = %d\n", r2.botRight.x, r2.botRight.y);
    printf("\tArea is %d\n", Area(r2));
    
    r3.topLeft.x = -50   rand() % 50;
    r3.topLeft.y = -50   rand() % 50;
    r3.botRight.x = -50   rand() % 50;
    r3.botRight.y = -50   rand() % 50;

    while (r3.botRight.x <= r3.topLeft.x) {
        r3.botRight.x = -50   rand() % 50;
    }
    while (r3.topLeft.y <= r3.botRight.y) {
        r3.topLeft.y = -50   rand() % 50;
    }
    printf("\t----------RECTANGLE 3----------\n");
    printf("\tTop left point is x = %d y = %d\n", r3.topLeft.x, r3.topLeft.y);
    printf("\tBottom right point is x = %d y = %d\n", r3.botRight.x, r3.botRight.y);
    printf("\tArea is %d\n\n", Area(r3));
    
    if (Area(r1) >= Area(r2) && Area(r1) >= Area(r3))
        printf("\tRECTANGLE 1 HAS A BIGGEST AREA --> %d\n", Area(r1));
    
    if (Area(r2) >= Area(r1) && Area(r2) >= Area(r3))
        printf("\tRECTANGLE 2 HAS A BIGGEST AREA --> %d\n", Area(r2));

    if (Area(r3) >= Area(r1) && Area(r3) >= Area(r2))
        printf("\tRECTANGLE 3 HAS A BIGGEST AREA --> %d\n", Area(r3));
}

CodePudding user response：

First, you need an array of Rectangles and sort them by their area:

struct Rectangle rects[N];

//return:
//- negative value, if a < b
//- zero,           if a == b
//- positive value, if a > b
int rect_cmp(const void *a, const void *b)
{
    return Area(*((struct Rectangle*)a)) - Area(*((struct Rectangle*)b));
}

//use qsort: https://en.cppreference.com/w/c/algorithm/qsort
qsort(rects, N, sizeof(struct Rectangle), rect_cmp);

The array rects will now contain all the rectangles, sorted in ascending order, from lowest to highest area.

From now on, all you have to do is to iterate over the array and test if the largest rectangle encloses the following, subsequent rectangles. The following code picks the largest rectangle and iterates over all subsequent rectangles to test if they are inside. Then pick the second largest and do the testing again, and so on, e.g.

for (int i=N-1; i >= 0; --i) { //current largest rectangle
    for (int j=i-1; j >= 0; --j) { //test if the next rectangles in sequence are inside
        if (contains(rects[i], rects[j])) {
            //rect[j] inside rect[i]
        } else {
            //rect[j] not inside rect[i]
        }
    }
}

A possible outcome could be that the first rect neither contains the second and third rect but the second rect could contain the third one.

CodePudding user response：

Item 1:
There really is no need to use a point struct. The problem is simple enough to merely keep track to 2 values for x and 2 values for y. While we're at it, the area of each rectangle could be stored, too.

typedef struct {
    int x0, x1, y0, y1, area;
} Rect;

Notice that there is no bias in the names x0 and x1. Attempting to control which coordinate pair is "top left" and which is "bottom right" is difficult. A rectangle has two horizonal edges (importantly they are not equal). Merely store the lower and higher values of y. Similarly, store only the "left & right" values of the vertical edges x... This makes life simple.

Item 2:
It's worthwhile, if possible, to think and to code without immediate concern for negative numbers.

const int wid = 101; // for -50 to  50
const int hgt = 101; // for -50 to  50

Item 3:
Generating 3 sets of values by copy/paste of code indicates that this should be done in a function called 3 times. (Imagine the next assignment is "do the same for 20 rectangles.")

Below includes two bonus "branchless" functions that return the minimum or maximum of two integer values.

int min( int x, int y ) { return y ^ ((x^y) & -(x<y)); }
int max( int x, int y ) { return y ^ ((x^y) & -(x>y)); }

void genRect( Rect *r ) {
    int v0 = rand() % wid; // A random horizontal value (a vertical line)
    int v1 = ( v0   rand()%(wid-1) ) % wid; // A different horizontal value

    r->x0 = min( v0, v1 ); // the lower of the two values
    r->x1 = max( v0, v1 ); // and the higher

    // do the same for horizontal edges (vertical boundaries)
    v0 = rand() % hgt;
    v1 = ( r->y0   rand()%(hgt-1) ) % hgt;

    r->y0 = min( v0, v1 );
    r->y1 = max( v0, v1 );

    // calc and store the area, too
    r->area = (r->x1 - r->x0) * (r->y1 - r->y0);
}

Important to note is that the calculation of the second value for x and for y will never be the same as the first value. The OP code had the potential to generate a "left edge" at the right boundary, then enter an endless loop trying to generate a value that was always rejected.

As suggested in the other answer, it is now easy to qsort() the small array (big rectangles may contain smaller ones).

The search for one inside another is much simpler with comparing x0 against x0 and x1 against x1... (Likewise for the y dimension).

Because the code has been dealing with (0,0) to (100,100) inclusive, the output is where to tailor to suit the assignment.

void print( int n, Rect *r ) {
    printf( "Rect %d: BotLft(%d,%d) TopRgt(%d, %d) Area %d\n",
        n, r->x0 - 50, r->y0 - 50, r->x1 - 50, r->y1 - 50, r->area );
}

I leave it as an exercise for the reader to eliminate the arbitrary constants above.