common_area_of_two_rectangles_v1.c

/*

    common_area_of_two_rectangles_v1.c

    Task from:
    Radoslav Mincev
    https://www.facebook.com/groups/217159954971669/user/100001229417895/

    Facebook group:
    https://www.facebook.com/groups/cppInPracticeQuestions/

    Task:
    https://www.facebook.com/dmilicev/posts/10224433354287423:10

You are given a 2d coordinate system.
Each rectangle can be defined with 4 numbers with a floating point,
its coordinates of its low left angle ( x, y ) , its width and height.

Write a program that reads from the input, defines two rectangles
( based on the numbers of the input ) and gives you an output of the area
of the their intersecting ( overlapping ) part.
If there is no intersection the program should give you an output of 0.

Note:
It may be assumed that the rectangles are parallel to the coordinate axis.

Example :

Input :                  output
0053
4133                         2

0022
-1-111                       0

We shouldn't be using arrays and loops in the code.


https://www.geeksforgeeks.org/find-two-rectangles-overlap/
https://practice.geeksforgeeks.org/problems/overlapping-rectangles/0
https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
https://practice.geeksforgeeks.org/problems/check-if-two-line-segments-intersect/0
https://stackoverflow.com/questions/25070577/sort-4-numbers-without-array


A nice way to do small, fixed-size sorts is using a sorting network:
https://en.wikipedia.org/wiki/Sorting_network

int tmp;
if (a > b) { tmp = a; a = b; b = tmp; }
if (c > d) { tmp = c; c = d; d = tmp; }
if (a > c) { tmp = a; a = c; c = tmp; }
if (b > d) { tmp = b; b = d; d = tmp; }
if (b > c) { tmp = b; b = c; c = tmp; }

Each line codes a comparison and swap between two elements.
You can use this page to generate optimal sorting networks for small numbers of inputs.
http://pages.ripco.net/~jgamble/nw.html
To sort in reverse order, just flip the > signs to < signs.


Rectangle R1(x1,y1,w1,h1)

  x1,y1+h1         x1+w1,y1+h1
    ---------------------
    |                   |
    |                   |
    |                   |
    |                   |
    ---------------------
  x1,y1            x1+w1,y1



Rectangle R1(x1,y1,w1,h1) and
Rectangle R2(x2,y2,w2,h2)

              x2,y2+h2               x2+w2,y2+h2
                ---------------------------
                |                         |
                |                         |
  x1,y1+h1      |    x1+w1,y1+h1          |
    ------------|----------               |
    |           |         |               |
    |           |         |               |
    |           |         |               |
    |           ----------|----------------
    |         x2,y2       |          x2+w2,y2
    |                     |
    |                     |
    -----------------------
  x1,y1              x1+w1,y1


To simplify (halve) the problem, let's start by looking at just x point coordinates.

    ----------          -----------
    x1     x1+w1        x2      x2+w2

 L1begin   L1end     L2begin    L2end

after sorting:

 first     second   third       fourth


Let us find the overlap length of these two lengths.

Let's name the appropriate coordinates with the names
L1begin,   L1end,     L2begin,    L2end
and assign them the appropriate values.

Then let's sort those four coordinates by values but remembering their names
and remembering their sort order
first, second, third, fourth.

There are 6 possible cases:

1. L1 is to the left of L2, no overlap
    ----------          -----------
 L1begin   L1end     L2begin    L2end


2. L2 is to the left of L1, no overlap
    ----------          -----------
 L2begin   L2end     L1begin    L1end


3. L1 is to the left of L2, overlap is L1end-L2begin
    -----------------------
 L1begin                L1end
                -----------------------
             L2begin                L2end


4. L2 is to the left of L1, overlap is L2end-L1begin
    -----------------------
 L2begin                L2end
                -----------------------
             L1begin                L1end


5. L2 is inside L1, overlap is L2end-L2begin
    -------------------------------------
 L1begin                              L1end
            ---------------------
         L2begin              L2end


6. L1 is inside L2, overlap is L1end-L1begin
            ---------------------
         L1begin              L1end
    -------------------------------------
 L2begin                              L2end


Now we know the x-axis overlap, similarly done for the y-axis.

The overlap area is obtained by multiplying these two values.


    You can find all my C++ programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>
#include <string.h>

struct Point
{
    float x, y;
    char name[10];              // begin, end
};

struct Rectangle
{
    float x, y, width, height;  // x,y are coordinates of Down Left point
};

// To sort in decrease order, just flip the > signs to < signs.
void sort_by_x_four_numbers( struct Point *a,
                             struct Point *b,
                             struct Point *c,
                             struct Point *d )
{
    struct Point tmp;

    if ( (*a).x > (*b).x )              // (*a).x  is same as  a->num
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }

    if ((*c).x > (*d).x)
    {
        tmp = *c;
        *c = *d;
        *d = tmp;
    }

    if ((*a).x > (*c).x)
    {
        tmp = *a;
        *a = *c;
        *c = tmp;
    }

    if ((*b).x > (*d).x)
    {
        tmp = *b;
        *b = *d;
        *d = tmp;
    }

    if ((*b).x > (*c).x)
    {
        tmp = *b;
        *b = *c;
        *c = tmp;
    }
}

// To sort in decrease order, just flip the > signs to < signs.
void sort_by_y_four_numbers( struct Point *a,
                             struct Point *b,
                             struct Point *c,
                             struct Point *d )
{
    struct Point tmp;

    if ( (*a).y > (*b).y )              // (*a).y  is same as  a->num
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }

    if ((*c).y > (*d).y)
    {
        tmp = *c;
        *c = *d;
        *d = tmp;
    }

    if ((*a).y > (*c).y)
    {
        tmp = *a;
        *a = *c;
        *c = tmp;
    }

    if ((*b).y > (*d).y)
    {
        tmp = *b;
        *b = *d;
        *d = tmp;
    }

    if ((*b).y > (*c).y)
    {
        tmp = *b;
        *b = *c;
        *c = tmp;
    }
}


int main(void)
{
    struct Rectangle R1, R2;
    struct Point L1begin, L1end, L2begin, L2end, tmp;
    float lineXoverlap=0.0, lineYoverlap=0.0, overlapArea;
    float L1b, L1e, L2b, L2e;   // b stands for begin, e stands for end

    R1.x = 0.0;                 // input values for rectangle R1
    R1.y = 0.0;
    R1.width = 3.0;
    R1.height = 5.0;

    R2.x = 2.0;                 // input values for rectangle R1
    R2.y = 1.0;
    R2.width = 3.0;
    R2.height = 6.0;

/*
    -----------------           -----------------
    x1          x1+w1           x2          x2+w2

    R1.x        R1.x+R1.width   R2.x        R2.x+R2.width
    L1begin     L1end           L2begin     L2end
    first       second          third       fourth

after sorting (only for example) :

    fourth      second          first       third
*/

    // let's find lineXoverlap

    L1begin.x = R1.x;                   // make four x numbers
    sprintf(L1begin.name, "L1begin");

    L1end.x = R1.x + R1.width;
    sprintf(L1end.name, "L1end");


    L2begin.x = R2.x;
    sprintf(L2begin.name, "L2begin");

    L2end.x = R2.x + R2.width;
    sprintf(L2end.name, "L2end");

    // remember four numbers before sorting
    L1b = L1begin.x;
    L1e = L1end.x;
    L2b = L2begin.x;
    L2e = L2end.x;

    // let's sort these four numbers, without arrays and loops
    sort_by_x_four_numbers( &L1begin, &L1end, &L2begin, &L2end );

    // let's calculate lineXoverlap

/*
3. L1 is to the left of L2, overlap is L1end-L2begin
    -----------------------
 L1begin                L1end
                -----------------------
             L2begin                L2end
*/
    if ( strcmp(L1begin.name, "L1begin") == 0 &&
         strcmp(L1end.name, "L2begin")   == 0 &&
         strcmp(L2begin.name, "L1end")   == 0
       )
        lineXoverlap = L1e - L2b;

/*
4. L2 is to the left of L1, overlap is L2end-L1begin
    -----------------------
 L2begin                L2end
                -----------------------
             L1begin                L1end
*/
    if ( strcmp(L1begin.name, "L2begin") == 0 &&
         strcmp(L1end.name, "L1begin")   == 0 &&
         strcmp(L2begin.name, "L2end")   == 0
       )
        lineXoverlap = L2e - L1b;

/*
5. L2 is inside L1, overlap is L2end-L2begin
    -------------------------------------
 L1begin                              L1end
            ---------------------
         L2begin              L2end
*/
    if ( strcmp(L1begin.name, "L1begin") == 0 &&
         strcmp(L1end.name, "L2begin")   == 0 &&
         strcmp(L2begin.name, "L2end")   == 0
       )
        lineXoverlap = L2e - L2b;

/*
6. L1 is inside L2, overlap is L1end-L1begin
            ---------------------
         L1begin              L1end
    -------------------------------------
 L2begin                              L2end
*/
    if ( strcmp(L1begin.name, "L2begin") == 0 &&
         strcmp(L1end.name, "L1begin")   == 0 &&
         strcmp(L2begin.name, "L1end")   == 0
       )
        lineXoverlap = L1e - L1b;

    printf("\n lineXoverlap = %.2f \n", lineXoverlap);



    // let's find lineYoverlap

    L1begin.y = R1.y;                   // make four y numbers
    sprintf(L1begin.name, "L1begin");

    L1end.y = R1.y + R1.height;
    sprintf(L1end.name, "L1end");


    L2begin.y = R2.y;
    sprintf(L2begin.name, "L2begin");

    L2end.y = R2.y + R2.height;
    sprintf(L2end.name, "L2end");

    // remember four numbers before sorting
    L1b = L1begin.y;
    L1e = L1end.y;
    L2b = L2begin.y;
    L2e = L2end.y;


    // let's sort these four numbers, without arrays and loops
    sort_by_y_four_numbers( &L1begin, &L1end, &L2begin, &L2end );

    // let's calculate lineYoverlap

/*
3. L1 is to the left of L2, overlap is L1end-L2begin
    -----------------------
 L1begin                L1end
                -----------------------
             L2begin                L2end
*/
    if ( strcmp(L1begin.name, "L1begin") == 0 &&
         strcmp(L1end.name, "L2begin")   == 0 &&
         strcmp(L2begin.name, "L1end")   == 0
       )
        lineYoverlap = L1e - L2b;

/*
4. L2 is to the left of L1, overlap is L2end-L1begin
    -----------------------
 L2begin                L2end
                -----------------------
             L1begin                L1end
*/
    if ( strcmp(L1begin.name, "L2begin") == 0 &&
         strcmp(L1end.name, "L1begin")   == 0 &&
         strcmp(L2begin.name, "L2end")   == 0
       )
        lineYoverlap = L2e - L1b;

/*
5. L2 is inside L1, overlap is L2end-L2begin
    -------------------------------------
 L1begin                              L1end
            ---------------------
         L2begin              L2end
*/
    if ( strcmp(L1begin.name, "L1begin") == 0 &&
         strcmp(L1end.name, "L2begin")   == 0 &&
         strcmp(L2begin.name, "L2end")   == 0
       )
        lineYoverlap = L2e - L2b;

/*
6. L1 is inside L2, overlap is L1end-L1begin
            ---------------------
         L1begin              L1end
    -------------------------------------
 L2begin                              L2end
*/
    if ( strcmp(L1begin.name, "L2begin") == 0 &&
         strcmp(L1end.name, "L1begin")   == 0 &&
         strcmp(L2begin.name, "L1end")   == 0
       )
        lineYoverlap = L1e - L1b;


    printf("\n lineYoverlap = %.2f \n", lineYoverlap);


    // let's calculate overlapArea
    overlapArea = lineXoverlap * lineYoverlap;

    printf("\n\n Overlap area = %.2f \n", overlapArea);


    return 0;

} // main()