Advertisement
dmilicev

common_area_of_two_rectangles_v1.c

Nov 12th, 2020
842
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.61 KB
  1. /*
  2.  
  3.     common_area_of_two_rectangles_v1.c
  4.  
  5.     Task from:
  6.     Radoslav Mincev
  7.     https://www.facebook.com/groups/217159954971669/user/100001229417895/
  8.  
  9.     Facebook group:
  10.     https://www.facebook.com/groups/cppInPracticeQuestions/
  11.  
  12.     Task:
  13.     https://www.facebook.com/dmilicev/posts/10224433354287423:10
  14.  
  15. You are given a 2d coordinate system.
  16. Each rectangle can be defined with 4 numbers with a floating point,
  17. its coordinates of its low left angle ( x, y ) , its width and height.
  18.  
  19. Write a program that reads from the input, defines two rectangles
  20. ( based on the numbers of the input ) and gives you an output of the area
  21. of the their intersecting ( overlapping ) part.
  22. If there is no intersection the program should give you an output of 0.
  23.  
  24. Note:
  25. It may be assumed that the rectangles are parallel to the coordinate axis.
  26.  
  27. Example :
  28.  
  29. Input :                  output
  30. 0053
  31. 4133                         2
  32.  
  33. 0022
  34. -1-111                       0
  35.  
  36. We shouldn't be using arrays and loops in the code.
  37.  
  38.  
  39. https://www.geeksforgeeks.org/find-two-rectangles-overlap/
  40. https://practice.geeksforgeeks.org/problems/overlapping-rectangles/0
  41. https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
  42. https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
  43. https://practice.geeksforgeeks.org/problems/check-if-two-line-segments-intersect/0
  44. https://stackoverflow.com/questions/25070577/sort-4-numbers-without-array
  45.  
  46.  
  47. A nice way to do small, fixed-size sorts is using a sorting network:
  48. https://en.wikipedia.org/wiki/Sorting_network
  49.  
  50. int tmp;
  51. if (a > b) { tmp = a; a = b; b = tmp; }
  52. if (c > d) { tmp = c; c = d; d = tmp; }
  53. if (a > c) { tmp = a; a = c; c = tmp; }
  54. if (b > d) { tmp = b; b = d; d = tmp; }
  55. if (b > c) { tmp = b; b = c; c = tmp; }
  56.  
  57. Each line codes a comparison and swap between two elements.
  58. You can use this page to generate optimal sorting networks for small numbers of inputs.
  59. http://pages.ripco.net/~jgamble/nw.html
  60. To sort in reverse order, just flip the > signs to < signs.
  61.  
  62.  
  63. Rectangle R1(x1,y1,w1,h1)
  64.  
  65.   x1,y1+h1         x1+w1,y1+h1
  66.     ---------------------
  67.     |                   |
  68.     |                   |
  69.     |                   |
  70.     |                   |
  71.     ---------------------
  72.   x1,y1            x1+w1,y1
  73.  
  74.  
  75.  
  76. Rectangle R1(x1,y1,w1,h1) and
  77. Rectangle R2(x2,y2,w2,h2)
  78.  
  79.               x2,y2+h2               x2+w2,y2+h2
  80.                 ---------------------------
  81.                 |                         |
  82.                 |                         |
  83.   x1,y1+h1      |    x1+w1,y1+h1          |
  84.     ------------|----------               |
  85.     |           |         |               |
  86.     |           |         |               |
  87.     |           |         |               |
  88.     |           ----------|----------------
  89.     |         x2,y2       |          x2+w2,y2
  90.     |                     |
  91.     |                     |
  92.     -----------------------
  93.   x1,y1              x1+w1,y1
  94.  
  95.  
  96. To simplify (halve) the problem, let's start by looking at just x point coordinates.
  97.  
  98.     ----------          -----------
  99.     x1     x1+w1        x2      x2+w2
  100.  
  101.  L1begin   L1end     L2begin    L2end
  102.  
  103. after sorting:
  104.  
  105.  first     second   third       fourth
  106.  
  107.  
  108. Let us find the overlap length of these two lengths.
  109.  
  110. Let's name the appropriate coordinates with the names
  111. L1begin,   L1end,     L2begin,    L2end
  112. and assign them the appropriate values.
  113.  
  114. Then let's sort those four coordinates by values but remembering their names
  115. and remembering their sort order
  116. first, second, third, fourth.
  117.  
  118. There are 6 possible cases:
  119.  
  120. 1. L1 is to the left of L2, no overlap
  121.     ----------          -----------
  122.  L1begin   L1end     L2begin    L2end
  123.  
  124.  
  125. 2. L2 is to the left of L1, no overlap
  126.     ----------          -----------
  127.  L2begin   L2end     L1begin    L1end
  128.  
  129.  
  130. 3. L1 is to the left of L2, overlap is L1end-L2begin
  131.     -----------------------
  132.  L1begin                L1end
  133.                 -----------------------
  134.              L2begin                L2end
  135.  
  136.  
  137. 4. L2 is to the left of L1, overlap is L2end-L1begin
  138.     -----------------------
  139.  L2begin                L2end
  140.                 -----------------------
  141.              L1begin                L1end
  142.  
  143.  
  144. 5. L2 is inside L1, overlap is L2end-L2begin
  145.     -------------------------------------
  146.  L1begin                              L1end
  147.             ---------------------
  148.          L2begin              L2end
  149.  
  150.  
  151. 6. L1 is inside L2, overlap is L1end-L1begin
  152.             ---------------------
  153.          L1begin              L1end
  154.     -------------------------------------
  155.  L2begin                              L2end
  156.  
  157.  
  158. Now we know the x-axis overlap, similarly done for the y-axis.
  159.  
  160. The overlap area is obtained by multiplying these two values.
  161.  
  162.  
  163.     You can find all my C++ programs at Dragan Milicev's pastebin:
  164.  
  165.     https://pastebin.com/u/dmilicev
  166.  
  167. */
  168.  
  169. #include <stdio.h>
  170. #include <string.h>
  171.  
  172. struct Point
  173. {
  174.     float x, y;
  175.     char name[10];              // begin, end
  176. };
  177.  
  178. struct Rectangle
  179. {
  180.     float x, y, width, height;  // x,y are coordinates of Down Left point
  181. };
  182.  
  183. // To sort in decrease order, just flip the > signs to < signs.
  184. void sort_by_x_four_numbers( struct Point *a,
  185.                              struct Point *b,
  186.                              struct Point *c,
  187.                              struct Point *d )
  188. {
  189.     struct Point tmp;
  190.  
  191.     if ( (*a).x > (*b).x )              // (*a).x  is same as  a->num
  192.     {
  193.         tmp = *a;
  194.         *a = *b;
  195.         *b = tmp;
  196.     }
  197.  
  198.     if ((*c).x > (*d).x)
  199.     {
  200.         tmp = *c;
  201.         *c = *d;
  202.         *d = tmp;
  203.     }
  204.  
  205.     if ((*a).x > (*c).x)
  206.     {
  207.         tmp = *a;
  208.         *a = *c;
  209.         *c = tmp;
  210.     }
  211.  
  212.     if ((*b).x > (*d).x)
  213.     {
  214.         tmp = *b;
  215.         *b = *d;
  216.         *d = tmp;
  217.     }
  218.  
  219.     if ((*b).x > (*c).x)
  220.     {
  221.         tmp = *b;
  222.         *b = *c;
  223.         *c = tmp;
  224.     }
  225. }
  226.  
  227. // To sort in decrease order, just flip the > signs to < signs.
  228. void sort_by_y_four_numbers( struct Point *a,
  229.                              struct Point *b,
  230.                              struct Point *c,
  231.                              struct Point *d )
  232. {
  233.     struct Point tmp;
  234.  
  235.     if ( (*a).y > (*b).y )              // (*a).y  is same as  a->num
  236.     {
  237.         tmp = *a;
  238.         *a = *b;
  239.         *b = tmp;
  240.     }
  241.  
  242.     if ((*c).y > (*d).y)
  243.     {
  244.         tmp = *c;
  245.         *c = *d;
  246.         *d = tmp;
  247.     }
  248.  
  249.     if ((*a).y > (*c).y)
  250.     {
  251.         tmp = *a;
  252.         *a = *c;
  253.         *c = tmp;
  254.     }
  255.  
  256.     if ((*b).y > (*d).y)
  257.     {
  258.         tmp = *b;
  259.         *b = *d;
  260.         *d = tmp;
  261.     }
  262.  
  263.     if ((*b).y > (*c).y)
  264.     {
  265.         tmp = *b;
  266.         *b = *c;
  267.         *c = tmp;
  268.     }
  269. }
  270.  
  271.  
  272. int main(void)
  273. {
  274.     struct Rectangle R1, R2;
  275.     struct Point L1begin, L1end, L2begin, L2end, tmp;
  276.     float lineXoverlap=0.0, lineYoverlap=0.0, overlapArea;
  277.     float L1b, L1e, L2b, L2e;   // b stands for begin, e stands for end
  278.  
  279.     R1.x = 0.0;                 // input values for rectangle R1
  280.     R1.y = 0.0;
  281.     R1.width = 3.0;
  282.     R1.height = 5.0;
  283.  
  284.     R2.x = 2.0;                 // input values for rectangle R1
  285.     R2.y = 1.0;
  286.     R2.width = 3.0;
  287.     R2.height = 6.0;
  288.  
  289. /*
  290.     -----------------           -----------------
  291.     x1          x1+w1           x2          x2+w2
  292.  
  293.     R1.x        R1.x+R1.width   R2.x        R2.x+R2.width
  294.     L1begin     L1end           L2begin     L2end
  295.     first       second          third       fourth
  296.  
  297. after sorting (only for example) :
  298.  
  299.     fourth      second          first       third
  300. */
  301.  
  302.     // let's find lineXoverlap
  303.  
  304.     L1begin.x = R1.x;                   // make four x numbers
  305.     sprintf(L1begin.name, "L1begin");
  306.  
  307.     L1end.x = R1.x + R1.width;
  308.     sprintf(L1end.name, "L1end");
  309.  
  310.  
  311.     L2begin.x = R2.x;
  312.     sprintf(L2begin.name, "L2begin");
  313.  
  314.     L2end.x = R2.x + R2.width;
  315.     sprintf(L2end.name, "L2end");
  316.  
  317.     // remember four numbers before sorting
  318.     L1b = L1begin.x;
  319.     L1e = L1end.x;
  320.     L2b = L2begin.x;
  321.     L2e = L2end.x;
  322.  
  323.     // let's sort these four numbers, without arrays and loops
  324.     sort_by_x_four_numbers( &L1begin, &L1end, &L2begin, &L2end );
  325.  
  326.     // let's calculate lineXoverlap
  327.  
  328. /*
  329. 3. L1 is to the left of L2, overlap is L1end-L2begin
  330.     -----------------------
  331.  L1begin                L1end
  332.                 -----------------------
  333.              L2begin                L2end
  334. */
  335.     if ( strcmp(L1begin.name, "L1begin") == 0 &&
  336.          strcmp(L1end.name, "L2begin")   == 0 &&
  337.          strcmp(L2begin.name, "L1end")   == 0
  338.        )
  339.         lineXoverlap = L1e - L2b;
  340.  
  341. /*
  342. 4. L2 is to the left of L1, overlap is L2end-L1begin
  343.     -----------------------
  344.  L2begin                L2end
  345.                 -----------------------
  346.              L1begin                L1end
  347. */
  348.     if ( strcmp(L1begin.name, "L2begin") == 0 &&
  349.          strcmp(L1end.name, "L1begin")   == 0 &&
  350.          strcmp(L2begin.name, "L2end")   == 0
  351.        )
  352.         lineXoverlap = L2e - L1b;
  353.  
  354. /*
  355. 5. L2 is inside L1, overlap is L2end-L2begin
  356.     -------------------------------------
  357.  L1begin                              L1end
  358.             ---------------------
  359.          L2begin              L2end
  360. */
  361.     if ( strcmp(L1begin.name, "L1begin") == 0 &&
  362.          strcmp(L1end.name, "L2begin")   == 0 &&
  363.          strcmp(L2begin.name, "L2end")   == 0
  364.        )
  365.         lineXoverlap = L2e - L2b;
  366.  
  367. /*
  368. 6. L1 is inside L2, overlap is L1end-L1begin
  369.             ---------------------
  370.          L1begin              L1end
  371.     -------------------------------------
  372.  L2begin                              L2end
  373. */
  374.     if ( strcmp(L1begin.name, "L2begin") == 0 &&
  375.          strcmp(L1end.name, "L1begin")   == 0 &&
  376.          strcmp(L2begin.name, "L1end")   == 0
  377.        )
  378.         lineXoverlap = L1e - L1b;
  379.  
  380.     printf("\n lineXoverlap = %.2f \n", lineXoverlap);
  381.  
  382.  
  383.  
  384.     // let's find lineYoverlap
  385.  
  386.     L1begin.y = R1.y;                   // make four y numbers
  387.     sprintf(L1begin.name, "L1begin");
  388.  
  389.     L1end.y = R1.y + R1.height;
  390.     sprintf(L1end.name, "L1end");
  391.  
  392.  
  393.     L2begin.y = R2.y;
  394.     sprintf(L2begin.name, "L2begin");
  395.  
  396.     L2end.y = R2.y + R2.height;
  397.     sprintf(L2end.name, "L2end");
  398.  
  399.     // remember four numbers before sorting
  400.     L1b = L1begin.y;
  401.     L1e = L1end.y;
  402.     L2b = L2begin.y;
  403.     L2e = L2end.y;
  404.  
  405.  
  406.     // let's sort these four numbers, without arrays and loops
  407.     sort_by_y_four_numbers( &L1begin, &L1end, &L2begin, &L2end );
  408.  
  409.     // let's calculate lineYoverlap
  410.  
  411. /*
  412. 3. L1 is to the left of L2, overlap is L1end-L2begin
  413.     -----------------------
  414.  L1begin                L1end
  415.                 -----------------------
  416.              L2begin                L2end
  417. */
  418.     if ( strcmp(L1begin.name, "L1begin") == 0 &&
  419.          strcmp(L1end.name, "L2begin")   == 0 &&
  420.          strcmp(L2begin.name, "L1end")   == 0
  421.        )
  422.         lineYoverlap = L1e - L2b;
  423.  
  424. /*
  425. 4. L2 is to the left of L1, overlap is L2end-L1begin
  426.     -----------------------
  427.  L2begin                L2end
  428.                 -----------------------
  429.              L1begin                L1end
  430. */
  431.     if ( strcmp(L1begin.name, "L2begin") == 0 &&
  432.          strcmp(L1end.name, "L1begin")   == 0 &&
  433.          strcmp(L2begin.name, "L2end")   == 0
  434.        )
  435.         lineYoverlap = L2e - L1b;
  436.  
  437. /*
  438. 5. L2 is inside L1, overlap is L2end-L2begin
  439.     -------------------------------------
  440.  L1begin                              L1end
  441.             ---------------------
  442.          L2begin              L2end
  443. */
  444.     if ( strcmp(L1begin.name, "L1begin") == 0 &&
  445.          strcmp(L1end.name, "L2begin")   == 0 &&
  446.          strcmp(L2begin.name, "L2end")   == 0
  447.        )
  448.         lineYoverlap = L2e - L2b;
  449.  
  450. /*
  451. 6. L1 is inside L2, overlap is L1end-L1begin
  452.             ---------------------
  453.          L1begin              L1end
  454.     -------------------------------------
  455.  L2begin                              L2end
  456. */
  457.     if ( strcmp(L1begin.name, "L2begin") == 0 &&
  458.          strcmp(L1end.name, "L1begin")   == 0 &&
  459.          strcmp(L2begin.name, "L1end")   == 0
  460.        )
  461.         lineYoverlap = L1e - L1b;
  462.  
  463.  
  464.     printf("\n lineYoverlap = %.2f \n", lineYoverlap);
  465.  
  466.  
  467.     // let's calculate overlapArea
  468.     overlapArea = lineXoverlap * lineYoverlap;
  469.  
  470.     printf("\n\n Overlap area = %.2f \n", overlapArea);
  471.  
  472.  
  473.     return 0;
  474.  
  475. } // main()
  476.  
Advertisement
RAW Paste Data Copied
Advertisement