 # 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!
1. /*
2.
3.     common_area_of_two_rectangles_v1.c
4.
8.
11.
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;              // 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.