Monday, October 6, 2014

Intersect

Problem:

TopCoder Problem Statement - Intersect

Overview:

Give the area where a set of rectangles intersect.

Java Source:
01: public class Intersect {
02: 
03:     class Rectangle {
04: 
05:         final int left;  // X coordinate of left edge
06:         final int right;
07:         final int top;  // Y coordinate of top edge
08:         final int bottom;
09: 
10:         public Rectangle(int x1, int y1, int x2, int y2) {
11: 
12:             /*
13:             * We don't know if the first point is the top-left or bottom-right
14:             * corner.  But we can assign the left edge to the smaller of the
15:             * x values, and the right edge to the larger.  Same goes for top
16:             * and bottom
17:             */
18:             this.left = Math.min(x1, x2);
19:             this.right = Math.max(x1, x2);
20:             this.top = Math.max(y1, y2);
21:             this.bottom = Math.min(y1, y2);
22:         }
23: 
24:         /*
25:         * Returns a rectangle that is the intersection of this rectangle
26:         * and the paramter r.  Returns null if there is no intersection.
27:         */
28:         public Rectangle getIntersection(Rectangle r)  {
29: 
30:             /*
31:             * If the right edge of one rectangle is >= the left edge of the
32:             * other, then there is no intersection.  Return null.  Same goes
33:             * for the other three edges.
34:             */
35:             if (r.left >= right) return null;
36:             if (r.right <= left) return null;
37:             if (r.top <= bottom) return null;
38:             if (r.bottom >= top) return null;
39: 
40:             /*
41:             * The intersection is given by the:
42:             * right-most left edge
43:             * highest bottom edge
44:             * left-most right edge
45:             * lowest top edge
46:             */
47:             return new Rectangle(
48:                     Math.max(left, r.left),
49:                     Math.max(bottom, r.bottom),
50:                     Math.min(right, r.right),
51:                     Math.min(top, r.top));
52:         }
53: 
54:         public int getArea() {
55:             return ((right - left) * (top - bottom));
56:         }
57:     }
58: 
59:     public int area(int[] x, int[] y) {
60: 
61: 
62:         /*
63:         * Start with the largest possible rectangle.  Then for each rectangle
64:         * reduce it to the intersection.  If the intersection is ever null,
65:         * return 0.
66:         */
67:         Rectangle common = null;
68: 
69:         for (int i=0; i < x.length - 1; i += 2)  {
70:             Rectangle r = new Rectangle(x[i], y[i], x[i+1], y[i+1]);
71: 
72:             if (common == null)  {
73:                 common = r;
74:             } else  {
75:                 common = common.getIntersection(r);
76:                 if (common == null) return 0;
77:             }
78:         }
79: 
80:         return common.getArea();
81:     }
82: }
Notes:

First, a Rectangle class is created to handle much of the work. This class provides a constructor, to take the input in a convenient manner; a method to get the Area of the Rectangle, and a method to return a new Rectangle that is the intersection of the current rectangle and the rectangle given as a parameter.

Then, we'll use a rectangle named common to represent the intersection of all the rectangles given. Initially, this gets set to the fist rectangle processed. Then with each additional rectangle, common becomes the intersection of itself and the new rectangle.

After all the input has been processed, return the area of the Rectangle common.

No comments:

Post a Comment